Partial cubes are distance graphs

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Angleški jezik
Leto izida:	2008
Tipologija:	1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	14621529
ISSN:	0012-365X
Št. ogledov:	37
Št. prenosov:	17
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Delne kocke so razdaljni grafi
Sekundarni povzetek:	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:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	Str. 820-826
ID:	1473501