4.7 Article

Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs

期刊

INFORMATION SCIENCES
卷 654, 期 -, 页码 -

出版社

ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2023.119858

关键词

Reconstruction conjecture; Graph isomorphism; Hypomorphism; Reconstructible graphs; Graph recognition; Quadratric assignment

向作者/读者索取更多资源

This paper provides a unified proof method for the reconstruction conjecture of undirected graphs and verifies that the conjecture holds true for finite undirected graphs with at least three vertices.
Background: The Kelly-Ulam reconstruction conjecture proposes that a graph's isomorphism class is determined by the classes of its multiset of vertex-deleted subgraphs. Although the conjecture has been verified for many families of undirected graphs, several cases remain unresolved. This analysis proposes a unified proof of the reconstruction conjecture for all finite undirected graphs. Methodology: A vertex-substitution framework is introduced, in which vertex-deleted subgraphs are augmented by a substitute vertex connected universally with characteristic edge weight (an arbitrary constant outside the deck alphabet). Vertex-substituted subgraphs have as many vertices as the parent graph, permitting tensor representation of the deck reconstruction.Results: Hypomorphism under vertex-deletion is shown to imply hypomorphism under vertex-substitution and vice-versa. In the vertex-substitution framework, bijections mapping cards be-tween hypomorphic decks are shown to map vertices between the parent graphs, demonstrating that an isomorphic mapping always exists. Conclusions: The Kelly-Ulam reconstruction conjecture is verified for finite, undirected graphs on at least three vertices. The vertex-substitution framework provides a unified analytical approach to the reconstruction conjecture for all undirected graphs.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据