Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: composite graphs

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Weak k-reconstruction of Cartesian products

100%

Imrich W., Zmazek B., Zerovnik J.

Discussiones Mathematicae Graph Theory

2003

tom 23

nr 2

273-285

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Imrich W.

1 Zerovnik J.

1 Zmazek B.

1 2003

Wyniki wyszukiwania

Weak k-reconstruction of Cartesian products