A383998 Number of distinct truncated Graham sequences (as in Graham's Tree Reconstruction Conjecture) of length 4 on trees of order n.

1, 1, 1, 2, 3, 6, 11, 20, 37, 68, 114, 188, 300, 462, 702, 1041

Offset: 1

Author

Kaylee Weatherspoon, May 22 2025

Keywords

• nonn
• more

Comments

For small trees, the sequence |G|, |L(G)|, |L(L(G))|, |L(L(L(G)))| is sufficient to determine the tree, so this sequence has the same first few terms as A000055.

Examples

			For n=8, there are 23 trees but only 20 distinct truncated Graham sequences of length 4.
There are two pairs of trees on 8 vertices which have the same length-4 sequence [|G|, |L(G)|, |L(L(G))|, |L(L(L(G)))|], namely the sequence [8,7,7,9] which comes from both the (unlabeled versions of) {{1, 2}, {2, 3}, {3, 7}, {4, 5}, {5, 6}, {6, 7}, {7, 8}} and {{1, 2}, {2, 3}, {3, 8}, {4, 7}, {5, 6}, {6, 7}, {7, 8}}.
But for sequences of length 5 there are different sequences, namely
[8, 7, 7, 9, 18] and [8, 7, 7, 9, 17]: the sequence [8,7,9,17] comes from both {{1, 3}, {2, 3}, {3, 7}, {4, 6}, {5, 6}, {6, 7}, {7, 8}} and {{1, 2}, {2, 3}, {3, 8}, {4, 7}, {5, 7}, {6, 7}, {7, 8}}
So Graham's conjecture is confirmed for trees with 8 vertices, but requires using sequences of length up to 5.
		

Links

• Kaylee Weatherspoon, Maple program.
• Kaylee Weatherspoon and Doron Zeilberger, An Experimental Note on Graham’s Tree Reconstruction Conjecture, Rutgers Univ. (2025). See p. 3.

Crossrefs

Cf. A000055.

Extensions

Corrected by Doron Zeilberger, Aug 12 2025.