Journal of Combinatorics

Volume 9 (2018)

Number 3

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

Pages: 469 – 488

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

Authors

Joshua Cooper (Department of Mathematics, University of South Carolina, Columbia, S.C., U.S.A.)

Bill Kay (Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia, U.S.A.)

Anton Swifton (Department of Mathematics, University of South Carolina, Columbia, S.C., U.S.A.)

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.

Received 14 January 2016

Published 18 May 2018