PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | 23 | 2 | 273-285
Tytuł artykułu

Weak k-reconstruction of Cartesian products

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
By Ulam's conjecture every finite graph G can be reconstructed from its deck of vertex deleted subgraphs. The conjecture is still open, but many special cases have been settled. In particular, one can reconstruct Cartesian products. We consider the case of k-vertex deleted subgraphs of Cartesian products, and prove that one can decide whether a graph H is a k-vertex deleted subgraph of a Cartesian product G with at least k+1 prime factors on at least k+1 vertices each, and that H uniquely determines G. This extends previous work of the authors and Sims. The paper also contains a counterexample to a conjecture of MacAvaney.
Wydawca
Rocznik
Tom
23
Numer
2
Strony
273-285
Opis fizyczny
Daty
wydano
2003
otrzymano
2001-09-26
poprawiono
2002-04-12
Twórcy
  • Montanuniversität Leoben, Institut für Mathematik und Angewandte Geometrie, Franz-Josef Straße 18, A-8700 Leoben, Austria
autor
  • University of Maribor, Faculty of Mechanical Engineering, Smetanova 17, 2000 Maribor, Slovenia
  • IMFM, Jadranska 19, Ljubljana
  • University of Maribor, Faculty of Mechanical Engineering, Smetanova 17, 2000 Maribor, Slovenia
  • IMFM, Jadranska 19, Ljubljana
Bibliografia
  • [1] W. Dörfler, Some results on the reconstruction of graphs, Colloq. Math. Soc. János Bolyai, 10, Keszthely, Hungary (1973) 361-383.
  • [2] T. Feder, Product graph representations, J. Graph Theory 16 (1992) 467-488, doi: 10.1002/jgt.3190160508.
  • [3J. Feigenbaum and R. Haddad, On factorable extensions and subgraphs of prime graphs, SIAM J. Discrete Math. 2 (1989) 197-218.
  • [4] J. Fisher, A counterexample to the countable version of a conjecture of Ulam, J. Combin. Theory 7 (1969) 364-365, doi: 10.1016/S0021-9800(69)80063-3.
  • [5] J. Hagauer and J. Zerovnik, An algorithm for the weak reconstruction of Cartesian-product graphs, J. Combin. Information & System Sciences 24 (1999) 87-103.
  • [6W. Imrich, Embedding graphs into Cartesian products, Graph Theory and Applications: East and West, Ann. New York Acad. Sci. 576 (1989) 266-274.
  • [7] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
  • [8] W. Imrich and J. Zerovnik, Factoring Cartesian product graphs, J. Graph Theory 18 (1994) 557-567.
  • [9] W. Imrich and J. Zerovnik, On the weak reconstruction of Cartesian-product graphs, Discrete Math. 150 (1996) 167-178, doi: 10.1016/0012-365X(95)00185-Y.
  • [10] S. Klavžar, personal communication.
  • [11] K.L. MacAvaney, A conjecture on two-vertex deleted subgraphs of Cartesian products, Lecture Notes in Math. 829 (1980) 172-185, doi: 10.1007/BFb0088911.
  • [12] G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457, doi: 10.1007/BF01162967.
  • [13] J. Sims, Stability of the cartesian product of graphs (M. Sc. thesis, University of Melbourne, 1976).
  • [14] J. Sims and D.A. Holton, Stability of cartesian products, J. Combin. Theory (B) 25 (1978) 258-282, doi: 10.1016/0095-8956(78)90002-3.
  • [15] S.M. Ulam, A Collection of Mathematical Problems, (Wiley, New York, 1960) p. 29.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1202
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ć.