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
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.
Comments