Graph isomorphism conjectures for edge-, spanning-tree-, and subset-deleted graphs
Statement
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.
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.