PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2008 | 28 | 1 | 179-184
Tytuł artykułu

A cancellation property for the direct product of graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
28
Numer
1
Strony
179-184
Opis fizyczny
Daty
wydano
2008
otrzymano
2007-08-13
poprawiono
2007-12-05
zaakceptowano
2007-12-05
Twórcy
  • Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, VA 23284-2014, USA
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1400
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.