Geodesic
Cancellation of direct products of digraphs
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 4, pp. 575-590.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2010_30_4_a4,
     author = {Hammack, Richard and Toman, Katherine},
     title = {Cancellation of direct products of digraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {575--590},
     publisher = {mathdoc},
     volume = {30},
     number = {4},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a4/}
}
TY  - JOUR
AU  - Hammack, Richard
AU  - Toman, Katherine
TI  - Cancellation of direct products of digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 575
EP  - 590
VL  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a4/
LA  - en
ID  - DMGT_2010_30_4_a4
ER  - 
%0 Journal Article
%A Hammack, Richard
%A Toman, Katherine
%T Cancellation of direct products of digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 575-590
%V 30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a4/
%G en
%F DMGT_2010_30_4_a4
Hammack, Richard; Toman, Katherine. Cancellation of direct products of digraphs. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 4, pp. 575-590. http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a4/

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