![](/files/happy5.png)
Graham's conjecture on tree reconstruction
![$ 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.
Graph theory
Does for any tree T there exist n that L^n(T) is a regular graph? Or perhaps for all graph?
No
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.
If G is a star graph of
If G is a star graph of order 5, then L(G) = K_5.
Reference
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).