Graph isomorphism conjectures for edge-, spanning-tree-, and subset-deleted graphs

Let G,H,Ga,GbG,H,G_a,G_b be graphs, let EGE(G)E_G\subset E(G) and EHE(H)E_H\subset E(H) be edge subsets, let Ta,TbT_a,T_b be spanning trees, and let SGV(G)E(G)S_G\in V(G)\cup E(G) and SHV(H)E(H)S_H\in V(H)\cup E(H) be proper subsets. Graph isomorphism conjectures. (i) If EG=EH|E_G|=|E_H|, GEGHEHG-E_G\cong H-E_H, and G,HG,H are connected (p,q)(p,q)-graphs admitting the isomorphic subgraph similarity, then GHG\cong H by Kelly–Ulam's Reconstruction Conjecture. (ii) If each spanning tree TaT_a of a connected (p,q)(p,q)-graph GaG_a corresponds to a spanning tree TbT_b of another connected graph GbG_b with TaTbT_a\cong T_b, and vice versa, then GaGbG_a\cong G_b. (iii) If GG and HH have nn vertices and each proper subset SGV(G)E(G)S_G\in V(G)\cup E(G) corresponds to a proper subset SHV(H)E(H)S_H\in V(H)\cup E(H) with GSGHSHG-S_G\cong H-S_H, then GHG\cong H. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.