Open Problem Garden - Graham's conjecture on tree reconstruction - Comments

No (re: Graham's conjecture on tree reconstruction)

leshabirukov — Wed, 16 Jan 2013 10:34:25 +0100

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 (re: Graham's conjecture on tree reconstruction)

Anonymous — Tue, 08 Jan 2013 22:36:31 +0100

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

No (re: Graham's conjecture on tree reconstruction)

Anonymous — Thu, 10 Jun 2010 20:21:11 +0200

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

Reference (re: Graham's conjecture on tree reconstruction)

Anonymous — Tue, 14 Apr 2009 02:41:49 +0200

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 (re: Graham's conjecture on tree reconstruction)

Anonymous — Mon, 22 Dec 2008 04:19:54 +0100

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

Graham's conjecture on tree reconstruction

mdevos — Sun, 18 Mar 2007 20:15:00 +0100

Author(s): Graham

Subject: Graph Theory » Basic G.T.

Problem for every graph , we let denote the line graph of . Given that is a tree, can we determine it from the integer sequence ?