1 / 9
文档名称:

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

格式:pdf   大小:199KB   页数:9页
下载后只包含 1 个 PDF 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

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

上传人:好用的文档 2021/10/16 文件大小:199 KB

下载得到文件列表

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