Isomorphic components of Kronecker product of bipartite graphs

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Angleški jezik
Leto izida:	1997
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM PEF - Pedagoška fakulteta
UDK:	519.17
COBISS:	8195161
ISSN:	1234-3099
Št. ogledov:	1123
Št. prenosov:	367
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Izomorfne komponente Kroneckerjevega produkta dvodelnih grafov
Sekundarni povzetek:	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.
Sekundarne ključne besede:	Teorija grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Članek v reviji
Strani:	str. 301-309
Letnik:	ǂLet. ǂ17
Zvezek:	ǂšt. ǂ2
Čas izdaje:	1997
ID:	9595935