DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 28(1) (2008) 179-184
DOI: https://doi.org/10.7151/dmgt.1400

A CANCELLATION PROPERTY FOR THE DIRECT PRODUCT OF GRAPHS

Richard H. Hammack

Department of Mathematics and Applied Mathematics
Virginia Commonwealth University
Richmond, VA 23284-2014, USA
e-mail: rhammack@vcu.edu

Abstract

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.

Keywords: graph products, graph direct product, cancellation.

2000 Mathematics Subject Classification: 05C60.

References

[1] R. Hammack, A quasi cancellation property for the direct product, Proceedings of the Sixth Slovenian International Conference on Graph Theory, under review.
[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.
[3] W. Imrich and S. Klavžar, Product Graphs; Structure and Recognition (Wiley Interscience Series in Discrete Mathematics and Optimization, 2000).
[4] L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1 (1971) 59-101.

Received 13 August 2007
Revised 5 December 2007
Accepted 5 December 2007


Close