Originators: Robert Jamison (presented by Robert Jamison - REGS 2011)
Definitions: For a tree T, let MT denote the average number of nodes in the nonempty subtrees of T. To compare the behavior of MT over trees of different orders, let the density Den(T) of a tree of order n be MT/n.
Background: Not surprisingly, the n-vertex tree minimizing MT is the path Pn, whose density is essentially 1/3. The density of the star is roughly 1/2, but stars are not the trees of highest density. In fact, as n→∞, there are trees whose densities tend to 1.
Conjecture 1: For each n, among n-vertex trees the maximum density is achieved by a caterpillar.
Comments: Conjecture 1 has been verified by Allen Schwenk (private communication) for n up to some value between 20 and 30. In these cases, the caterpillars that maximize the density are not necessarily symmetric!
Given a tree T of order n, let ak denote the number of k node subtrees. Note that a1 = n and a2 = n-1.
Question 2: For an n-vertex tree T, when is it tree that the numbers a2,…,an form a unimodal list? In particular, is it unimodal when T has no vertices of degree 2?
Comments: Andrew Vince and Hua Wang [VW] proved the related result that if T has no nodes of degree 2, then 1/2 ≤ Den(T) ≤ 3/4. The lower bound was conjectured in [J1].
The current proof that the path is the n-vertex tree minimizing MT is surprisingly complicated. The following conjecture, if true, would yield an easy proof:
Conjecture 3: (Jamison [J2]) If uv is an edge in a tree T, and S is obtained from T by contracting uv, then MT ≥ MS + (1/3).
References:
[J1] Robert E. Jamison, On the average number of nodes in a subtree of a tree,
J. Combin. Theory Ser. B 35 (1983), 207-223.
[J2] Robert E. Jamison, Monotonicity of the mean order of subtrees,
J. Combin. Theory, Ser. B 37 (1984), 70-78.
[VW] Andrew Vince and Hua Wang,
The average order of a subtree of a tree.
J. Combin. Theory, Ser. B 100 (2010), 161-170.