Wiener indices of maximal $k$-degenerate graphs

Allan Bickle; Zhongyuan Che

REVIEW 2 major objections 5 minor 15 references

Wiener indices of maximal $k$-degenerate graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves sharp lower and upper bounds on the Wiener index of maximal k-degenerate graphs, and shows that among k-trees of order at least 2k+2 the k-th power of a path is the unique extremal graph for the upper bound.

desk verdict Sharp Wiener bounds for maximal k-degenerate graphs are solid and new in general form, but the k-tree extremal characterization in Theorem 4.2 rests on two unproved assertions and needs a real fix. read the letter →

arxiv 1908.09202 v1 pith:6SCZTPOY submitted 2019-08-24 math.CO

Allan Bickle , Zhongyuan Che This is my paper · ORCID

classification math.CO MSC 05C1205C3505C75

keywords Wienerindexmaximalk-degenerategraphk-treepathpowerextremaldiameterdistanceingraphsk-connected

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how large or small the sum of all pairwise distances (the Wiener index) can be among maximal k-degenerate graphs: graphs whose every induced subgraph has a vertex of degree at most k, and to which no edge can be added without destroying that condition. It proves that for order n ≥ k the Wiener index is always at least $n^{2}$ − (k+1)n + \binom{k+1}{2}, with equality exactly for maximal k-degenerate graphs of diameter at most 2, and always at most W(P^k_n) = \sum_{i=0}^{\lfloor (n-2)/k\rfloor} \binom{n-ik}{2}, the value for the k-th power of a path. For the chordal subclass called k-trees, and for n ≥ 2k+2, the path power is the unique graph attaining the upper bound. These bounds unify earlier sharp results for trees (k=1), maximal outerplanar graphs (k=2), and Apollonian networks (k=3), and yield a closed formula for the extremal value.

What carries the argument

The load-bearing object is the k-th power of a path, P^k_n, whose vertices are those of a path with edges between vertices at path distance at most k; it is a k-tree whose distance layers from either end each contain exactly k vertices. The proof of the upper bound runs through the vertex status σ_G(v), the sum of distances from v to all other vertices. Lemma 2.2 bounds σ_G(v) in any k-connected graph by (\lfloor (n-2)/k\rfloor+1)(n-1 - \frac{k}{2}\lfloor (n-2)/k\rfloor), with equality only when the eccentricity is maximal and every distance layer N_G(v,i) has exactly k vertices. Induction deletes a degree-k vertex v, applies W(G) ≤ W(G-v)+σ_G(v), and matches each term against the corresponding term for P^k_n. The lower bound uses the edge bound |E(G)| ≤ kn - \binom{k+1}{2} together with the identity W(G) ≥ 2\binom{n}{2} - |E(G)|, whose equality case is diameter at most 2.

What would settle it

Enumerate all k-trees of order 2k+2 and, for small k, all k-trees of order 2k+3 built from P^k_{n-1} by attaching a new vertex to each k-clique, and compare their Wiener indices with $W(P^k_n)$; any graph other than P^k_n with the same value would refute Theorem 4.2, and checking the two asserted properties at these smallest orders would settle the gap directly.

Watch

Extended reading notes

Core claim

The paper's central discovery is a pair of sharp inequalities. Theorem 3.1 states that every k-degenerate graph of order n ≥ k has W(G) ≥ $n^{2}$ − (k+1)n + \binom{k+1}{2}, and equality holds exactly when G is maximal k-degenerate with diameter at most 2; examples attaining it include K_k + \overline{K}_{n-k} for n ≥ k+2. Theorem 3.2 states that every maximal k-degenerate graph of order n ≥ 2 satisfies W(G) ≤ W(P^k_n) = \sum_{i=0}^{\lfloor (n-2)/k\rfloor}\binom{n-ik}{2}, with P^k_n itself extremal. Theorem 4.2 sharpens the upper bound for k-trees: for order n ≥ 2k+2, equality holds exactly for G = P^k_n. For orders k ≤ n ≤ 2k+1 the lower and upper bounds coincide, so every maximal k-degenerate graph of that order has the same Wiener index.

Load-bearing premise

The uniqueness of P^k_n among extremal k-trees rests on two assertions stated in the induction but not proved there: that P^k_{2k+2} is the only k-tree of order 2k+2 with diameter 3, and that in P^k_{n-1} a new vertex attached to any k vertices other than the first or last k creates more than k vertices at distance two; if either assertion fails, another k-tree could attain the upper bound.

Editorial extensions

If this is right

For every maximal k-degenerate graph of order n, the Wiener index is trapped between two explicit polynomial values, so the average pairwise distance is determined up to an explicit gap that depends only on n and k.
If k ≤ n ≤ 2k+1, every maximal k-degenerate graph has Wiener index exactly \binom{n}{2} + \binom{n-k}{2}; no extremal search is needed in this range.
The formula W(P^k_n)=\sum_{i=0}^{\lfloor (n-2)/k\rfloor}\binom{n-ik}{2} has the closed form of Corollary 3.3, giving the extremal values for all k; in particular the k=1 tree bound n^3/6 - n/6 and the k=3 Apollonian bound \lfloor (n^3+3n^2)/18 \rfloor are special cases.
For k-trees of order at least 2k+2, equality in the upper bound forces the graph to be the path power, so P^k_n is the unique distance-maximizing k-tree in that range.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof suggests that the uniqueness result could be completed by verifying the two stated induction facts; the same layer-counting argument would then carry through for all n.
The lower-bound equality class is much larger than the explicit example K_k + \overline{K}_{n-k}; Proposition 4.1 shows that even among 2-trees it includes every graph T + K_1 with T a tree, so a general classification is likely to be as hard as classifying diameter-2 graphs.
For orders k+3 ≤ n ≤ 2k+1 the paper shows the upper-bound extremal graph is not unique, and the k=3 examples point to a finite family built from trees and small cliques; a complete list for every k seems plausible.
The status-bound machinery, which is stated for arbitrary k-connected graphs, may transfer to other k-connected families once an extremal graph with the same layered-distance structure is found.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The genuinely useful part of this paper is the pair of sharp bounds in Theorems 3.1 and 3.2. The lower bound is a quick consequence of known edge counts plus the diameter lemma, but the upper bound for all maximal k-degenerate graphs is a real generalization of the tree and Apollonian cases, and the inductive proof using the Che-Collins status bound is clean. The closed form in Corollary 3.3 checks out. If you work on extremal graph theory or chemical graph theory, these bounds are worth having.

The weak spot is exactly where the stress-test note lands: Theorem 4.2 claims that among k-trees of order n >= 2k+2, the only graph attaining the upper bound is P^k_n. The induction needs two things that are asserted but not proved. First, the base case says the only k-tree of order 2k+2 with diameter 3 is P^k_{2k+2}; the text essentially says this follows from the recursive definition, but no argument is given. Second, after assuming G-v = P^k_{n-1}, the proof says any root clique other than the first or last k vertices gives |N_G(v,2)| > k, so sigma_G(v) is not maximized. That is the entire content of the uniqueness step, and it is stated without derivation. If either assertion fails, a different k-tree could attain the bound. The sharp bounds in Theorems 3.1 and 3.2 do not depend on this, so the numerical results are safe, but the advertised extremal characterization is not fully established.

The rest is fine. The reliance on Lemma 2.2 from Che and Collins and on Bickle's structural results is legitimate; those are prior results with independent proofs, not circular. The k=1 and k=3 special cases line up with known results, and the paper is honest about which extremal graphs are known for small orders.

Who is this for? Someone who wants the general Wiener bounds for maximal k-degenerate graphs can use this paper now. Someone who wants to cite the uniqueness of P^k_n as an extremal graph should wait until the gap in Theorem 4.2 is repaired. I would send it to a serious referee: the main bounds are valuable, and the gap is localized and likely fixable, but the proof of Theorem 4.2 as written is incomplete.

Referee Report

2 major / 5 minor

Summary. The manuscript studies the Wiener index of maximal k-degenerate graphs. Theorem 3.1 gives the sharp lower bound W(G) ≥ n² − (k+1)n + binom(k+1,2), with equality exactly for maximal k-degenerate graphs of diameter at most 2. Theorem 3.2 gives the sharp upper bound W(G) ≤ W(P^k_n), where P^k_n is the k-th power of a path, together with the summation formula W(P^k_n)=Σ_{i=0}^{⌊(n−2)/k⌋} binom(n−ik,2); Corollary 3.3 provides a closed form. The paper then claims in Theorem 4.2 that for k-trees of order n ≥ 2k+2, equality in the upper bound holds exactly for G=P^k_n, and it characterizes 2-trees of diameter 2 in Proposition 4.1. Corollary 4.3 specializes the bounds to k=1,2,3, including Apollonian networks.

Significance. The lower and upper bounds are attractive and, if correct, unify known results for trees, maximal outerplanar graphs, and Apollonian networks. The derivations of Theorems 3.1 and 3.2 are sound: Theorem 3.1 uses only the standard edge bound for k-degenerate graphs and Lemma 2.1(i), and Theorem 3.2 is a valid induction built on Lemma 2.2. The closed form in Corollary 3.3 is algebraically correct. I see no circular dependence: Lemma 2.2 is a prior result cited as a black box, and W(P^k_n) is computed directly rather than fitted to the claimed bounds. The advertised extremal characterization in Theorem 4.2, however, is not established by the current proof because two uniqueness assertions are stated without proof. These gaps concern only the equality part of Theorem 4.2; the numerical bounds in Theorems 3.1 and 3.2 are not affected.

major comments (2)

[Section 4, Theorem 4.2 (base case)] The base case of the induction asserts that P^k_{2k+2} is the only k-tree of order 2k+2 with diameter 3. This is a classification claim, but no proof is given. The sentence beginning "By the recursive definition of a k-tree..." does not establish uniqueness; the statement about the i-th added vertex is not developed into an argument that every such k-tree must be the path power. If a second diameter-3 k-tree of order 2k+2 exists, the induction base fails and the "exactly when G=P^k_n" conclusion of Theorem 4.2 would be false as stated. Please supply a proof, for example by showing that in a k-tree of minimum order and diameter 3 the root cliques used in the construction must form a chain, forcing P^k_{2k+2}.
[Section 4, Theorem 4.2 (inductive step)] The inductive step assumes G-v=P^k_{n-1} and then states that "any other choice for N_G(v)" with n ≥ 2k+3 has |N_G(v,2)| > k, so σ_G(v) is not maximized. This is the entire content of the argument that the root of v must be the first or last k vertices of P^k_{n-1}, and it is not proved. Lemma 2.2 requires equality in condition (ii), namely |N_G(v,i)| = k for all i up to floor((n-2)/k); the assertion about |N_G(v,2)| is precisely what rules out interior roots. Without a derivation, the induction does not establish that P^k_n is the only extremal k-tree. A short counting argument for the vertices at distance two from v would close the gap.

minor comments (5)

[Throughout] There are several typos: "charcterize" in the abstract, "the the summation" in the Introduction, and "compliment" for "complement" in Section 2; these should be corrected.
[Section 4, first paragraph] The sentence "Any maximal k-degenerate graph of diameter 1 is Kn, 2≤n≤k+1" omits the case n=1,k=1; either include it or add a parenthetical for that trivial case.
[Section 3, Theorem 3.2 proof] The assertion that for 2≤n≤k+2, P^k_n is the only maximal k-degenerate graph is stated without proof; a one-sentence edge-count argument would suffice.
[Section 4, Proposition 4.1] The proof of the characterization of 2-trees of diameter 2 uses phrases such as "It is easily seen" and "It is easy to check" without giving the case details; since this is a classification result, please expand the verification or provide a more formal case enumeration.
[Section 4, Corollary 4.3(3)] The claim that there are exactly four additional 3-trees of order 7 attaining the upper bound is asserted as "easily checked" with no verification; please include the check or a reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the Wiener-index bounds are derived from prior independent lemmas and direct computation; the unproved uniqueness assertions in Theorem 4.2 are proof gaps, not circular reasoning.

full rationale

The derivation of the two sharp bounds is not circular. Theorem 3.1 combines Lemma 2.1(i) (W >= 2*C(n,2) - |E|) with the standard edge bound for k-degenerate graphs and the maximality characterization; none of these ingredients states the Wiener bound being proved. Theorem 3.2 is an induction using Lemma 2.2 (a k-connected status bound from Che-Collins and Favaron-Kouider-Maheo) and computes W(P^k_n) directly by distance-layer summation; the target formula is not an input to Lemma 2.2. The self-citations [1] and [4] are load-bearing in the proofs but are independent prior results with external co-authors or external parallel sources, and they do not assume the present theorem. The extremal characterization in Theorem 4.2 does contain two assertions (the base-case uniqueness of P^k_{2k+2} and the claim that any other root clique gives |N_G(v,2)| > k) that are stated without proof; this is an omitted-proof gap that affects the completeness of the equality characterization, not a circular reduction, because the assertions are not restatements of the desired conclusion. Therefore no circularity is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No empirical parameters or newly invented entities appear. All constants are algebraic and derive from graph-theoretic lemmas. The proof relies on standard prior results, including one self-cited status bound and structural facts from the same author group. No free parameters are fitted to data.

assumptions (4)

standard math Lemma 2.1: For connected G, W(G) ≥ n(n-1) - |E(G)| with equality iff diam(G) ≤ 2, and W(G) ≤ W(G-v) + σ_G(v).
Cited from [2,9]; used to derive the lower bound and the induction step for the upper bound.
standard math Lemma 2.2: For a k-connected graph of order n, σ_G(x) ≤ (floor((n-2)/k)+1)(n-1 - (k/2)floor((n-2)/k)), with equality conditions on layer sizes.
Cited from [4,10]; this is the key status bound used to bound σ_G(v) in Theorem 3.2. One source is co-authored by Che.
domain assumption Structural facts on maximal k-degenerate graphs: they have exactly kn - C(k+1,2) edges, are k-connected when n ≥ k+1, and contain a degree-k vertex whose deletion leaves a maximal k-degenerate graph.
Cited from [12] and [1]; these facts set up the induction and the edge-count lower bound. Reference [1] is by Bickle.
standard math Chordal maximal k-degenerate graphs of order n ≥ k are exactly k-trees.
Cited to [1]; this identifies the class in which the extremal graph characterization is stated.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Wiener indices of maximal $k$-degenerate graphs." pith.science (2026). https://pith.science/paper/6SCZTPOY

@misc{pith2026190809202,
  author       = {Pith},
  title        = {Pith review of: Wiener indices of maximal $k$-degenerate graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6SCZTPOY}},
  note         = {Machine review of arXiv:1908.09202}
}

abstract

A graph is maximal $k$-degenerate if each induced subgraph has a vertex of degree at most $k$ and adding any new edge to the graph violates this condition. In this paper, we provide sharp lower and upper bounds on Wiener indices of maximal $k$-degenerate graphs of order $n \ge k \ge 1$. A graph is chordal if every induced cycle in the graph is a triangle and chordal maximal $k$-degenerate graphs of order $n \ge k$ are $k$-trees. For $k$-trees of order $n \ge 2k+2$, we characterize all extremal graphs for the upper bound.

Figures

Figures reproduced from arXiv: 1908.09202 by the authors.

**Figure 1.** Examples of 2-trees. Proposition 4.1 Let G be a 2-tree with diameter 2. Then G is isomorphic to T + K1 for a tree T, or a graph formed by adding any number of vertices adjacent to pairs of vertices of K3. In particular, the maximal outerplanar graphs with diameter 2 are fans Pn−1 + K1 and the triangular grid T r2. See [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

**Figure 2.** Examples of 3-trees of order 7. References [1] A. Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 (2012), 659–676. [2] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Redwood, 1990. [3] L. W. Beineke and R. E. Pippert, The number of labeled k-dimensional trees, J. Combinatorial Theory 6 (1969), 200–205. [4] Z. Che and K. L. Collins, An upper bound on the Wiene… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Bickle, Structural results on maximal k-degenerate graphs, Discuss

A. Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 (2012), 659–676

work page 2012
[2]

Buckley and F

F. Buckley and F. Harary, Distance in Graphs , Addison-Wesley, Redwood, 1990

work page 1990
[3]

L. W. Beineke and R. E. Pippert, The number of labeled k-dimensional trees, J. Com- binatorial Theory 6 (1969), 200–205

work page 1969
[4]

An upper bound on the Wiener Index of a k-connected graph

Z. Che and K. L. Collins, An upper bound on the Wiener index of a k-connected graph, arXiv:1811.02664 [math.CO]

work page Pith review arXiv
[5]

Che and K

Z. Che and K. L. Collins, An upper bound on Wiener indices of maximal planar graphs, Discrete Appl. Math. 258 (2019), 76–86

work page 2019
[6]

Wiener Index and Remoteness in Triangulations and Quadrangulations

E. Czabarka, P. Dankelmann, T. Olsen and L. A. Sz´ ekely, Wiener index and remoteness in triangulations and quadrangulations, arXiv:1905.06753v1 [math.CO ]

work page Pith review arXiv 1905
[7]

Chartrand and F

G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. H. Poincar Sect. B (N.S.) 3 (1967), 433–438

work page 1967
[8]

J. K. Doyle and J. E. Graver, Mean distance in a graph, Discrete Math. 7 (1977), 147–154

work page 1977

Show all 15 references

[9]

R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in gra phs, Czech. Math. J. 26 (1976), 283–296. 8

1976
[10]

Favaron, M

O. Favaron, M. Kouider and M. Mah´ eo, Edge-vulnerability and mean distance, Networks 19 (1989), 493–504

1989
[11]

Harary, Status and contrastatus, Sociometry 22 (1959), 23–43

F. Harary, Status and contrastatus, Sociometry 22 (1959), 23–43

1959
[12]

D. R. Lick and A. T. White, k-degenerate graphs, Canadian J. Math. 22 (1970), 1082– 1096

1970
[13]

Plesn ´ ık, On the sum of all distances in a graph or digraph, J

J. Plesn ´ ık, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984), 1–21

1984
[14]

H. P. Patil, On the structure of k-trees, J. Combin. Inform. System Sci. 11 (1986), 57–64

1986
[15]

Wiener, Structural determination of paraﬃn boiling points, J

H. Wiener, Structural determination of paraﬃn boiling points, J. Am. Chem. Soc. 69 (1947), 17–20. 9

1947

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Bickle, Structural results on maximal k-degenerate graphs, Discuss

A. Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 (2012), 659–676

work page 2012

[2] [2]

Buckley and F

F. Buckley and F. Harary, Distance in Graphs , Addison-Wesley, Redwood, 1990

work page 1990

[3] [3]

L. W. Beineke and R. E. Pippert, The number of labeled k-dimensional trees, J. Com- binatorial Theory 6 (1969), 200–205

work page 1969

[4] [4]

An upper bound on the Wiener Index of a k-connected graph

Z. Che and K. L. Collins, An upper bound on the Wiener index of a k-connected graph, arXiv:1811.02664 [math.CO]

work page Pith review arXiv

[5] [5]

Che and K

Z. Che and K. L. Collins, An upper bound on Wiener indices of maximal planar graphs, Discrete Appl. Math. 258 (2019), 76–86

work page 2019

[6] [6]

Wiener Index and Remoteness in Triangulations and Quadrangulations

E. Czabarka, P. Dankelmann, T. Olsen and L. A. Sz´ ekely, Wiener index and remoteness in triangulations and quadrangulations, arXiv:1905.06753v1 [math.CO ]

work page Pith review arXiv 1905

[7] [7]

Chartrand and F

G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. H. Poincar Sect. B (N.S.) 3 (1967), 433–438

work page 1967

[8] [8]

J. K. Doyle and J. E. Graver, Mean distance in a graph, Discrete Math. 7 (1977), 147–154

work page 1977