A cancellation property for the direct product of graphs

Richard H. Hammack

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 1, page 179-184
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Richard H. Hammack. "A cancellation property for the direct product of graphs." Discussiones Mathematicae Graph Theory 28.1 (2008): 179-184. <http://eudml.org/doc/270517>.

@article{RichardH2008,
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.},
author = {Richard H. Hammack},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph products; graph direct product; cancellation},
language = {eng},
number = {1},
pages = {179-184},
title = {A cancellation property for the direct product of graphs},
url = {http://eudml.org/doc/270517},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Richard H. Hammack
TI - A cancellation property for the direct product of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 1
SP - 179
EP - 184
AB - 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.
LA - eng
KW - graph products; graph direct product; cancellation
UR - http://eudml.org/doc/270517
ER -

References

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.