Geodesic
Weak k-reconstruction of Cartesian products
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 273-285

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: reconstruction problem, Cartesian product, composite graphs 
@article{DMGT_2003_23_2_a5,
     author = {Imrich, Wilfried and Zmazek, Blaz and Zerovnik, Janez},
     title = {Weak k-reconstruction of {Cartesian} products},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {273--285},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a5/}
}
TY  - JOUR
AU  - Imrich, Wilfried
AU  - Zmazek, Blaz
AU  - Zerovnik, Janez
TI  - Weak k-reconstruction of Cartesian products
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 273
EP  - 285
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a5/
LA  - en
ID  - DMGT_2003_23_2_a5
ER  - 
%0 Journal Article
%A Imrich, Wilfried
%A Zmazek, Blaz
%A Zerovnik, Janez
%T Weak k-reconstruction of Cartesian products
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 273-285
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a5/
%G en
%F DMGT_2003_23_2_a5
Imrich, Wilfried; Zmazek, Blaz; Zerovnik, Janez. Weak k-reconstruction of Cartesian products. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 273-285. http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a5/