Weak k-reconstruction of Cartesian products

Wilfried Imrich; Blaz Zmazek; Janez Zerovnik

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 2, page 273-285
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Wilfried Imrich, Blaz Zmazek, and Janez Zerovnik. "Weak k-reconstruction of Cartesian products." Discussiones Mathematicae Graph Theory 23.2 (2003): 273-285. <http://eudml.org/doc/270511>.

@article{WilfriedImrich2003,
abstract = {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.},
author = {Wilfried Imrich, Blaz Zmazek, Janez Zerovnik},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {reconstruction problem; Cartesian product; composite graphs; Cartesian products},
language = {eng},
number = {2},
pages = {273-285},
title = {Weak k-reconstruction of Cartesian products},
url = {http://eudml.org/doc/270511},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Wilfried Imrich
AU - Blaz Zmazek
AU - Janez Zerovnik
TI - Weak k-reconstruction of Cartesian products
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 2
SP - 273
EP - 285
AB - 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.
LA - eng
KW - reconstruction problem; Cartesian product; composite graphs; Cartesian products
UR - http://eudml.org/doc/270511
ER -

References

top
  1. [1] W. Dörfler, Some results on the reconstruction of graphs, Colloq. Math. Soc. János Bolyai, 10, Keszthely, Hungary (1973) 361-383. 
  2. [2] T. Feder, Product graph representations, J. Graph Theory 16 (1992) 467-488, doi: 10.1002/jgt.3190160508. Zbl0766.05092
  3. [3J. Feigenbaum and R. Haddad, On factorable extensions and subgraphs of prime graphs, SIAM J. Discrete Math. 2 (1989) 197-218. Zbl0736.05061
  4. [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. Zbl0187.21304
  5. [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. Zbl1219.05094
  6. [6W. Imrich, Embedding graphs into Cartesian products, Graph Theory and Applications: East and West, Ann. New York Acad. Sci. 576 (1989) 266-274. 
  7. [7] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000). 
  8. [8] W. Imrich and J. Zerovnik, Factoring Cartesian product graphs, J. Graph Theory 18 (1994) 557-567. Zbl0811.05054
  9. [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. Zbl0858.05076
  10. [10] S. Klavžar, personal communication. 
  11. [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. [12] G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457, doi: 10.1007/BF01162967. Zbl0093.37603
  13. [13] J. Sims, Stability of the cartesian product of graphs (M. Sc. thesis, University of Melbourne, 1976). 
  14. [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. Zbl0405.05052
  15. [15] S.M. Ulam, A Collection of Mathematical Problems, (Wiley, New York, 1960) p. 29. Zbl0086.24101

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.