PDF

Discussiones Mathematicae Graph Theory 26(2) (2006) 231-248
DOI: https://doi.org/10.7151/dmgt.1316

ISOMORPHIC COMPONENTS OF DIRECT PRODUCTS OF BIPARTITE GRAPHS

Richard Hammack

Department of Mathematics
Virginia Commonwealth University
Richmond, Virginia 23284-2014, USA
e-mail: rhammack@rmc.edu

Abstract

A standard result states the direct product of two connected bipartite graphs has exactly two components. Jha, Klavžar and Zmazek proved that if one of the factors admits an automorphism that interchanges partite sets, then the components are isomorphic. They conjectured the converse to be true. We prove the converse holds if the factors are square-free. Further, we present a matrix-theoretic conjecture that, if proved, would prove the general case of the converse; if refuted, it would produce a counterexample.

Keywords: direct product, tensor product, Kronecker product, bipartite graph.

2000 Mathematics Subject Classification: 05C60.

References

[1]	T. Chow, The Q-spectrum and spanning trees of tensor products of bipartite graphs, Proc. Amer. Math. Soc. 125 (1997) 3155-3161, doi: 10.1090/S0002-9939-97-04049-5.
[2]	W. Imrich and S. Klavžar, Product Graphs; Structure and Recognition (Wiley Interscience Series in Discrete Mathematics and Optimization, New York, 2000).
[3]	P. Jha, S. Klavžar and B. Zmazek, Isomorphic components of Kronecker product of bipartite graphs, Discuss. Math. Graph Theory 17 (1997) 302-308, doi: 10.7151/dmgt.1057.
[4]	P. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962) 47-52, doi: 10.1090/S0002-9939-1962-0133816-6.

Received 29 August 2005
Revised 23 November 2005