Partial cubes are distance graphs

Melita Gorše Pihler (Author), Janez Žerovnik (Author)

Abstract

Chatrand, Kubicki in Schultz [Aequationes Math. 55 (1998) 129-145] so postavili domnevo, da so vsi dvodelni grafi razdaljni grafi. V tem članku pokažemo, da so vsi grafi podmnožice dvodelnih grafov, in sicer delne kocke, razdaljni grafi.

Keywords

matematika;teorija grafov;razdaljni graf;delna kocka;hiperkocka;izometrični podgraf;vložitev;mathematics;graph theory;distance graph;partial cube;hypercube;isometric subgraph;embedding;

Data

Language:	English
Year of publishing:	2005
Typology:	1.02 - Review Article
Organization:	UM FS - Faculty of Mechanical Engineering
UDC:	519.17
COBISS:	13780313
ISSN:	1318-4865
Views:	0
Downloads:	0
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Delne kocke so razdaljni grafi
Secondary abstract:	Chatrand, Kubicki and Schultz [Aequationes Math. 55 (1998) 129-145] have recently conjectured that all bipartite graphs are distance graphs. Here we show that all graphs of a large subclass of bipartite graphs, i.e. partial cubes, are distance graphs.
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1-8
Volume:	ǂVol. ǂ43
Issue:	ǂšt. ǂ987
Chronology:	2005
ID:	66668