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:	2005
Tipologija:	1.02 - Pregledni znanstveni članek
Organizacija:	UM FS - Fakulteta za strojništvo
UDK:	519.17
COBISS:	13780313
ISSN:	1318-4865
Št. ogledov:	0
Št. prenosov:	0
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. 1-8
Letnik:	ǂVol. ǂ43
Zvezek:	ǂšt. ǂ987
Čas izdaje:	2005
ID:	66668