- Tytuł:
- Weak k-reconstruction of Cartesian products
- Autorzy:
-
Imrich, Wilfried
Zmazek, Blaz
Zerovnik, Janez - Powiązania:
- https://bibliotekanauki.pl/articles/743162.pdf
- Data publikacji:
- 2003
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
reconstruction problem
Cartesian product
composite graphs - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 273-285
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł