PDF
Discussiones Mathematicae Graph Theory 30(4) (2010)
575-590
DOI: https://doi.org/10.7151/dmgt.1515
CANCELLATION OF DIRECT PRODUCTS OF DIGRAPHS
Richard H. Hammack and Katherine E. Toman
Department of Mathematics and Applied Mathematics
Virginia Commonwealth University
Richmond, VA 23284-2014, USA
e-mail: | rhammack@vcu.edu |
e-mail: | tomanke@vcu.edu |
Abstract
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.Keywords: graph direct product, graph product cancellation, digraphs.
2010 Mathematics Subject Classification: Primary: 05C76; Secondary: 05C20, 05C60.
References
[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. |
[2] | R. Hammack, On direct product cancellation of graphs, Discrete Math. 309 (2009) 2538-2543, doi: 10.1016/j.disc.2008.06.004. |
[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. |
[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). |
[5] | L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1 (1971) 145-156, doi: 10.1007/BF02029172. |
Received 16 July 2009
Revised 18 November 2009
Accepted 18 November 2009
Close