weak reconstruction of strong product graphs开题资料.pdf

Discrete Mathematics 307 (2007) 641–649

Weak reconstruction of strong product graphsଁ
Blaž Zmazek∗,1, Janez Žerovnik1
University of Maribor, FME, Smetanova 17, 2000 Maribor, Slovenia
Received 26 June 2003; received in revised form 24 April 2004; accepted 26 September 2005
Available online 1 September 2006
Abstract
We prove that the class of nontrivial connected strong product graphs is weakly reconstructible. We also show that any nontrivial
connected thin strong product graph can be uniquely reconstructed from each of its one-vertex-deleted deleted subgraphs.
© 2006 Elsevier . All rights reserved.
MSC: 05C
Keywords: Graph; Reconstruction problem; Strong product; Composite graphs
1. Introduction
In [11] Ulam asked the question of whether a graph G is uniquely determined up to isomorphism by its deck, which
is the multiset of all isomorphism classes of graphs G\x obtained from G by deleting a vertex x and all edges incident to
it. While the conjecture is false for infinite graphs it still is open for finite graphs. When reconstructing a class of graphs,
the problem of reconstruction partitions naturally into tw