期刊
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据