{"id":"342ab3c2-066e-4e38-a35d-5327dec6333f","arxiv_id":"1908.09202","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For all n ≥ k ≥ 1, every maximal k-degenerate graph has Wiener index at least n^2 - (k+1)n + k(k+1)/2 and at most sum_{i=0}^{floor((n-2)/k)} C(n-ik,2), and for k-trees with n ≥ 2k+2 the upper bound is attained only by P_n^k.","lead":"Maximal k-degenerate graphs are a broad family that includes trees and Apollonian networks, and this paper pins down the smallest and largest possible Wiener index (sum of all pairwise distances) for every order n and parameter k. It also proves that among k-trees with n at least 2k+2, the only graph reaching the upper bound is the k-th power of a path.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's 'exactly when G=P^k_n' relies on two unproved assertions in the induction; the bounds are sound, but the extremal characterization is not fully established.","rationale":"Read in good faith: The main contributions are the lower bound Theorem 3.1 and upper bound Theorem 3.2. I checked the proofs: Lemma 2.1 gives W(G) >= 2*C(n,2)-|E(G)|, the Lick-White edge bound gives the lower expression, and equality requires diameter at most 2 and maximality; the induction for the upper bound works because every maximal k-degenerate graph has a degree-k vertex whose deletion is again maximal k-degenerate, and Lemma 2.2 bounds the status contribution by the endpoint status in P^k_n. The formula for W(P^k_n) is correct; the displayed grouped sum is slightly terse for small D, but the binomial-sum identity is valid. The genuinely insecure point is Theorem 4.2. Its induction is structurally sound: take a Wiener-maximizing k-tree G; since P^k_n is a k-tree, the maximum equals W(P^k_n); equality forces G-v=P^k_{n-1} and sigma_G(v) at the Lemma 2.2 bound. But the proof does not establish that the only way to get sigma_G(v) at the bound is to root v at the first or last k vertices, nor does it establish the base-case uniqueness. These are not covered by the cited lemmas; they are asserted in one sentence each. The reader identified exactly this point, and I agree. The concern is a proof gap rather than a discovered counterexample; both assertions look plausible and likely fillable. Therefore the appropriate verdict is unchanged: CONDITIONAL, pending proof or independent verification of the two missing assertions.","tokens_in":7588,"tokens_out":24877,"duration_ms":231319,"concrete_test":"Perform exhaustive generation of unlabeled k-trees for k=2,3,4 (using the recursive root-clique definition and nauty canonical labeling) at orders 2k+2 and 2k+3. Check (i) all order-2k+2 k-trees of diameter 3 are isomorphic to P^k_{2k+2}; (ii) for each k-tree G of order 2k+3 with G-v isomorphic to P^k_{2k+2}, adding v to a k-clique Q of P^k_{2k+2} gives |N_G(v,2)|=k only for Q={1,...,k} or {n-k,...,n-1}. If either check fails, Theorem 4.2 is false. If both pass, it corroborates the theorem; a full settlement still requires writing the two missing analytic lemmas: a path-counting proof for |N(Q)\\Q| and a diameter-layer classification for the base case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4, Theorem 4.2. The induction requires two assertions that are stated but not proved. Base case: 'the only such k-tree is P^k_{2k+2}' for order 2k+2 and diameter 3. The preceding sentence about constructed vertices is not a proof, and no classification is given. Inductive step: after assuming G-v = P^k_{n-1}, the proof says 'any other choice for N_G(v) has |N_G(v,2)| > k, so sigma_G(v) is not maximized.' This is the whole content of the uniqueness argument for roots, but no derivation is supplied. The equality statement of Theorem 4.2 depends on both assertions: if a second diameter-3 k-tree of order 2k+2 existed, or if some non-endpoint root in P^k_{n-1} had exactly k second neighbors, the corresponding k-tree would attain W(P^k_n) without being P^k_n. Theorems 3.1 and 3.2 (the sharp bounds) do not depend on these assertions, so the numerical bounds are not threatened. The gap is in the 'characterize all extremal graphs' half, which is a central advertised result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7751,"tokens_out":15646,"duration_ms":145018,"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":[{"comment":"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":"Section 4, Theorem 4.2 (base case)"},{"comment":"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.","section":"Section 4, Theorem 4.2 (inductive step)"}],"minor_comments":[{"comment":"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":"Throughout"},{"comment":"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":"Section 4, first paragraph"},{"comment":"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":"Section 3, Theorem 3.2 proof"},{"comment":"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":"Section 4, Proposition 4.1"},{"comment":"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.","section":"Section 4, Corollary 4.3(3)"}],"recommendation":"major_revision","confidential_remarks":"The paper depends substantially on the authors' own prior work, especially Lemma 2.2 from [4] and structural facts from [1]; this is legitimate but means the novelty is partly conditional on those results. The main issue is the unproved uniqueness assertions in Theorem 4.2; once those are supplied, I would be comfortable with publication. The editor may also wish to confirm the final published status of reference [4]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":8341,"tokens_out":873,"would_cite":true,"duration_ms":9703,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C35","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Wiener index","maximal k-degenerate graph","k-tree","path power","extremal graph","diameter","distance in graphs","k-connected graph"],"falsifier":"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.","tokens_in":7308,"feed_emoji":"📏","tokens_out":13877,"duration_ms":120523,"temperature":0.7,"pith_summary":"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.","feed_headline":"Path powers maximize the Wiener index of k-trees","feed_subtitle":"A sharp two-sided inequality fixes the sum of all pairwise distances for maximal k-degenerate graphs of order n.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines k-degenerate and maximal k-degenerate graphs; supplies the edge bound, the degree-k deletion vertex, and k-connectivity used in both main theorems.","marker":"[12]"},{"why":"Gives the structural characterization of maximal k-degenerate graphs by edge count and identifies chordal maximal k-degenerate graphs as k-trees.","marker":"[1]"},{"why":"Supplies the inequality W(G) ≥ 2\\binom{n}{2} - |E(G)| with equality iff diameter is at most 2, used for the lower bound.","marker":"[2]"},{"why":"Supplies the distance-layer formula for W(G) and the inequality W(G) ≤ W(G-v)+σ_G(v), the engine of the upper-bound induction.","marker":"[9]"},{"why":"The combined citation for Lemma 2.2: it provides the upper bound on vertex status in k-connected graphs and the equality conditions on distance layers that drive the upper-bound and uniqueness arguments.","marker":"[4, 10]"},{"why":"Defines k-trees recursively, which justifies the induction and the role of path powers as extremal k-trees.","marker":"[3]"}],"fun_headline_variants":["Sharp Wiener bounds for maximal k-degenerate graphs","Two-sided Wiener bound for maximal k-degenerate graphs","Path powers are the Wiener-maximizing k-trees","Exact Wiener index range for maximal k-degenerate graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sharp Wiener bounds for maximal k-degenerate graphs","Two-sided Wiener bound for maximal k-degenerate graphs","Path powers are the Wiener-maximizing k-trees","Exact Wiener index range for maximal k-degenerate graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001231,"raw_usage":{"total_tokens":5018,"prompt_tokens":869,"completion_tokens":4149,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":4085}},"tokens_in":485,"tokens_out":4149,"duration_ms":28657,"temperature":1.0,"reasoning_tokens":4085,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:19:22.586112+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines k-degenerate and maximal k-degenerate graphs; supplies the edge bound, the degree-k deletion vertex, and k-connectivity used in both main theorems."},{"cited_title":"Bickle, Structural results on maximal k-degenerate graphs, Discuss","cited_arxiv_id":null,"evidence_quote":"Gives the structural characterization of maximal k-degenerate graphs by edge count and identifies chordal maximal k-degenerate graphs as k-trees."},{"cited_title":"Buckley and F","cited_arxiv_id":null,"evidence_quote":"Supplies the inequality W(G) ≥ 2\\binom{n}{2} - |E(G)| with equality iff diameter is at most 2, used for the lower bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the distance-layer formula for W(G) and the inequality W(G) ≤ W(G-v)+σ_G(v), the engine of the upper-bound induction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines k-trees recursively, which justifies the induction and the role of path powers as extremal k-trees."}],"review_version":1}