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

About 1 year old · traced to

Let G,H,Ga,GbG,H,G_a,G_b be graphs, let EG⊂E(G)E_G\subset E(G) and EH⊂E(H)E_H\subset E(H) be edge subsets, let Ta,TbT_a,T_b be spanning trees, and let SG∈V(G)∪E(G)S_G\in V(G)\cup E(G) and SH∈V(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|, G−EG≅H−EHG-E_G\cong H-E_H, and G,HG,H are connected (p,q)(p,q)-graphs admitting the isomorphic subgraph similarity, then G≅HG\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 Ta≅TbT_a\cong T_b, and vice versa, then Ga≅GbG_a\cong G_b. (iii) If GG and HH have nn vertices and each proper subset SG∈V(G)∪E(G)S_G\in V(G)\cup E(G) corresponds to a proper subset SH∈V(H)∪E(H)S_H\in V(H)\cup E(H) with G−SG≅H−SHG-S_G\cong H-S_H, then G≅HG\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.

References

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.