![](/files/happy5.png)
Problem for every graph
, we let
denote the line graph of
. Given that
is a tree, can we determine it from the integer sequence
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ L(G) $](/files/tex/76f6ee75811ed6d89f7e99f8aa7a505f462c30b2.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ |V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots $](/files/tex/b93a7a2773f22770891c213297401ce7189f4fa2.png)
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.
Bibliography
[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.