Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 3

### Graham’s Tree Reconstruction Conjecture and a Waring-Type problem on partitions

Pages: 469 – 488

DOI: http://dx.doi.org/10.4310/JOC.2018.v9.n3.a3

#### Authors

#### Abstract

Suppose $G$ is a tree. Graham’s “Tree Reconstruction Conjecture” states that $G$ is uniquely determined by the integer sequence $\lvert G \rvert, \lvert L(G) \rvert, \lvert L(L(G)) \rvert, \lvert L(L(L(G))) \rvert, \dotsc ,$ where $L(H)$ denotes the line graph of the graph $H$. Little is known about this question apart from a few simple observations. We show that the number of trees on n vertices which can be distinguished by their associated integer sequences is $e^{\Omega ({(\log n)}^{3/2})}$. The proof strategy involves constructing a large collection of caterpillar graphs using partitions arising from the Prouhet–Tarry–Escott problem.

This work was funded in part by NSF grant DMS-1001370.

Received 14 January 2016