Graham's tree reconstruction conjecture
Let be a simple undirected graph. A tree is an acyclic, connected graph. Its line graph has vertex set , with distinct adjacent exactly when and are incident in . Define the iterated line graphs by
and
Graham's tree reconstruction conjecture. For each sequence of natural numbers , all the conditions for are satisfied by at most one tree .
The conjecture asks whether the sequence of sizes of a tree and all its iterated line graphs uniquely determines the tree. Apart from a few simple observations, little is known; the paper gives lower bounds on the number of trees distinguishable by these sequences but does not resolve the conjecture.
References
- Joshua Cooper, Bill Kay and Anton Swifton, “Graham's Tree Reconstruction Conjecture and a Waring-Type Problem on Partitions”, arXiv:1109.0522 (2017).
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
No solutions have been posted yet.