The extremal values of the Wiener index of a tree with given degree sequence

• For vertices u and v, dT(u, v) is the number of edges on their unique path, and vertices of degree 1 are leaves.Source: §1 · p. 2
• A tree’s degree sequence lists the degrees of its non-leaf vertices in descending order.Source: §1 · p. 2
• In a rooted tree, a vertex’s height is its distance from the root; adjacent vertices along a root-to-leaf path are parent and child.Source: §1 · p. 2

• The greedy-tree construction starts at a largest-degree root and assigns the largest available degrees successively to vertices as they are labeled.Source: §2 · p. 2
• A greedy tree is characterized by leaves at heights differing by at most one and ordered degrees across levels and successor subtrees.Source: §2 · p. 3
• A greedy caterpillar attaches pendant edges to a path, with its non-leaf degrees arranged in a specified order along the path.Source: §2 · p. 3
• Fixed degree sequences reflect natural valence restrictions in molecular graphs, extending work on trees constrained only by maximal degree.Source: §2 · p. 3
• Given the degree sequence and number of vertices, the greedy tree minimizes the Wiener index and the greedy caterpillar maximizes it.Source: §2 · p. 4
• The paper presents structural lemmas before proving the minimizing result in Section 4 and the maximizing result in Section 5.Source: §2 · p. 4

3 On the structure of an ‘optimal’ tree

• Here, “optimal” means minimizing the Wiener index among trees with the same number of vertices and degree sequence.The path setup labels components to the right and left of a chosen vertex z and groups later components into two tails.Source: §3 · p. 4
• The path-based argument reorders the two tail subtrees when needed, using a swap that does not increase the Wiener index.For paths without z, only distances with exactly one endpoint in the swapped tails need to be considered.Source: §3 · p. 5
• When the stated component-size inequalities hold, an optimal tree can be labeled so that d(xk) ≥ d(yk); transferring branches between xk and yk preserves the degree sequence.If a strict inequality holds in the conditions of Lemmas 3.1–3.2 or Corollary 3.3, the conclusion is forced rather than merely permissible.Source: §3 · p. 6
• In an optimal tree, vertices can be labeled so component sizes alternate in nonincreasing order, with the displayed sequences ending in singleton components; the even-length case has path length 2m.Source: §3 · p. 7
• For an even-length path, the vertex degrees can be ordered nonincreasingly along the path, ending with two vertices of degree 1.The proof obtains adjacent degree comparisons by applying the ordering corollary to successive vertices and component pairs.Source: §3 · p. 8

• The minimum of gT(v) occurs at u1, where both d(u1) and |V(U1)| are maximal on the path; the proof roots the tree at a centroid vertex.Source: §4 · p. 9
• Leaves have heights differing by at most 1, and each vertex’s degree is at least that of any of its successors.Source: §4 · p. 9
• For vertices at different heights, path comparisons establish that the higher vertex has degree at least as large; at equal heights, larger-degree vertices have successors ordered by degree.Source: §4 · p. 9
• The sibling-subtree comparison yields |V(T(x0)/T(x′))| > |V(T(y0)/T(y′))|; for successors x′′, y′′ of the same height, d(x′) ≥ d(y′) and d(x′′) ≥ d(y′′), so (v) of Lemma 2.2 is satisfied.Source: §4 · pp. 9–10
• The optimal tree is the greedy tree.Source: §4 · p. 10

5 On Theorem 2.4

• For the stated even-length case (2m), component sizes follow an alternating order through U_m; the other displayed ordering ends at W_{m−1}.The orderings are |V(U1)| ≤ |V(W1)| ≤ |V(U2)| ≤ ... ≤ |V(Wm−1)| ≤ |V(Um)| and |V(U1)| ≤ |V(W1)| ≤ ... ≤ |V(Um−1)| ≤ |V(Wm−1)|.Source: §5 · p. 10
• The proof examines a longest path and shows that any neighbor of a path vertex lying off the path must be a leaf.It then applies Lemma 5.1 to conclude that the maximizing tree is a greedy caterpillar.Source: §5 · p. 10
• A maximum-Wiener tree with a fixed degree sequence is a greedy caterpillar.The proof shows that every vertex off the longest path is a leaf.Source: §5 · p. 10