Suppose that G is a tree

Definitions and mathematical statement

For a finite simple graph $G$, its line graph $L(G)$ has vertex set $E(G)$, with two distinct vertices adjacent precisely when the corresponding edges of $G$ share an endpoint. Define iterates by $L^0(G)=G$ and $L^{j+1}(G)=L(L^j(G))$ for integers $j\ge0$. An empty line graph is allowed, so iteration continues after all vertices have disappeared.

For a finite tree $T$, write \[ a_j(T)=|V(L^j(T))|\qquad(j\ge0). \] Graham's reconstruction question asks whether this complete sequence determines $T$ up to graph isomorphism. In quantified form, must two finite trees $T,T'$ satisfying \[ a_j(T)=a_j(T')\quad\text{for all integers }j\ge0 \] be isomorphic?

Only the orders of the iterated line graphs are supplied, not the iterated graphs themselves, their degree sequences, or embeddings. The first entries give the numbers of vertices and edges of the tree, but the problem uses the entire infinite sequence. Agreement through an arbitrary fixed finite number of iterates is not itself a counterexample. Conversely, nonisomorphic trees with all these orders equal would disprove reconstruction even if their line graphs differ as graphs at early stages.

Short English statement

Does the sequence of vertex counts of all iterated line graphs determine a finite tree up to isomorphism?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100022 (AMR-030-0022), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Graphs, Hypergraphs, Set Systems, Designs, source-order bullet 22. Original source indexed by AMR-030-0022. https://people.math.sc.edu/cooper/combprob.html.
• S3 Cooper, research paper on reconstruction from iterated line-graph orders. https://people.math.sc.edu/cooper/treerecon.pdf.