{"id":"fa610997-7273-47c5-8e29-c684f6f8cb10","arxiv_id":"2411.13439","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For four graph classes, a single extremal graph simultaneously maximizes every increasing distance-based index and minimizes every decreasing one.","lead":"A graph's distance sequence, the sorted list of all pairwise distances, is used to prove sharp extremal bounds for a whole family of distance-based indices, including the Harary and hyper-Wiener indices. This resolves an open problem on the minimum Harary index of graphs with fixed order and size, and gives new extremal graphs for several graph families.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 hinges entirely on Lemma 2, imported without proof from [11]; if that distance-sequence bound is false or unproved, the Harary-index resolution collapses.","rationale":"I read the full text in good faith. The framework is elegant: once the distance sequence is maximal, all monotone indices are bounded. The new proofs for maximal k-degenerate graphs and odd trees are internally consistent; I checked the monotonicity of the concatenation operation, the sphere-size argument for k-connected graphs, and the parity argument in Lemma 6. The only place where the argument relies on an unverified external result is Lemmas 2 and 3. Because these are cited as established theorems, this is not an internal inconsistency, but it is the point of highest correctness risk. The reader's verdict of CONDITIONAL is appropriate: the paper should be accepted after confirming the imported lemmas and correcting the Theorem 2(b) inequality. No change from the reader's verdict is needed.","tokens_in":9831,"tokens_out":18431,"duration_ms":195722,"concrete_test":"Obtain [11] and verify that it proves, for every connected graph G of order n and size m, the componentwise distance-sequence bound D(G) ≤ D(PK_{n,m}), and similarly D(G) ≤ D(C_n^{κ/2}) for even κ; if the paper only proves maximality of the Wiener sum, then Theorems 1–2 lack proof. As a cross-check, exhaustively enumerate connected graphs on n ≤ 8 vertices and compare their sorted distance sequences with those of PK_{n,m} for all admissible m.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is a corollary: by Proposition 1, I(G) ≤ I(PK_{n,m}) follows from D(G) ≤ D(PK_{n,m}), and Lemma 2 supplies exactly that bound. Lemma 2 is not proved in this paper and is imported from [11], whose stated topic is strong products rather than path-complete graphs. The text does not reproduce the proof or state the precise conditions under which [11] establishes componentwise maximality of the distance sequence of PK_{n,m}; it may only prove Wiener-index maximality. Similarly, Lemma 3 supplies the whole of Theorem 2 for even connectivity. The remaining proofs (Lemmas 1, 5, 6) are self-contained and appear sound, so the load-bearing external input is precisely these two lemmas. The apparent reversal of the inequality in Theorem 2(b) is a typo, not a structural flaw: for an increasing index, D(G) ≤ D(C_n) gives I(G) ≤ I(C_n), not ≥. No machine-checked verification of Lemmas 2–3 is provided.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a unified method for bounding distance-based topological indices by comparing distance sequences. It shows that if a graph class has a member G* with componentwise maximal distance sequence, then every nondecreasing distance-based index is maximized by G*, and every nonincreasing one is minimized. The paper identifies such extremal graphs for four classes: the path-complete graph for connected graphs of given order and size (Theorem 1), powers of cycles for even-vertex-connectivity (Theorem 2), powers of paths for maximal k-degenerate graphs and k-trees (Theorem 3 and Corollary 1), and a particular tree T_n for odd trees (Theorem 4). Applications include a sharp lower bound on the Harary index among graphs of given order and size, which resolves an open problem from Xu, Das, and Trinajstić's monograph, and sharp upper bounds on the hyper-Wiener and multiplicative Wiener indices. Lemmas 5 and 6 are proved in the paper; Lemmas 2 and 3 are cited from the author's earlier paper [11].","tokens_in":10028,"tokens_out":26063,"duration_ms":220235,"significance":"The distance-sequence framework is a clean and productive idea: one extremal distance-sequence result yields bounds for an entire family of indices (Wiener, Harary, hyper-Wiener, multiplicative Wiener, variable Wiener, etc.) simultaneously. The resolution of the Harary-index open problem is a concrete contribution, and the results for maximal outerplanar graphs, Apollonian networks, and odd trees extend the literature in classes where only Wiener-index results were known. The in-paper proofs (Lemmas 5 and 6) are elementary and appear sound. The principal risks are the two imported lemmas and a false inequality in Theorem 2(b); both are local and repairable, so the paper is likely suitable for publication after revision.","major_comments":[{"comment":"Theorem 1 is a direct corollary of Lemma 2, but Lemma 2 is imported from [11] without proof or a verbatim statement of the result in [11]. Componentwise maximality of D(PK_{n,m}) is strictly stronger than Wiener-index maximality (the sum of the entries), so a proof that PK_{n,m} maximizes the Wiener index alone would not suffice. Since [11] is about strong products and the current paper does not reproduce the argument, the central claim resolving the Harary-index problem cannot be verified from the submitted text. The author should include a proof of Lemma 2 or quote the exact theorem from [11] with all hypotheses.","section":"Section 4, Lemma 2 and Theorem 1"},{"comment":"Theorem 2 depends entirely on Lemma 3, also cited from [11] without proof. The same request applies: either reproduce the proof or state the precise theorem from [11] that establishes componentwise maximality of D(C_n^{κ/2}) among κ-connected graphs. This is load-bearing for the Harary and hyper-Wiener bounds for even connectivity.","section":"Section 5, Lemma 3 and Theorem 2"},{"comment":"The inequality as printed is false. For an increasing index I, Lemma 3 and Proposition 1 give I(G) ≤ I(C_n^{κ/2}), not ≥. For instance, the Wiener index is increasing, and among 2-connected graphs on four vertices, W(K_4)=6 < W(C_4)=8. The inequality should read ≤, and the equality statement 'iff G is a cycle' is then consistent for strictly increasing indices.","section":"Section 5, Theorem 2(b)"}],"minor_comments":[{"comment":"Both parts of Corollary 1 are labelled (a); the second should be (b).","section":"Section 6, Corollary 1"},{"comment":"The phrase 'minimises every nondecreasing' should be 'minimises every nonincreasing'.","section":"Section 6, after Theorem 3"},{"comment":"The symbol T' is used for both T−{v1,v2} and T−v2; please clarify, and in inequality (6) the sequence should be D_{T−v2}(v1), not D_{T'}(v1) as printed.","section":"Section 7, Lemma 6 proof"},{"comment":"In the definition of the hyper-Wiener index, the term d_G(u,) should be d_G(u,v).","section":"Introduction"},{"comment":"The phrase 'if an only if' should be 'if and only if'.","section":"Section 3, Lemma 1"},{"comment":"Please clarify whether 'increasing' is meant strictly; the equality conditions in Proposition 1(b) and Theorem 2(b) depend on strict monotonicity.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The two external lemmas are from the author's own earlier paper [11]; if possible, the editor should verify that [11] indeed contains the componentwise distance-sequence results cited, since the current manuscript does not reproduce them. The reversal in Theorem 2(b) is clearly a typographical error rather than a conceptual flaw. I see no grounds for rejection; the main request is self-containment of the central lemmas."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does two useful things. First, it formalizes a simple and transferable idea: if you know a graph maximizes the distance sequence (componentwise) in a class, then every nondecreasing distance-based index is maximized by that same graph. Proposition 1 plus the path-complete graph's distance-sequence maximality from Soltés/Casablanca–Dankelmann gives an immediate sharp upper bound on the hyper-Wiener index and lower bound on the Harary index for fixed order and size, resolving an explicit open problem in Xu–Das–Trinajstić. That is a real result, even if the derivation is short. Second, the paper extends the trick to new classes with self-contained proofs: maximal k-degenerate graphs (Lemma 5) and odd trees (Lemma 6). The proofs of Lemmas 5 and 6 are structurally sound; I checked the induction steps and the sequence bounds. The fact that the same extremal graph works for all monotone indices, not just Wiener, is a genuine consolidation.\n\nThe soft spots are minor and mostly editorial. Theorem 2(b) states the wrong direction: for κ=2 and an increasing index, the inequality should be I(G) ≤ I(C_n), not ≥. As written it contradicts Theorem 2(a). It is almost certainly a typo, but it needs fixing. Corollary 1 has a duplicated label: the second part should be (b), not (a). Lemma 6's proof has a small garbled phrase (\"the neighbour w of v in T′\") that should read \"of v1 in T′.\" None of these affect the main arguments.\n\nThe more substantive concern is the reliance on Lemmas 2 and 3, both imported without proof from [11]. The central Theorem 1 is just Proposition 1 plus Lemma 2, so the paper's headline result inherits all of its weight from a cited lemma. That is normal mathematical practice, but I would want a referee to verify that [11] indeed proves componentwise distance-sequence maximality of PK_{n,m} and C_n^{κ/2}, and not merely Wiener maximality. The stress-test note is right to flag this. It is not a reason to reject; it is a reason to have a careful referee check the cited lemmas.\n\nWho is this for? People working in chemical graph theory and distance-based indices will get immediate use from the Harary and hyper-Wiener bounds. The framework is simple enough to be taught. I would send it to a serious referee. After fixing the typo, the duplication, and verifying the two imported lemmas, I would accept it.\n\nRecommendation: send to peer review with a referee who can check [11].","headline":"A clean distance-sequence framework that gives sharp Harary/hyper-Wiener bounds, but the load-bearing lemmas are imported from earlier work and one theorem has a sign typo.","tokens_in":10557,"tokens_out":2452,"would_cite":true,"duration_ms":25208,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C35","05C40","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Distance-sequence maximality makes one graph extremal for every monotone Wiener-type index and resolves the Harary-index open problem.","keywords":["generalised Wiener index","Harary index","hyper-Wiener index","Wiener index","multiplicative Wiener index","distance sequence","extremal graphs","path-complete graph"],"falsifier":"Enumerate all connected graphs with n vertices and m edges for n up to 7 and compare, entry by entry, their sorted distance lists with the distance list of the path-complete graph; finding any graph whose list is larger in some coordinate would disprove Theorem 1. The same exhaustive check against the relevant power of the cycle for 2-connected and 4-connected graphs would test the even-connectivity theorem.","tokens_in":9629,"feed_emoji":"📊","tokens_out":14058,"duration_ms":130109,"temperature":0.7,"pith_summary":"The paper's central claim is that many extremal questions for distance-based graph indices can be settled at once by comparing a single object, the distance sequence: the sorted list of all pairwise shortest-path distances. If one graph's list is at least as large as another's entry by entry, then every nondecreasing index, such as the hyper-Wiener index, is at least as large, and every nonincreasing index, such as the Harary index, is at least as small. The paper identifies, for several graph classes, a graph whose distance sequence dominates all others, and thereby derives sharp extremal bounds for every monotone distance-based index at once. In particular, among connected graphs of fixed order and size, the path-complete graph has minimum Harary index and maximum hyper-Wiener index, resolving an open problem from the monograph on the Harary index. The same template covers even-connectivity graphs, maximal k-degenerate graphs, maximal outerplanar graphs, Apollonian networks, and trees with all degrees odd.","feed_headline":"One graph settles the Harary-index problem","feed_subtitle":"Sorted distance lists make the path-complete graph extremal for every monotone Wiener-type index.","key_machinery":"The central object is the distance sequence $D(G)$, the nondecreasing list of distances between all unordered pairs of vertices, compared entry by entry. The transfer statement, Proposition 1, converts a distance-sequence comparison into an index comparison for any index that is monotone in each coordinate; this is why all named indices can be handled at once. The work in each section is to find a graph whose distance sequence dominates every graph in the class: the path-complete graph $PK_{n,m}$ for fixed order and size, the $\\kappa/2$-th power of the cycle $C_n^{\\kappa/2}$ for even connectivity $\\kappa$, the $k$-th power of the path $P_n^k$ for maximal $k$-degenerate graphs, and the odd tree $T_n$ for trees with all degrees odd. Lemma 1, the deletion inequality $D(G) \\le D(G-v) \\odot D_G(v)$ for a non-cut vertex $v$, is the inductive engine that proves the new distance-sequence extrema.","core_discovery":"The discovery is that the extremal graph for a whole family of distance-based indices is determined by the maximum of the distance sequence, not by the particular index. A distance-based index is any function of the sorted distance list $D(G)$, and it is nondecreasing or nonincreasing according to how it responds to each entry. The paper's transfer principle says: if every graph in a class satisfies $D(G) \\le D(H^*)$ for a fixed graph $H^*$, then $H^*$ maximises every nondecreasing distance-based index and minimises every nonincreasing one. Taking $H^*$ to be the path-complete graph $PK_{n,m}$, a path whose end vertex is joined to a clique, gives the main theorem: for connected graphs of order $n$ and size $m$, $PK_{n,m}$ maximises the hyper-Wiener and multiplicative Wiener indices and minimises the Harary index, resolving the open problem from the Harary-index monograph. The same transfer applied to known or newly proved distance-sequence maxima yields $C_n^{\\kappa/2}$ for even-$\\kappa$-connected graphs, $P_n^k$ for maximal $k$-degenerate graphs and $k$-trees, and $T_n$ for odd trees.","pith_inferences":["If a distance-sequence maximum is found for odd connectivity, the same template would immediately yield sharp Harary and hyper-Wiener bounds for $\\kappa$-connected graphs with odd $\\kappa$, a case the paper leaves open.","The paper leaves open whether all maximal planar graphs have distance sequence at most that of $P_n^3$; a positive answer would give sharp Harary and hyper-Wiener bounds for all maximal planar graphs by the same argument.","Computationally, the approach reduces bounding any monotone distance-based index on these classes to evaluating one fixed sequence, so closed-form or algorithmic bounds follow directly from the explicit distance sequence of the extremal graph.","Because the extremality criterion is the distance sequence, the same machinery could be reused in any graph class where a dominating distance sequence is known or can be constructed, such as classes with prescribed diameter or degree sequence."],"forward_implications":["Among all connected graphs of order $n$ and size $m$, the path-complete graph simultaneously minimises the Harary index and maximises the hyper-Wiener and multiplicative Wiener indices, settling the open problem from the Harary-index monograph.","For every even $\\kappa$, the graph $C_n^{\\kappa/2}$ is extremal for all nondecreasing distance-based indices among $\\kappa$-connected graphs of order $n$, and for $\\kappa = 2$ the cycle is the unique extremal graph.","Among maximal $k$-degenerate graphs and $k$-trees, $P_n^k$ is extremal for all nondecreasing distance-based indices; this makes $P_n^2$ extremal for maximal outerplanar graphs and $P_n^3$ for Apollonian networks.","Among trees whose vertices all have odd degree, the tree $T_n$ is extremal for all nondecreasing distance-based indices.","Any future monotone distance-based index automatically inherits these same extremal graphs, because extremality is a property of the distance sequence rather than of the individual index."],"supporting_citations":[{"why":"Supplies the imported distance-sequence maximality results, Lemmas 2 and 3, on which Theorems 1 and 2 rest.","marker":"[11]"},{"why":"Introduces the path-complete graph and proves it maximises the Wiener index, the base result Theorem 1 extends to all nondecreasing distance-based indices.","marker":"[35]"},{"why":"The monograph that poses the open problem on sharp lower bounds for the Harary index, which Theorem 1 resolves.","marker":"[44]"},{"why":"Proves every maximal k-degenerate graph is k-connected, a step used in the proof that P_n^k has maximal distance sequence.","marker":"[7]"},{"why":"Shows P_n^k maximises the Wiener index among maximal k-degenerate graphs, the result Theorem 3 generalises to all nondecreasing distance-based indices.","marker":"[8]"}],"fun_headline_variants":["Path-complete graph resolves Harary index open problem","Distance sequence bounds all Wiener-type indices","Sharp bounds for Harary and hyper-Wiener indices","Extremal graphs for general Wiener-type indices found","Solving Harary index problem via distance sequences"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument depends on two maximum-distance-sequence facts imported from an earlier paper: every connected graph with n vertices and m edges has distance sequence no larger than that of the path-complete graph, and every even-connectivity graph has distance sequence no larger than that of the appropriate power of a cycle; if either imported fact is false, the corresponding sharp bounds, including the Harary-index resolution, collapse.","fun_headline_variants_meta":{"raw":{"variants":["Path-complete graph resolves Harary index open problem","Distance sequence bounds all Wiener-type indices","Sharp bounds for Harary and hyper-Wiener indices","Extremal graphs for general Wiener-type indices found","Solving Harary index problem via distance sequences"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000274,"raw_usage":{"total_tokens":1648,"prompt_tokens":966,"completion_tokens":682,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":610}},"tokens_in":582,"tokens_out":682,"duration_ms":7182,"temperature":1.0,"reasoning_tokens":610,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:25:36.710778+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all connected graphs with n vertices and m edges for n up to 7 and compare, entry by entry, their sorted distance lists with the distance list of the path-complete graph; finding any graph whose list is larger in some coordinate would disprove Theorem 1. The same exhaustive check against the relevant power of the cycle for 2-connected and 4-connected graphs would test the even-connectivity theorem.","supporting_citations":[{"cited_title":"Casablanca, P","cited_arxiv_id":null,"evidence_quote":"Supplies the imported distance-sequence maximality results, Lemmas 2 and 3, on which Theorems 1 and 2 rest."},{"cited_title":"Solt´ es, Transmission in graphs: A bound and vertex removing","cited_arxiv_id":null,"evidence_quote":"Introduces the path-complete graph and proves it maximises the Wiener index, the base result Theorem 1 extends to all nondecreasing distance-based indices."},{"cited_title":"Xu, K.Ch","cited_arxiv_id":null,"evidence_quote":"The monograph that poses the open problem on sharp lower bounds for the Harary index, which Theorem 1 resolves."},{"cited_title":"Bickle, Structural results on maximal k-degenerate graphs","cited_arxiv_id":null,"evidence_quote":"Proves every maximal k-degenerate graph is k-connected, a step used in the proof that P_n^k has maximal distance sequence."},{"cited_title":"Bickle, Z","cited_arxiv_id":null,"evidence_quote":"Shows P_n^k maximises the Wiener index among maximal k-degenerate graphs, the result Theorem 3 generalises to all nondecreasing distance-based indices."}],"review_version":1}