# Isomorphic components of Kronecker product of bipartite graphs

Pranava K. Jha; Sandi Klavžar; Blaž Zmazek

Discussiones Mathematicae Graph Theory (1997)

- Volume: 17, Issue: 2, page 301-309
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPranava K. Jha, Sandi Klavžar, and Blaž Zmazek. "Isomorphic components of Kronecker product of bipartite graphs." Discussiones Mathematicae Graph Theory 17.2 (1997): 301-309. <http://eudml.org/doc/270647>.

@article{PranavaK1997,

abstract = {Weichsel (Proc. Amer. Math. Soc. 13 (1962) 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.},

author = {Pranava K. Jha, Sandi Klavžar, Blaž Zmazek},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Kronecker product; bipartite graphs; graph isomorphism; graph products; Kronecker product of graphs},

language = {eng},

number = {2},

pages = {301-309},

title = {Isomorphic components of Kronecker product of bipartite graphs},

url = {http://eudml.org/doc/270647},

volume = {17},

year = {1997},

}

TY - JOUR

AU - Pranava K. Jha

AU - Sandi Klavžar

AU - Blaž Zmazek

TI - Isomorphic components of Kronecker product of bipartite graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1997

VL - 17

IS - 2

SP - 301

EP - 309

AB - Weichsel (Proc. Amer. Math. Soc. 13 (1962) 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.

LA - eng

KW - Kronecker product; bipartite graphs; graph isomorphism; graph products; Kronecker product of graphs

UR - http://eudml.org/doc/270647

ER -

## References

top- [1] L. Babai, Automorphism Groups, Isomorphism, Reconstruction, Chapter 27 in Handbook of Combinatorics (R.L. Graham. M. Grötschel, L. Lovász, eds.) Elsevier, Amsterdam, (1995) 1447-1540. Zbl0846.05042
- [2] D. Greenwell and L. Lovász, Applications of product colouring, Acta Math. Acad. Sci. Hungar. 25 (1974) 335-340, doi: 10.1007/BF01886093. Zbl0294.05108
- [3] S. Hedetniemi, Homomorphisms of graphs and automata, University of Michigan, Technical Report 03105-44-T, (1966).
- [4] P. Hell, An introduction to the category of graphs, Ann. New York Acad. Sci. 328 (1979) 120-136, doi: 10.1111/j.1749-6632.1979.tb17773.x.
- [5] W. Imrich, Factorizing cardinal product graphs in polynomial time, Discrete Math., to appear.
- [6] P.K. Jha, Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths, Indian J. Pure Appl. Math. 23 (1992) 585-602. Zbl0768.05077
- [7] P.K. Jha, Hamiltonian decompositions of products of cycles, Indian J. Pure Appl. Math. 23 (1992) 723-729. Zbl0783.05080
- [8] P.K. Jha, N. Agnihotri and R. Kumar, Edge exchanges in Hamiltonian decompositions of Kronecker-product graphs, Comput. Math. Applic. 31 (1996) 11-19, doi: 10.1016/0898-1221(95)00189-1. Zbl0849.05057
- [9] F. Lalonde, Le probleme d'etoiles pour graphes est NP-complet, Discrete Math. 33 (1981) 271-280, doi: 10.1016/0012-365X(81)90271-5. Zbl0458.68025
- [10] R.H. Lamprey and B.H. Barnes, Product graphs and their applications, Modelling and Simulation, 5 (1974) 1119-1123 (Proc Fifth Annual Pittsburgh Conference, Instrument Society of America, Pittsburgh, PA, 1974).
- [11] J. Neetil, Representations of graphs by means of products and their complexity, Lecture Notes in Comput. Sci. 118 (1981) 94-102, doi: 10.1007/3-540-10856-4₇6.
- [12] E. Pesch, Minimal extensions of graphs to absolute retracts, J. Graph Theory 11 (1987) 585-598, doi: 10.1002/jgt.3190110416. Zbl0649.05050
- [13] V.G. Vizing, The Cartesian product of graphs, Vyc. Sis. 9 (1963) 30-43.
- [14] P.M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962) 47-52, doi: 10.1090/S0002-9939-1962-0133816-6. Zbl0102.38801

## Citations in EuDML Documents

top- Boštjan Brešar, Pranava K. Jha, Sandi Klavžar, Blaž Zmazek, Median and quasi-median direct products of graphs
- Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Spacapan, Some results on total domination in direct products of graphs
- Antoaneta Klobučar, On the $k$-dominating number of Cartesian products of two paths

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.