ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.