Cancellation of direct products of digraphs

• Autorzy: Richard H. Hammack , Katherine E. Toman
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph direct product; graph product cancellation; digraphs

Kategorie tematyczne

• 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
• 05C20: Directed graphs (digraphs), tournaments
• 05C76: Graph operations (line graphs, products, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2010
• Tom: 30
• Numer: 4
• Strony: 575-590

Daty

wydano

2010

otrzymano

2009-07-16

poprawiono

2009-11-18

zaakceptowano

2009-11-18

Twórcy

autor

Richard H. Hammack

• Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, VA 23284-2014, USA

autor

Katherine E. Toman

• Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, VA 23284-2014, USA

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1515