Graham's conjecture on tree reconstruction

Importance: Medium ✭✭
Author(s): Graham, Ronald L.
Keywords: reconstruction
Recomm. for undergrads: no
Posted by: mdevos
on: March 18th, 2007

\begin{problem} for every graph $G$, we let $L(G)$ denote the \Def{line graph} of $G$. Given that $G$ is a tree, can we determine it from the integer sequence $|V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots$? \end{problem}

Graph reconstruction is a notoriously difficult subject. This conjecture is an unusual type of reconstruction problem where our class of graphs is very limited - just trees, but we are also given relatively little information - just a sequence of integers.


[GR] C. Godsil and G. Royle, Algebraic graph theory. Graduate Texts in Mathematics, 207. Springer-Verlag, New York, 2001 (page 18).

* indicates original appearance(s) of problem.


Could someone pleas give a proper reference? If I'm not mistaken, the problem is just *mentioned* in G&R, without references (anyway, I didn't find any).

Graph theory

Does for any tree T there exist n that L^n(T) is a regular graph? Or perhaps for all graph?


Consider L^i(T) is a graph with "even triangle"(triangle with even degrees of vertices) subgraph. Edges of even triangle produce new even triangle in L^(i+1)(T). And if there is an odd degree vertex adjacent to parent triangle, there would be another one adjacent to child. So, irregular subgraph remains.


Let G be a star graph of order 5. Then L(G) = C_4. Note that L(C_4) = C_4.

If G is a star graph of

If G is a star graph of order 5, then L(G) = K_5.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.