pith. sign in

arxiv: 2606.06945 · v1 · pith:JJLEU6XOnew · submitted 2026-06-05 · 🧮 math.CO

On a distance Laplacian analog of Brouwer's conjecture for several classes of graphs

Silin Huang This is my paper

Pith reviewed 2026-06-27 22:02 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C12
keywords distance LaplacianBrouwer conjectureWiener indexeigenvalue partial sumsgraph diametermaximum degreeauxiliary graphsspectral graph theory
0
0 comments X

The pith

The distance Laplacian analog of Brouwer's conjecture holds for all sufficiently large graphs of bounded diameter, all but two diameter-2 graphs, and all graphs with maximum degree n-k above a size threshold depending on k.

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

The paper proves that the partial sums of the largest distance Laplacian eigenvalues satisfy the proposed bound involving the Wiener index for three families of connected graphs. The first family consists of all graphs whose diameter is at most D once the number of vertices reaches roughly four-ninths of (D+1) cubed. The second family covers diameter-2 graphs except the stars K_{1,3} at r=2 and K_{1,4} at r=3. The third family covers graphs whose largest degree equals n minus k once n exceeds a threshold that is 10 when k=2 and roughly 5(k-1) to the three-halves for larger k. The proofs rest on expressing the distance Laplacian as a sum of ordinary Laplacians of auxiliary graphs whose edges join pairs at least a fixed distance apart, then applying classical eigenvalue inequalities to each piece.

Core claim

For any connected graph G the inequality sum from i=1 to r of the i-th largest distance Laplacian eigenvalue is at most the Wiener index W(G) plus the binomial coefficient of r+2 choose 3. This holds for every connected graph of diameter at most D when n is at least the ceiling of (4/9)(D+1)^3; it holds for every diameter-2 graph except K_{1,3} when r=2 and K_{1,4} when r=3; and it holds whenever the maximum degree equals n-k once n meets or exceeds N(k) with N(2)=10 and N(k) equal to the ceiling of 5(k-1)^{3/2} for k at least 3.

What carries the argument

Decomposition of the distance Laplacian matrix into a sum of Laplacian matrices of auxiliary graphs whose edges connect pairs of vertices at distance at least a fixed threshold, allowing classical bounds on Laplacian eigenvalues to be applied term by term.

If this is right

  • Every fixed diameter D yields a finite threshold beyond which the conjecture holds for all larger graphs.
  • All diameter-2 graphs satisfy the bound except the two listed small exceptions at the two listed values of r.
  • Any graph whose largest degree is n minus a fixed k satisfies the bound once the order exceeds the stated N(k).
  • The three families together cover all graphs whose diameter is small, whose diameter is exactly two, or whose degree sequence is nearly regular at the top.

Where Pith is reading between the lines

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

  • The same decomposition may produce explicit constants or remove the size thresholds for the three families.
  • If the only exceptions in the diameter-2 case are the two stars already identified, the conjecture would hold for every connected graph of diameter two.
  • The auxiliary-graph decomposition could be adapted to obtain analogous bounds for other distance-based matrices such as the distance signless Laplacian.

Load-bearing premise

The distance Laplacian matrix admits a decomposition into ordinary Laplacian matrices of auxiliary graphs that lets standard eigenvalue inequalities produce the desired numerical bound.

What would settle it

A single counterexample graph of diameter D with at least ceil((4/9)(D+1)^3) vertices for which the partial sum of distance Laplacian eigenvalues exceeds W(G) plus binom(r+2,3) for some r.

Figures

Figures reproduced from arXiv: 2606.06945 by Silin Huang.

Figure 1
Figure 1. Figure 1: Illustrations of K1,3 and K1,4, respectively. We now combine the preceding theorems with an analysis of the small-order graphs to obtain the full diameter-2 graph classification. Theorem 4.8. Let G be a connected graph of diameter 2. Then the target inequality holds for every valid r, except for K1,3 at r = 2 and K1,4 at r = 3 ( [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
read the original abstract

Zhou et al. (2025) proposed a distance Laplacian analog of Brouwer's conjecture on partial sums of Laplacian eigenvalues, asserting that for any connected graph $G$, $\sum_{i=1}^r \partial_i^L(G)\le W(G)+\binom{r+2}{3},$ where $\partial_i^L(G)$ are the eigenvalues of the distance Laplacian matrix and $W(G)$ is the Wiener index. We prove this inequality for three broad classes of graphs, thereby improving and extending existing results. First, we prove that all connected graphs of diameter at most $D$ satisfy the inequality once the order $n$ satisfies $n\ge\lceil\frac49(D+1)^3\rceil$. Second, we show that the inequality holds for every diameter-$2$ graph with the only exceptions being $K_{1,3}$ at $r=2$ and $K_{1,4}$ at $r=3$. Third, we prove that if the maximum degree is $\Delta(G)=n-k$, then the inequality holds for all $n\ge N(k)$, where $N(2)=10$ and $N(k)=\lceil 5(k-1)^{3/2}\rceil$ for $k\ge 3$. Our proofs rely on decomposing the distance Laplacian matrix into Laplacian matrices of auxiliary graphs whose edges are vertex pairs at distance at least a prescribed value, together with classical eigenvalue inequalities.

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.

Referee Report

1 major / 0 minor

Summary. The paper proves a distance-Laplacian analog of Brouwer's conjecture, namely that ∑_{i=1}^r ∂_i^L(G) ≤ W(G) + inom{r+2}{3} for any connected graph G, for three classes: (i) all connected graphs of diameter ≤ D once n ≥ ⌈(4/9)(D+1)^3⌉, (ii) all diameter-2 graphs except K_{1,3} (r=2) and K_{1,4} (r=3), and (iii) graphs with Δ(G)=n-k once n ≥ N(k) (with explicit N(2)=10 and N(k)=⌈5(k-1)^{3/2}⌉ for k≥3). All three proofs rest on writing the distance Laplacian as a sum of ordinary Laplacians of auxiliary graphs whose edges join pairs at distance at least a fixed threshold, followed by classical partial-sum eigenvalue inequalities.

Significance. If the matrix decompositions are exact, the results give concrete, large-scale support for the conjecture and improve earlier partial results by covering all sufficiently large graphs in each of the three families. The approach is standard but the explicit diameter and degree thresholds, together with the identification of the only two exceptional diameter-2 graphs, constitute a useful advance.

major comments (1)
  1. [the decomposition step (common to all three proofs)] The central proofs for all three classes rely on an exact matrix identity decomposing the distance Laplacian Diag(Tr) − D into a sum of ordinary graph Laplacians of auxiliary graphs G_k. Because the transmission vector Tr is defined from the distance matrix D, any such decomposition must simultaneously decompose both the diagonal and the off-diagonal blocks; an incomplete accounting of the zero-eigenvalue multiplicities or of the diagonal contributions would invalidate the subsequent application of Weyl/Ky-Fan bounds. The manuscript must exhibit the explicit identity (including verification that the auxiliary graphs are simple and that the sum reproduces both Tr and D) in the section where the auxiliary graphs are introduced.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the constructive comment on the decomposition. We address it below and will revise the manuscript to incorporate the requested explicit identity.

read point-by-point responses

  1. Referee: [the decomposition step (common to all three proofs)] The central proofs for all three classes rely on an exact matrix identity decomposing the distance Laplacian Diag(Tr) − D into a sum of ordinary graph Laplacians of auxiliary graphs G_k. Because the transmission vector Tr is defined from the distance matrix D, any such decomposition must simultaneously decompose both the diagonal and the off-diagonal blocks; an incomplete accounting of the zero-eigenvalue multiplicities or of the diagonal contributions would invalidate the subsequent application of Weyl/Ky-Fan bounds. The manuscript must exhibit the explicit identity (including verification that the auxiliary graphs are simple and that the sum reproduces both Tr and D) in the section where the auxiliary graphs are introduced.

    Authors: We agree that the manuscript should contain an explicit matrix identity for the decomposition to ensure both the diagonal (Tr) and off-diagonal (D) contributions are fully accounted for, along with verification of simplicity of the auxiliary graphs and correct zero-eigenvalue handling. While the decomposition approach is outlined, the explicit identity with these verifications is not displayed. In the revised manuscript we will insert the required explicit identity immediately after the auxiliary graphs are defined, confirming that their Laplacians sum to Diag(Tr) − D exactly and that the subsequent Weyl/Ky-Fan applications remain valid. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation uses external classical inequalities on explicit matrix decomposition

full rationale

The paper's proofs for the three classes rest on an explicit decomposition of the distance Laplacian into a sum of auxiliary graph Laplacians (defined by distance thresholds) followed by application of standard eigenvalue inequalities (Weyl, Ky Fan). No parameters are fitted to the target inequality, no quantity is defined in terms of itself, and no self-citation supplies a uniqueness theorem or ansatz that forces the result. The central claims therefore remain independent of the paper's own inputs and are not reduced by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proofs rest on the existence of a decomposition of the distance Laplacian into ordinary Laplacians of auxiliary graphs and on the applicability of standard eigenvalue majorization or interlacing inequalities; no free parameters or new entities are introduced.

axioms (1)
  • standard math Classical eigenvalue inequalities (e.g., interlacing or majorization) hold for the Laplacian matrices of the auxiliary graphs constructed from distance thresholds.
    Invoked as the final step that converts the decomposition into the target bound, per the abstract.

pith-pipeline@v0.9.1-grok · 5785 in / 1480 out tokens · 25962 ms · 2026-06-27T22:02:58.706867+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    Brouwer and Willem H

    Andries E. Brouwer and Willem H. Haemers, Spectra of graphs , Springer, New York, 2012. DOI: 10.1007/978-1-4614-1939-6

    work page doi:10.1007/978-1-4614-1939-6 2012

  2. [2]

    Haemers, Ali Mohammadian, and Behruz Tayfeh-Rezaie, On the sum of Laplacian eigenvalues of graphs, Linear Algebra and its Applications 432 (2010), no

    Willem H. Haemers, Ali Mohammadian, and Behruz Tayfeh-Rezaie, On the sum of Laplacian eigenvalues of graphs, Linear Algebra and its Applications 432 (2010), no. 9, 2214–2221. DOI: 10.1016/j.laa.2009.03.038

    work page doi:10.1016/j.laa.2009.03.038 2010

  3. [3]

    DOI: 10.1016/j.laa.2026.01.026

    Ke Wang, Zhen Lin, Shumin Zhang, and Chengfu Ye,A proof of Brouwer’s conjecture fork = 3, Linear Algebra and its Applications 736 (2026), 189–213. DOI: 10.1016/j.laa.2026.01.026

    work page doi:10.1016/j.laa.2026.01.026 2026

  4. [4]

    9, 3672–3683

    Zhibin Du and Bo Zhou, Upper bounds for the sum of Laplacian eigenvalues of graphs , Linear Algebra and its Applications 436 (2012), no. 9, 3672–3683. DOI: 10.1016/j.laa.2012.01.007

    work page doi:10.1016/j.laa.2012.01.007 2012

  5. [5]

    DOI: 10.1016/j.laa.2018.08.003

    Xiaodan Chen, Improved results on Brouwer’s conjecture for sum of the Laplacian eigen- values of a graph , Linear Algebra and its Applications 557 (2018), 327–338. DOI: 10.1016/j.laa.2018.08.003

    work page doi:10.1016/j.laa.2018.08.003 2018

  6. [6]

    DOI: 10.1016/j.laa.2019.05.029

    Xiaodan Chen, On Brouwer’s conjecture for the sum of k largest Laplacian eigen- values of graphs , Linear Algebra and its Applications 578 (2019), 402–410. DOI: 10.1016/j.laa.2019.05.029

    work page doi:10.1016/j.laa.2019.05.029 2019

  7. [7]

    DOI: 10.1016/j.laa.2019.11.020

    Hilal Ahmad Ganie, Shariefuddin Pirzada, Bilal Ahmad Rather, and Vilmar Trevisan, Further developments on Brouwer’s conjecture for the sum of Laplacian eigenvalues of graphs , Linear Algebra and its Applications 588 (2020), 1–18. DOI: 10.1016/j.laa.2019.11.020

    work page doi:10.1016/j.laa.2019.11.020 2020

  8. [8]

    1, 21–33

    Mustapha Aouchiche and Pierre Hansen, Two Laplacians for the distance matrix of a graph , Linear Algebra and its Applications 439 (2013), no. 1, 21–33. DOI: 10.1016/j.laa.2013.02.030

    work page doi:10.1016/j.laa.2013.02.030 2013

  9. [9]

    3, 751–761

    Mustapha Aouchiche and Pierre Hansen, Some properties of the distance Laplacian eigen- values of a graph , Czechoslovak Mathematical Journal 64 (2014), no. 3, 751–761. DOI: 10.1007/s10587-014-0129-2

    work page doi:10.1007/s10587-014-0129-2 2014

  10. [10]

    DOI: 10.1016/j.laa.2014.07.025

    Milan Nath and Somnath Paul, On the distance Laplacian spectra of graphs , Linear Algebra and its Applications 460 (2014), 97–110. DOI: 10.1016/j.laa.2014.07.025

    work page doi:10.1016/j.laa.2014.07.025 2014

  11. [11]

    DOI: 10.1016/j.laa.2015.11.014

    Huiqiu Lin, Baoyindureng Wu, Yingying Chen, and Jinlong Shu, On the distance and distance Laplacian eigenvalues of graphs , Linear Algebra and its Applications 492 (2016), 128–135. DOI: 10.1016/j.laa.2015.11.014

    work page doi:10.1016/j.laa.2015.11.014 2016

  12. [12]

    de Freitas, Celso M

    Ros´ ario Fernandes, Maria Aguieiras A. de Freitas, Celso M. Jr. da Silva, and Renata Raposo del Vecchio, Multiplicities of distance Laplacian eigenvalues and forbidden subgraphs , Linear Algebra and its Applications 541 (2018), 81–93. DOI: 10.1016/j.laa.2017.11.031

    work page doi:10.1016/j.laa.2017.11.031 2018

  13. [13]

    DOI: 10.13001/ela.2020.4941

    Boris Brimkov, Ken Duna, Leslie Hogben, Kate Lorenzen, Carolyn Reinhart, Sung-Yell Song, and Mark Yarrow,Graphs that are cospectral for the distance Laplacian, The Electronic Journal of Linear Algebra 36 (2020), 334–351. DOI: 10.13001/ela.2020.4941

    work page doi:10.13001/ela.2020.4941 2020

  14. [14]

    DOI: 10.1016/j.dam.2024.10.001

    Bilal Ahmad Rather and Mustapha Aouchiche, Distance Laplacian spectra of graphs: A survey, Discrete Applied Mathematics 361 (2025), 136–195. DOI: 10.1016/j.dam.2024.10.001. 14

    work page doi:10.1016/j.dam.2024.10.001 2025

  15. [15]

    Yuwei Zhou, Ligong Wang, and Yirui Chai, Brouwer type conjecture for the eigenvalues of distance Laplacian matrix of a graph , Computational and Applied Mathematics 44 (2025), no. 3, 14. DOI: 10.1007/s40314-025-03095-0

    work page doi:10.1007/s40314-025-03095-0 2025

  16. [16]

    1, 83–91

    Shariefuddin Pirzada and Saleem Khan, On the sum of distance Laplacian eigen- values of graphs , Tamkang Journal of Mathematics 54 (2023), no. 1, 83–91. DOI: 10.5556/j.tkjm.54.2023.4120

    work page doi:10.5556/j.tkjm.54.2023.4120 2023

  17. [17]

    1, 193–202

    Ummer Mushtaq, Shariefuddin Pirzada, and Saleem Khan, On the sum of the eigenvalues of the distance Laplacian matrix of graphs with diameter three and four , Revista de la Uni´ on Matem´ atica Argentina69 (2026), no. 1, 193–202. DOI: 10.33044/revuma.5147

    work page doi:10.33044/revuma.5147 2026

  18. [18]

    11, 652–655

    Ky Fan, On a theorem of Weyl concerning eigenvalues of linear transformations I, Proceedings of the National Academy of Sciences 35 (1949), no. 11, 652–655. DOI: 10.1073/pnas.35.11.652

    work page doi:10.1073/pnas.35.11.652 1949

  19. [19]

    2, 221–229

    Robert Grone and Russell Merris, The Laplacian spectrum of a graph II , SIAM Journal on Discrete Mathematics 7 (1994), no. 2, 221–229. DOI: 10.1137/S0895480191222653

    work page doi:10.1137/s0895480191222653 1994

  20. [20]

    8, 4463–4474

    Hua Bai, The Grone-Merris conjecture, Transactions of the American Mathematical Society 363 (2011), no. 8, 4463–4474. DOI: 10.1090/S0002-9947-2011-05393-6

    work page doi:10.1090/s0002-9947-2011-05393-6 2011

  21. [21]

    DOI: 10.1016/j.laa.2013.11.006

    Gerald Williams, Smith forms for adjacency matrices of circulant graphs , Linear Algebra and its Applications 443 (2014), 21–33. DOI: 10.1016/j.laa.2013.11.006. 15

    work page doi:10.1016/j.laa.2013.11.006 2014