On a conjecture of distance spectral extremal problems

Hongzhang Chen; Jianxi Li; Yongtao Li

arxiv: 2604.26385 · v1 · submitted 2026-04-29 · 🧮 math.CO

On a conjecture of distance spectral extremal problems

Hongzhang Chen , Jianxi Li , Yongtao Li This is my paper

Pith reviewed 2026-05-07 11:22 UTC · model grok-4.3

classification 🧮 math.CO

keywords distance spectral radiusextremal graph theoryconjecturepath complementsspectral radius minimizationconnected graphs with m edges

0 comments

The pith

The complement of balanced disjoint paths minimizes the distance spectral radius for any number of edges.

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

This paper solves the conjecture that among all connected graphs with exactly m edges, the one with smallest distance spectral radius is always the complement of a balanced disjoint union of paths. It gives a single proof that works for the full range of the auxiliary parameter s from 1 to n-1, covering both the previously settled large-s cases and the open small-s cases. The result therefore completely characterizes the extremal graph in terms of n and s derived from m. A reader cares because the distance spectral radius encodes global distance structure, so knowing its minimizer supplies a concrete structural description for how to arrange m edges to keep all pairwise distances as small as possible in the spectral sense.

Core claim

For every m ≥ 3 let n satisfy binom(n-1,2) < m ≤ binom(n,2) and write m = binom(n-1,2) + s with 1 ≤ s ≤ n-1. The unique graph in the class G(m) of connected m-edge graphs that minimizes the distance spectral radius ρ(G) is the complement of a balanced disjoint union of paths, denoted overline{P_{n,s+1}}.

What carries the argument

Comparison principle for ordering distance spectral radii of candidate graphs, supported by increment analysis of Φ-functions on paths and cycles together with path-balancing and Neumann-series walk counting.

If this is right

The extremal graph is unique for every m.
One proof technique now covers the entire range of s.
Balancing the lengths of the paths in the complement is essential for minimality.
All earlier partial results for large s are recovered as special cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same structural description may govern minimizers for other distance-based matrices such as the distance Laplacian.
The comparison and increment techniques could be tested on small explicit graphs to give independent verification for small s.
The result supplies a candidate construction for network-design problems that seek to minimize average or spectral distance.

Load-bearing premise

The comparison principle and Φ-function increment analysis correctly rank the distance spectral radii of every graph in G(m) even when s is small.

What would settle it

A single connected graph with m edges whose distance spectral radius is strictly smaller than that of overline{P_{n,s+1}} would disprove the claim.

read the original abstract

Brualdi and Hoffman proposed a well-known problem of determining the graph with maximum adjacency spectral radius among all graphs with given size $m$. Early work by Friedland and Stanley addressed some specific cases. This problem was later completely solved by Rowlinson and recently revisited by Cheng and Weng. Pioneering work on the distance matrix was carried out by Graham and Pollak, as well as by Graham and Lov\'{a}sz. The distance spectral radius $\rho (G)$ of a connected graph $G$ is the largest eigenvalue of its distance matrix. In this paper, we completely solve the problem of characterizing the connected graph with minimum distance spectral radius among all graphs with size $m$. Let $\mathcal{G}(m)$ be the class of connected graphs with $m$ edges. For every $m \ge 3$, let $n$ be the unique integer satisfying $\binom{n-1}{2} < m \le \binom{n}{2}$, and we write $m = \binom{n-1}{2} + s$ with $1 \le s \le n-1$. Recently, Lin and Zhou [Adv. in Appl. Math. 173 (2026)] investigated the graph in $\mathcal{G}(m)$ that minimizes $\rho(G)$ in the range $s \ge \max\{ \frac{n-6}{2}, 1\}$. However, the problem is much more difficult in the remaining range $1 \le s \le \frac{n-7}{2}$, and they conjectured that the unique minimizer is $\overline{P_{n,s+1}}$, the complement of a balanced disjoint union of paths. Using novel matrix analysis, we solve this conjecture in the affirmative. Moreover, we provide a new unified proof for the entire range $1 \le s \le n-1$. The key ingredients in our proof argument include an innovative comparison principle for the distance spectral radius, an increment analysis of $\Phi$-functions on paths and cycles, an argument for balancing path lengths, and a walk enumeration technique via the Neumann series.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles the remaining case of the distance spectral radius minimizer conjecture for graphs with m edges and supplies a unified proof, but the new comparison principle lacks independent checks in the small-s range.

read the letter

Your colleague should know that this paper claims to have settled the last open case of the conjecture on the minimum distance spectral radius among connected graphs with a fixed number of edges. They also give a unified proof that covers the entire range. They handle the difficult interval where s is small, from 1 up to (n-7)/2, which Lin and Zhou left open. The new tools are a comparison principle for the distance spectral radius, an increment analysis for Φ-functions on paths and cycles, a balancing argument for path lengths, and walk enumeration using the Neumann series. These let them show that the claimed minimizer, the complement of a balanced disjoint union of paths, is indeed the unique one with the smallest radius. The unified proof is a real strength. It pulls together the earlier partial results into one argument instead of case-by-case handling. The main concern is whether the new comparison principle and the increment analysis actually work in the small-s regime. The paper invokes them to order the distance radii of all graphs in the class, but the abstract and the description stay at a high level. There are no explicit small-n verifications or tables of computed radii to confirm that the inequalities are strict when the graphs are most unbalanced. If any step in that chain fails for some pair of graphs when s is small, the uniqueness part does not hold. That is the spot that needs the most attention from a referee. This paper is aimed at researchers in spectral graph theory who care about distance matrices and extremal problems. Someone following the Brualdi-Hoffman type questions or the work on distance spectra would find the resolution useful. The techniques could carry over to related problems. It is worth sending to peer review. The claim is important enough that referees should check the details of the new principle rather than desk-rejecting it.

Referee Report

2 major / 2 minor

Summary. The paper claims a complete affirmative solution to the conjecture of Lin and Zhou: among all connected graphs with m edges (where m = binom(n-1,2) + s and 1 ≤ s ≤ n-1), the unique graph minimizing the distance spectral radius ρ(G) is the complement of a balanced disjoint union of paths, denoted overline{P_{n,s+1}}. The authors supply a new unified proof covering the full range, including the previously open interval 1 ≤ s ≤ (n-7)/2, via a novel comparison principle for ρ(D), increment analysis of Φ-functions on paths and cycles, a balancing argument, and walk enumeration through the Neumann series.

Significance. If the central arguments hold, the result fully characterizes the distance-spectral minimizers in G(m) for every m ≥ 3, closing the gap left by Lin and Zhou’s work on the larger-s regime. The introduction of a comparison principle and Φ-increment analysis constitutes a methodological contribution that could extend to other distance-matrix extremal problems.

major comments (2)

[Proof of the main result for the difficult range (high-level description in abstract and §3)] The novel comparison principle for the distance spectral radius (invoked throughout the proof of the main theorem for 1 ≤ s ≤ (n-7)/2) is load-bearing for both the minimality and uniqueness claims, yet the manuscript provides no independent verification—such as explicit eigenvalue computations or exhaustive checks on small-n instances in this regime—where the path-complement structure is most unbalanced; this directly addresses the skeptic’s concern about unverified ordering of candidate graphs.
[Increment analysis and balancing argument (abstract and corresponding proof section)] The increment analysis of Φ-functions on paths and cycles, combined with the balancing argument, is used to establish that any graph in G(m) has ρ at least as large as that of overline{P_{n,s+1}}; however, the manuscript does not supply an explicit check that the strict inequality is preserved for all non-isomorphic pairs when s ≤ (n-7)/2, which is required to support the uniqueness assertion.

minor comments (2)

[Introduction] The citation to Lin and Zhou (Adv. in Appl. Math. 173 (2026)) should include a note clarifying its status, as the year is in the future relative to the arXiv posting.
[Introduction and Theorem 1.1] Notation for overline{P_{n,s+1}} and the precise definition of the balanced path union could be restated explicitly in the statement of the main theorem for reader convenience.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive feedback. We respond to each major comment below, indicating the revisions we plan to make.

read point-by-point responses

Referee: [Proof of the main result for the difficult range] The novel comparison principle for the distance spectral radius is load-bearing for both the minimality and uniqueness claims, yet the manuscript provides no independent verification—such as explicit eigenvalue computations or exhaustive checks on small-n instances in this regime—where the path-complement structure is most unbalanced.

Authors: We acknowledge that the manuscript relies on the theoretical development of the comparison principle without additional numerical checks for the range 1 ≤ s ≤ (n-7)/2. To address this concern and provide reassurance regarding the ordering of candidate graphs, we will add a new subsection in the revised version containing explicit computations of the distance spectral radius for small n (e.g., n ≤ 12) in the relevant s range, comparing the proposed minimizer with other potential candidates. This will serve as independent verification. revision: yes
Referee: [Increment analysis and balancing argument] The increment analysis of Φ-functions on paths and cycles, combined with the balancing argument, is used to establish that any graph in G(m) has ρ at least as large as that of overline{P_{n,s+1}}; however, the manuscript does not supply an explicit check that the strict inequality is preserved for all non-isomorphic pairs when s ≤ (n-7)/2, which is required to support the uniqueness assertion.

Authors: The balancing argument shows that unbalanced partitions lead to strictly larger Φ values, and thus larger ρ, with equality only for isomorphic graphs. However, we agree that making the strictness explicit for non-isomorphic cases in the difficult range would strengthen the uniqueness proof. In the revision, we will expand the relevant section to include a detailed case analysis or additional lemmas demonstrating that the inequality is strict unless the graphs are isomorphic. revision: yes

Circularity Check

0 steps flagged

No circularity: proof deploys novel comparison principle and Φ-increment analysis as independent tools

full rationale

The derivation chain rests on four explicitly introduced techniques—an innovative comparison principle for ρ(D), increment analysis of Φ-functions on paths/cycles, a balancing argument for path lengths, and Neumann-series walk enumeration—none of which are shown to reduce by the paper’s own equations to the target minimizer or to any fitted parameter. The conjecture itself originates in prior work by Lin and Zhou (distinct authors), and the present manuscript supplies a unified proof rather than invoking self-citation as load-bearing justification. No equation or step equates the claimed extremal graph to a quantity defined in terms of itself or to a statistical fit on the same data; the argument therefore remains self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on standard linear algebra (eigenvalue properties of symmetric matrices) and graph-theoretic facts (connectedness, distance matrix definition) with no free parameters fitted to data, no invented entities, and no ad-hoc axioms beyond those already established in the literature.

axioms (1)

standard math The distance matrix of a connected graph is symmetric and nonnegative with positive off-diagonal entries for non-adjacent vertices.
Invoked implicitly when applying spectral radius comparisons and Neumann series expansion.

pith-pipeline@v0.9.0 · 5688 in / 1281 out tokens · 47004 ms · 2026-05-07T11:22:12.389778+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Alon, S.M

N. Alon, S.M. Cioab˘ a, B.D. Gilbert, J.H. Koolen, B.D. McKay, Addressing Johnson graphs, complete multipartite graphs, odd cycles, and random graphs, Exp. Math., 30 (2021) 372–382

work page 2021
[2]

Aouchiche, P

M. Aouchiche, P. Hansen, Distance spectra of graphs: a survey, Linear Algebra Appl. 458 (2014) 301–386

work page 2014
[3]

Bhatia, Matrix Analysis, GTM 169, Springer-Verlag, New York, 1997

R. Bhatia, Matrix Analysis, GTM 169, Springer-Verlag, New York, 1997

work page 1997
[4]

Brualdi, A.J

R.A. Brualdi, A.J. Hoffman, On the spectral radius of (0,1)-matrices, Linear Algebra Appl. 65 (1985) 133–146

work page 1985
[5]

Cheng, C.-W

Y.-J. Cheng, C.-W. Weng, A matrix realization of spectral bounds, J. Combin. Theory Ser. B 174 (2025) 1–27

work page 2025
[6]

L. Fang, Y. Li, H. Lin, J. Ma, Spectral supersaturation for color-critical graphs, (2025), arXiv:2512.22482

work page arXiv 2025
[7]

Friedland, The maximal eigenvalue of 0-1 matrices with prescribed number of ones, Linear Algebra Appl

S. Friedland, The maximal eigenvalue of 0-1 matrices with prescribed number of ones, Linear Algebra Appl. 69 (1985) 33–69

work page 1985
[8]

Graham, H.O

R.L. Graham, H.O. Pollak, On the addressing problem for loop switching, Bell Syst. Tech. J. 50 (1971) 2495–2519

work page 1971
[9]

Graham, A.J

R.L. Graham, A.J. Hoffman, H. Hosoya, On the distance matrix of a directed graph, J. Graph Theory 1 (1977) 85–88

work page 1977
[10]

Graham, L

R.L. Graham, L. Lov´ asz, Distance matrix polynomials of trees, Adv. Math. 29 (1978) 60–88

work page 1978
[11]

S. Li, S. Zhao, L. Zou, Spectral extrema of graphs with fixed size: forbidden a fan graph, a friendship graph, or a theta graph, J. Graph Theory 110 (4) (2025) 483–495

work page 2025
[12]

X. Li, M. Zhai, J. Shu, A Brualdi–Hoffman–Tur´ an problem on cycles, European J. Combin. 120 (2024), Paper No. 103966

work page 2024
[13]

Y. Li, H. Liu, S. Zhang, More on Nosal’s spectral theorem: Books and 4-cycles, J. Combin. Theory Ser. B 179 (2026) 219–249

work page 2026
[14]

Y. Li, H. Liu, S. Zhang, An edge-spectral Erd˝ os–Stone–Simonovits theorem and its stability, (2025), arXiv:2508.15271

work page arXiv 2025
[15]

Y. Li, H. Liu, S. Zhang, Edge-spectral Tur´ an theorems for color-critical graphs with applica- tions, (2025), arXiv:2511.15431

work page arXiv 2025
[16]

H. Lin, J. Shu, J. Xue, Y. Zhang, A survey on distance spectra of graphs, Adv. Math. (China) 50 (1) (2021) 29–76

work page 2021
[17]

H. Lin, B. Zhou, Extremal distance spectral radius of graphs with fixed size, Adv. in Appl. Math. 173 (2026), Paper No. 102980

work page 2026
[18]

Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin

V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002) 179–189

work page 2002
[19]

Rowlinson, On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl

P. Rowlinson, On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl. 110 (1988) 43–53. 13

work page 1988
[20]

Ruzieh, D.L

S.N. Ruzieh, D.L. Powers, The distance spectrum of the pathP n and the first distance eigen- vector of connected graphs, Linear Multilinear Algebra 28(1990) 75–81

work page 1990
[21]

Sawa, On a symmetric representation of Hermitian matrices and its applications to graph theory, J

M. Sawa, On a symmetric representation of Hermitian matrices and its applications to graph theory, J. Combin. Theory Ser. B 116 (2016) 484–503

work page 2016
[22]

Stanley, A bound on the spectral radius of graphs witheedges, Linear Algebra Appl

R.P. Stanley, A bound on the spectral radius of graphs witheedges, Linear Algebra Appl. 87 (1987) 267–269

work page 1987
[23]

Watanabe, K

S. Watanabe, K. Ishii, M. Sawa, AQ-analogue of the addressing problem of graphs by Graham and Pollak, SIAM J. Discrete Math. 26 (2) (2012) 527–536

work page 2012
[24]

Stevanovi´ c, A

D. Stevanovi´ c, A. Ili´ c, Distance spectral radius of trees with fixed maximum degree, Electron. J. Linear Algebra 20 (2010) 168–179. 14

work page 2010

[1] [1]

Alon, S.M

N. Alon, S.M. Cioab˘ a, B.D. Gilbert, J.H. Koolen, B.D. McKay, Addressing Johnson graphs, complete multipartite graphs, odd cycles, and random graphs, Exp. Math., 30 (2021) 372–382

work page 2021

[2] [2]

Aouchiche, P

M. Aouchiche, P. Hansen, Distance spectra of graphs: a survey, Linear Algebra Appl. 458 (2014) 301–386

work page 2014

[3] [3]

Bhatia, Matrix Analysis, GTM 169, Springer-Verlag, New York, 1997

R. Bhatia, Matrix Analysis, GTM 169, Springer-Verlag, New York, 1997

work page 1997

[4] [4]

Brualdi, A.J

R.A. Brualdi, A.J. Hoffman, On the spectral radius of (0,1)-matrices, Linear Algebra Appl. 65 (1985) 133–146

work page 1985

[5] [5]

Cheng, C.-W

Y.-J. Cheng, C.-W. Weng, A matrix realization of spectral bounds, J. Combin. Theory Ser. B 174 (2025) 1–27

work page 2025

[6] [6]

L. Fang, Y. Li, H. Lin, J. Ma, Spectral supersaturation for color-critical graphs, (2025), arXiv:2512.22482

work page arXiv 2025

[7] [7]

Friedland, The maximal eigenvalue of 0-1 matrices with prescribed number of ones, Linear Algebra Appl

S. Friedland, The maximal eigenvalue of 0-1 matrices with prescribed number of ones, Linear Algebra Appl. 69 (1985) 33–69

work page 1985

[8] [8]

Graham, H.O

R.L. Graham, H.O. Pollak, On the addressing problem for loop switching, Bell Syst. Tech. J. 50 (1971) 2495–2519

work page 1971

[9] [9]

Graham, A.J

R.L. Graham, A.J. Hoffman, H. Hosoya, On the distance matrix of a directed graph, J. Graph Theory 1 (1977) 85–88

work page 1977

[10] [10]

Graham, L

R.L. Graham, L. Lov´ asz, Distance matrix polynomials of trees, Adv. Math. 29 (1978) 60–88

work page 1978

[11] [11]

S. Li, S. Zhao, L. Zou, Spectral extrema of graphs with fixed size: forbidden a fan graph, a friendship graph, or a theta graph, J. Graph Theory 110 (4) (2025) 483–495

work page 2025

[12] [12]

X. Li, M. Zhai, J. Shu, A Brualdi–Hoffman–Tur´ an problem on cycles, European J. Combin. 120 (2024), Paper No. 103966

work page 2024

[13] [13]

Y. Li, H. Liu, S. Zhang, More on Nosal’s spectral theorem: Books and 4-cycles, J. Combin. Theory Ser. B 179 (2026) 219–249

work page 2026

[14] [14]

Y. Li, H. Liu, S. Zhang, An edge-spectral Erd˝ os–Stone–Simonovits theorem and its stability, (2025), arXiv:2508.15271

work page arXiv 2025

[15] [15]

Y. Li, H. Liu, S. Zhang, Edge-spectral Tur´ an theorems for color-critical graphs with applica- tions, (2025), arXiv:2511.15431

work page arXiv 2025

[16] [16]

H. Lin, J. Shu, J. Xue, Y. Zhang, A survey on distance spectra of graphs, Adv. Math. (China) 50 (1) (2021) 29–76

work page 2021

[17] [17]

H. Lin, B. Zhou, Extremal distance spectral radius of graphs with fixed size, Adv. in Appl. Math. 173 (2026), Paper No. 102980

work page 2026

[18] [18]

Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin

V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002) 179–189

work page 2002

[19] [19]

Rowlinson, On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl

P. Rowlinson, On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl. 110 (1988) 43–53. 13

work page 1988

[20] [20]

Ruzieh, D.L

S.N. Ruzieh, D.L. Powers, The distance spectrum of the pathP n and the first distance eigen- vector of connected graphs, Linear Multilinear Algebra 28(1990) 75–81

work page 1990

[21] [21]

Sawa, On a symmetric representation of Hermitian matrices and its applications to graph theory, J

M. Sawa, On a symmetric representation of Hermitian matrices and its applications to graph theory, J. Combin. Theory Ser. B 116 (2016) 484–503

work page 2016

[22] [22]

Stanley, A bound on the spectral radius of graphs witheedges, Linear Algebra Appl

R.P. Stanley, A bound on the spectral radius of graphs witheedges, Linear Algebra Appl. 87 (1987) 267–269

work page 1987

[23] [23]

Watanabe, K

S. Watanabe, K. Ishii, M. Sawa, AQ-analogue of the addressing problem of graphs by Graham and Pollak, SIAM J. Discrete Math. 26 (2) (2012) 527–536

work page 2012

[24] [24]

Stevanovi´ c, A

D. Stevanovi´ c, A. Ili´ c, Distance spectral radius of trees with fixed maximum degree, Electron. J. Linear Algebra 20 (2010) 168–179. 14

work page 2010