Graham's Tree Reconstruction Conjecture and a Waring-Type Problem on Partitions

Details Graham's Tree Reconstruction Conjecture and a Waring-Type Problem on Partitions Graham's Tree Reconstruction Conjecture and a Waring-Type Problem on Partitions

2011-09-02

arxiv.org/abs/1109.0522v1

Mathematics

Combinatorics

18 pages, 1 figure

Scientific paper

Suppose G is a tree. Graham's "Tree Reconstruction Conjecture" states that G is uniquely determined by the integer sequence |G|, |L(G)|, |L(L(G))|, |L(L(L(G)))|, ..., 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 at least exp(c(log n)^(3/2)). The proof strategy involves constructing a large collection of caterpillar graphs using partitions arising from the Prouhet-Tarry-Escott problem. We identify, but only partially resolve, an interesting question about representations of integers as sums of k-th powers of the parts of integer partitions.

Affiliated with

Also associated with

No associations

Rating

Graham's Tree Reconstruction Conjecture and a Waring-Type Problem on Partitions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graham's Tree Reconstruction Conjecture and a Waring-Type Problem on Partitions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graham's Tree Reconstruction Conjecture and a Waring-Type Problem on Partitions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-688894