Cancellation of direct products of digraphs

Richard H. Hammack; Katherine E. Toman

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 4, page 575-590
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Richard H. Hammack, and Katherine E. Toman. "Cancellation of direct products of digraphs." Discussiones Mathematicae Graph Theory 30.4 (2010): 575-590. <http://eudml.org/doc/271052>.

@article{RichardH2010,
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.},
author = {Richard H. Hammack, Katherine E. Toman},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph direct product; graph product cancellation; digraphs},
language = {eng},
number = {4},
pages = {575-590},
title = {Cancellation of direct products of digraphs},
url = {http://eudml.org/doc/271052},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Richard H. Hammack
AU - Katherine E. Toman
TI - Cancellation of direct products of digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 4
SP - 575
EP - 590
AB - 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.
LA - eng
KW - graph direct product; graph product cancellation; digraphs
UR - http://eudml.org/doc/271052
ER -

References

top
  1. [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. Zbl1154.05045
  2. [2] R. Hammack, On direct product cancellation of graphs, Discrete Math. 309 (2009) 2538-2543, doi: 10.1016/j.disc.2008.06.004. Zbl1210.05124
  3. [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. Zbl1062.05139
  4. [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. [5] L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1 (1971) 145-156, doi: 10.1007/BF02029172. Zbl0223.08002

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.