An Experimental Note on Graham's Tree Reconstruction Conjecture

An Experimental Note on Graham's Tree Reconstruction Conjecture
By Kaylee Weatherspoon and Doron Zeilberger
.pdf

Written: May 2025
Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Graph reconstruction questions, increasingly relevant to bioinformatics, network science, and cybersecurity, ask whether a given set of information suffices to uniquely determine a graph. Often, as is the case in the venerable Graph Reconstruction Conjecture, the given information is a set of subgraphs. For example, it is well known that any tree is uniquely determined by its “deck,” the multiset of subgraphs obtained by deleting a single vertex. Graham's Tree Reconstruction Conjecture stands out among these problems in that it asks if a tree is reconstructible from a specific integer sequence, rather than a collection of subgraphs ([2]). Letting L(G) denote the line graph of G, we refer to the following as the Graham sequence of a tree: |V (G)|, |V (L(G))|, |V (L(L(G))|, . . . . Graham's Tree Reconstruction Conjecture asks whether a tree is uniquely determined by its Graham sequence.
In this experimental paper, we fully confirm Graham's conjecture for all trees up to 11 vertices, and partially for trees with 12 to 16 vertices. With more computational power it would be possible to use our Maple packages and Python code to go further. We also explore the "statistics" of the cardinalities of the third and fourth components of the "Graham sequence" taken over all trees.

Maple packages

TreeLine.txt, A maple package to explore Ron Graham's Tree Line Conjecture
It also needs the data file: TreeLineData.txt .

Sample Input and Output for TreeLine.txt

If you want to see FULL verification of Graham's conjecture up to trees with 10 vertices
the input gives the output

If you want to see PARTIAL verification of Graham's conjecture up to trees with 11 to 15 vertices see this the data file gives the

If you want to see partial verification of Graham's conjecture for trees with vertices from 11 to 16
output

If you want to see the generating function for the third entry of the Graham Line-Graph sequence for all unlabeled trees up to 16 vertices
the input gives the output

If you want to see the generating function for the fourth entry of the Graham Line-Graph sequence for all unlabeled trees up to 13 vertices
the input gives the output