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:	2008
Typology:	1.08 - Published Scientific Conference Contribution
Organization:	UM FS - Faculty of Mechanical Engineering
UDC:	519.17
COBISS:	14621529
ISSN:	0012-365X
Views:	37
Downloads:	17
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. 820-826
ID:	1473501