Given graphs A, B and C for which A×C ≅ B×C, it is not generally true that A ≅ B. However, it is known that A×C ≅ B×C implies A ≅ B provided that C is non-bipartite, or that there are homomorphisms from A and B to C. This note proves an additional cancellation property. We show that if B and C are bipartite, then A×C ≅ B×C implies A ≅ B if and only if no component of B admits an involution that interchanges its partite sets.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1400,
author = {Richard H. Hammack},
title = {A cancellation property for the direct product of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {28},
year = {2008},
pages = {179-184},
zbl = {1154.05045},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1400}
}
Richard H. Hammack. A cancellation property for the direct product of graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 179-184. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1400/
[000] [1] R. Hammack, A quasi cancellation property for the direct product, Proceedings of the Sixth Slovenian International Conference on Graph Theory, under review. | Zbl 1154.05045
[001] [2] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics (Oxford U. Press, 2004), doi: 10.1093/acprof:oso/9780198528173.001.0001. | Zbl 1062.05139
[002] [3] W. Imrich and S. Klavžar, Product Graphs; Structure and Recognition (Wiley Interscience Series in Discrete Mathematics and Optimization, 2000). | Zbl 0963.05002
[003] [4] L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1 (1971) 59-101.