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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1202,
author = {Wilfried Imrich and Blaz Zmazek and Janez Zerovnik},
title = {Weak k-reconstruction of Cartesian products},
journal = {Discussiones Mathematicae Graph Theory},
volume = {23},
year = {2003},
pages = {273-285},
zbl = {1055.05105},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1202}
}
Wilfried Imrich; Blaz Zmazek; Janez Zerovnik. Weak k-reconstruction of Cartesian products. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 273-285. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1202/
[000] [1] W. Dörfler, Some results on the reconstruction of graphs, Colloq. Math. Soc. János Bolyai, 10, Keszthely, Hungary (1973) 361-383.
[001] [2] T. Feder, Product graph representations, J. Graph Theory 16 (1992) 467-488, doi: 10.1002/jgt.3190160508. | Zbl 0766.05092
[002] [3J. Feigenbaum and R. Haddad, On factorable extensions and subgraphs of prime graphs, SIAM J. Discrete Math. 2 (1989) 197-218. | Zbl 0736.05061
[003] [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. | Zbl 0187.21304
[004] [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. | Zbl 1219.05094
[005] [6W. Imrich, Embedding graphs into Cartesian products, Graph Theory and Applications: East and West, Ann. New York Acad. Sci. 576 (1989) 266-274.
[006] [7] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
[007] [8] W. Imrich and J. Zerovnik, Factoring Cartesian product graphs, J. Graph Theory 18 (1994) 557-567. | Zbl 0811.05054
[008] [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. | Zbl 0858.05076
[009] [10] S. Klavžar, personal communication.
[010] [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.
[011] [12] G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457, doi: 10.1007/BF01162967. | Zbl 0093.37603
[012] [13] J. Sims, Stability of the cartesian product of graphs (M. Sc. thesis, University of Melbourne, 1976).
[013] [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. | Zbl 0405.05052
[014] [15] S.M. Ulam, A Collection of Mathematical Problems, (Wiley, New York, 1960) p. 29. | Zbl 0086.24101