Graph isomorphism conjectures for edge-, spanning-tree-, and subset-deleted graphs
Graph isomorphism conjectures for edge-, spanning-tree-, and subset-deleted graphs
Let be graphs, let and be edge subsets, let be spanning trees, and let and be proper subsets. Graph isomorphism conjectures. (i) If , , and are connected -graphs admitting the isomorphic subgraph similarity, then by Kelly–Ulam's Reconstruction Conjecture. (ii) If each spanning tree of a connected -graph corresponds to a spanning tree of another connected graph with , and vice versa, then . (iii) If and have vertices and each proper subset corresponds to a proper subset with , then . These proposed extensions of reconstruction from deleted subgraphs concern when graph isomorphism is determined by families of edge-, spanning-tree-, or subset-deleted graphs; the source gives no resolution status.
Sources & referencesView supporting material
Primary source
Fei Ma and Bing Yao, “Topological Structures of Sets and their Subsets”, arXiv:2503.20167 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.