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

Abstract

top
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.

How to cite

top

Pranava 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. [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. [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. [3] S. Hedetniemi, Homomorphisms of graphs and automata, University of Michigan, Technical Report 03105-44-T, (1966). 
  4. [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. [5] W. Imrich, Factorizing cardinal product graphs in polynomial time, Discrete Math., to appear. 
  6. [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. [7] P.K. Jha, Hamiltonian decompositions of products of cycles, Indian J. Pure Appl. Math. 23 (1992) 723-729. Zbl0783.05080
  8. [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. [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. [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. [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. [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. [13] V.G. Vizing, The Cartesian product of graphs, Vyc. Sis. 9 (1963) 30-43. 
  14. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.