Isomorphic components of Kronecker product of bipartite graphs

Pranava Jha (Author), Sandi Klavžar (Author), Blaž Zmazek (Author)

Abstract

Weichsel je leta 1962 dokazal, da ima Kroneckerjev produkt dveh povezanih dvodelnih grafov natanko dve povezani komponenti. Predstavljen je pogoj, ki zagotavlja, da sta ti dve komponenti izomorfni. Pokazano je, da imajo mnogi znani grafi vpeljano lastnost. Dokazan je tudi delni obrat izreka in podana je domneva, da obrat obstaja v splošnem.

Keywords

matematika;teorija grafov;Kroneckerjev produkt grafov;dvodelni grafi;izomorfizem grafov;ne zaključna dela;mathematics;graph theory;Kronecker graph product;bipartite graphs;graph isomorphism;

Data

Language:	English
Year of publishing:	1997
Typology:	1.01 - Original Scientific Article
Organization:	UM PEF - Faculty of Education
UDC:	519.17
COBISS:	8195161
ISSN:	1234-3099
Views:	1123
Downloads:	367
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Izomorfne komponente Kroneckerjevega produkta dvodelnih grafov
Secondary abstract:	Weichsel (Proc. Amer. Math. Soc. 13 (1992), 47-52) proved that the Kronecker product of two connected bipartite graphs consists of two connected components. A condition on the factor graphs is presented which ensures that such components are isomorphic. It is demonstrated that several familiar and easily constructible graphs are amenable to that condition. A partial converse is proved for the above condition and it is conjectured that the converse is true in general.
Secondary keywords:	Teorija grafov;
URN:	URN:SI:UM:
Type (COBISS):	Article
Pages:	str. 301-309
Volume:	ǂLet. ǂ17
Issue:	ǂšt. ǂ2
Chronology:	1997
ID:	9595935