On subgraphs of Cartesian product graphs

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

Abstract

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.

Keywords

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

Data

Language:	English
Year of publishing:	1999
Typology:	0 - Not set
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	8984665
ISSN:	1318-4865
Views:	57
Downloads:	11
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	O podgrafih kartezičnega produkta grafov
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;kartezični produkt grafov;podgrafi;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1-9
Volume:	ǂVol. ǂ37
Issue:	ǂšt. ǂ661
Chronology:	1999
ID:	65803