We investigate expressions of form A×C ≅ B×C involving direct products of digraphs. Lovász gave exact conditions on C for which it necessarily follows that A ≅ B. We are here concerned with a different aspect of cancellation. We describe exact conditions on A for which it necessarily follows that A ≅ B. In the process, we do the following: Given an arbitrary digraph A and a digraph C that admits a homomorphism onto an arc, we classify all digraphs B for which A×C ≅ B×C.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1515,
author = {Richard H. Hammack and Katherine E. Toman},
title = {Cancellation of direct products of digraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {575-590},
zbl = {1217.05197},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1515}
}
Richard H. Hammack; Katherine E. Toman. Cancellation of direct products of digraphs. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 575-590. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1515/
[000] [1] R. Hammack, A cancellation property for the direct product of graphs, Discuss. Math. Graph Theory 28 (2008) 179-185, doi: 10.7151/dmgt.1400. | Zbl 1154.05045
[001] [2] R. Hammack, On direct product cancellation of graphs, Discrete Math. 309 (2009) 2538-2543, doi: 10.1016/j.disc.2008.06.004. | Zbl 1210.05124
[002] [3] 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
[003] [4] W. Imrich and S. Klavžar, Product Graphs: Structure and recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley and Sons, New York, 2000).
[004] [5] L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1 (1971) 145-156, doi: 10.1007/BF02029172. | Zbl 0223.08002