On subgraphs of Cartesian product graphs

Sandi Klavžar (Avtor), Alenka Lipovec (Avtor), Marko Petkovšek (Avtor)

Povzetek

Karakterizirani so grafi, ki jih lahko predstavimo kot netrivialen podgraf kartezičnega produkta grafov. Kot posledica je pokazano, da ima vsak dvodelni graf z radijem 2, ki ne vsebuje ▫$K_{2,3}$▫, tako predstavitev. Neskončna družina bazičnih podgrafov je tudi konstruirana - dosedaj je bilo znanih le končno takih grafov.

Ključne besede

matematika;teorija grafov;kartezični produkt grafov;podgrafi;mathematics;graph theory;Cartesian product graphs;subgraphs;

Podatki

Jezik:	Angleški jezik
Leto izida:	1999
Tipologija:	0 - Ni določena
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	8984665
ISSN:	1318-4865
Št. ogledov:	57
Št. prenosov:	11
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	O podgrafih kartezičnega produkta grafov
Sekundarni povzetek:	Graphs which can be represented as nontrivial subgraphs of Cartesian product graphs are characterized. As a corollary it is shown that any bipartite, ▫$K_{2,3}$▫-free graphs of radius 2 has such a representation. An infinite family of graphs which have no such representation and contain no proper representable subgraph is also constructed. Only a finite number of such graphs have been previously known.
Sekundarne ključne besede:	matematika;teorija grafov;kartezični produkt grafov;podgrafi;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1-9
Letnik:	ǂVol. ǂ37
Zvezek:	ǂšt. ǂ661
Čas izdaje:	1999
ID:	65803