pith. sign in

arxiv: 2606.10312 · v2 · pith:EEGMU6QAnew · submitted 2026-06-09 · 🧮 math.CO

On the Spectra of Digraph Laplacians

Saieed Akbari , Michael Cavers , Farzad Maghsoudi , Babak Miraftab This is my paper

Pith reviewed 2026-06-27 13:01 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C20
keywords digraph Laplacianout-degree Laplacianspectral radiusline digraphcharacteristic polynomialincidence matrixarc reversal
0
0 comments X

The pith

The spectral radius of the out-degree Laplacian of any loopless digraph is at most the number of its vertices.

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

The paper defines out-degree, in-degree, incidence, symmetrized, and skew-symmetrized Laplacian matrices for loopless directed graphs. It proves that the incidence Laplacian equals the ordinary Laplacian of the underlying undirected multigraph and derives relations for these matrices under arc reversal and complementation. The central result is an upper bound on the spectral radius of the out-degree Laplacian together with an equality characterization. Explicit expressions are also obtained for the spectra of joins and of line digraphs of regular digraphs, including a determinantal identity that links the characteristic polynomials of a regular digraph and its line digraph.

Core claim

For any loopless digraph D of order n the spectral radius of its out-degree Laplacian satisfies rho(L_out) <= n, with equality characterized in the stated cases. The incidence Laplacian L_inc coincides with the Laplacian of the underlying undirected multigraph. For regular digraphs a determinantal identity relates the characteristic polynomials of L_out(D) and L_out of the line digraph of D.

What carries the argument

The out-degree Laplacian L_out = Delta_out - A, where Delta_out is the diagonal out-degree matrix and A the adjacency matrix of the loopless digraph; this matrix supplies the spectral radius bound and the relations under graph operations.

If this is right

  • All eigenvalues of L_out lie in the interval [0, n].
  • The characteristic polynomial of L_out for the line digraph of a regular digraph is determined by that of the original digraph via an explicit determinant formula.
  • Spectral information for the symmetrized matrix S_out simplifies when the digraph is Eulerian.
  • Reversing all arcs produces a related Laplacian whose spectrum is obtained from the original by a simple transformation.

Where Pith is reading between the lines

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

  • Because L_inc equals the undirected Laplacian, every known spectral property of undirected graphs transfers immediately to the incidence version on digraphs.
  • The determinantal identity supplies a recursive route to the spectra of iterated line digraphs of regular digraphs.
  • The bound and the equality cases together classify the directed graphs that attain the maximum possible spectral radius for L_out.

Load-bearing premise

The digraph has no self-loops.

What would settle it

A single loopless digraph on n vertices whose out-degree Laplacian has an eigenvalue larger than n would falsify the spectral-radius bound.

Figures

Figures reproduced from arXiv: 2606.10312 by Babak Miraftab, Farzad Maghsoudi, Michael Cavers, Saieed Akbari.

Figure 1
Figure 1. Figure 1: A digraph of order 4 with its corresponding line digraph [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The direct sum and join of two digraphs D1 and D2, where D1 is a directed path on three vertices and D2 is a directed cycle on two vertices [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
read the original abstract

We present several Laplacian-type matrices associated with a loopless digraph $D$: the out-/in-degree Laplacians $\mathcal L_{\mathrm{out}},\mathcal L_{\mathrm{in}}$, the incidence Laplacian $\mathcal L_{\mathrm{inc}}=BB^{\mathsf T}$, and the symmetrized and skew-symmetrized variants $\mathcal S_{\mathrm{out}},\mathcal K_{\mathrm{out}}$. We show that $\mathcal L_{\mathrm{inc}}(D)$ coincides with the Laplacian of the underlying undirected multigraph, and we derive spectral and characteristic-polynomial relations under arc reversal and complementation (including a simplification for Eulerian digraphs for $\mathcal S_{\mathrm{out}}$). We demonstrate that the spectral radius of $\mathcal L_{\mathrm{out}}$ is bounded above by the order of the digraph and give a characterization in the equality case. We further obtain explicit formulas for joins and line digraphs, giving a general determinantal identity relating the out-degree Laplacian characteristic polynomials of a regular digraph and its line digraph.

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

0 major / 3 minor

Summary. The manuscript defines several Laplacian-type matrices for loopless digraphs (out-/in-degree Laplacians L_out and L_in, incidence Laplacian L_inc = BB^T, and symmetrized/skew-symmetrized variants S_out and K_out). It proves that L_inc coincides with the Laplacian of the underlying undirected multigraph, derives spectral and characteristic-polynomial relations under arc reversal and complementation (including a simplification for Eulerian digraphs), shows that the spectral radius of L_out is at most the digraph order n with an equality characterization, and supplies explicit formulas for joins and line digraphs together with a determinantal identity relating the out-degree Laplacian characteristic polynomials of a regular digraph and its line digraph.

Significance. If the derivations hold, the results extend standard spectral-graph techniques to directed graphs by furnishing explicit bounds, equality cases, and a general determinantal relation for line digraphs of regular digraphs. These identities are of interest in combinatorial matrix theory and may support further work on regular digraph spectra and network Laplacians.

minor comments (3)
  1. [Abstract] The abstract states the main results clearly but does not indicate the sections containing the proofs of the spectral-radius bound or the determinantal identity; adding such pointers would improve navigation.
  2. [Introduction] The definition of the incidence matrix B and the precise statement that the digraph is loopless should appear in the first paragraph of the introduction rather than being deferred, to make the matrix constructions immediately unambiguous.
  3. In the discussion of Eulerian digraphs, the simplification for S_out is stated without an explicit reference to the preceding reversal or complementation identities; a forward pointer to the relevant equation would clarify the derivation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its potential interest in combinatorial matrix theory, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivations are direct from definitions and linear-algebra identities

full rationale

The paper introduces out-/in-degree Laplacians, incidence Laplacian, and symmetrized variants directly from the loopless digraph adjacency and degree matrices. All listed results (spectral-radius bound with equality case, relations under reversal/complementation/joins/line digraphs, and the determinantal identity) are obtained by applying standard matrix identities to these explicit constructions. No parameters are fitted to data and then relabeled as predictions, no self-citation chain is invoked to justify a uniqueness claim, and no ansatz is smuggled in. The abstract and listed claims remain self-contained against the matrix definitions without reduction to their own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard definitions of digraph degree and incidence matrices together with the algebraic properties of the characteristic polynomial; no free parameters or new entities are introduced.

axioms (2)
  • standard math Characteristic polynomial of a matrix is defined as det(xI - A) and satisfies standard algebraic identities under similarity and block constructions.
    Invoked implicitly when relating characteristic polynomials of L_out under joins and line digraphs.
  • domain assumption A loopless digraph has no self-loops, so out-degree and in-degree are sums over distinct arcs.
    Stated at the beginning; required for the matrices to match the usual undirected Laplacian when directions are ignored.

pith-pipeline@v0.9.1-grok · 5722 in / 1440 out tokens · 20781 ms · 2026-06-27T13:01:02.429714+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

41 extracted references · 22 canonical work pages

  1. [1]

    Wang, Yi and Fan, Yizheng and Tan, Yingying , TITLE =. Appl. Math. J. Chinese Univ. Ser. B , FJOURNAL =. 2007 , NUMBER =. doi:10.1007/s11766-007-0414-z , URL =

    work page doi:10.1007/s11766-007-0414-z 2007

  2. [2]

    , TITLE =

    Pozrikidis, C. , TITLE =. 2014 , PAGES =

    2014

  3. [3]

    Discrete Math

    Hong, Yuan and Zhang, Xiao-Dong , TITLE =. Discrete Math. , FJOURNAL =. 2005 , NUMBER =. doi:10.1016/j.disc.2005.04.001 , URL =

    work page doi:10.1016/j.disc.2005.04.001 2005

  4. [4]

    , TITLE =

    Das, Kinkar ch. , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2003 , PAGES =. doi:10.1016/S0024-3795(02)00687-0 , URL =

    work page doi:10.1016/s0024-3795(02)00687-0 2003

  5. [5]

    Nonlinear Phenomena in Complex Systems , volume=

    A Primer on Laplacian Dynamics in Directed Graphs , author=. Nonlinear Phenomena in Complex Systems , volume=. 2020 , doi =

    2020

  6. [6]

    IEEE Transactions on automatic control , volume=

    Consensus problems in networks of agents with switching topology and time-delays , author=. IEEE Transactions on automatic control , volume=. 2004 , publisher=

    2004

  7. [7]

    Fiol, M. A. and Mitjana, M. , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2007 , NUMBER =. doi:10.1016/j.laa.2006.11.018 , URL =

    work page doi:10.1016/j.laa.2006.11.018 2007

  8. [8]

    Su, Li and Li, Hong-Hai and Zheng, Liu-Rong , TITLE =. Discuss. Math. Graph Theory , FJOURNAL =. 2012 , NUMBER =. doi:10.7151/dmgt.1612 , URL =

    work page doi:10.7151/dmgt.1612 2012

  9. [9]

    Symmetry , volume=

    On the Laplacian and signless Laplacian characteristic polynomials of a digraph , author=. Symmetry , volume=. 2022 , publisher=

    2022

  10. [10]

    The Laplacian spectrum of some digraphs obtained from the wheel , url =

    Li Su, Hong-Hai Li, Liu-Rong Zheng , journal =. The Laplacian spectrum of some digraphs obtained from the wheel , url =

  11. [11]

    Grone, Robert and Merris, Russell and Sunder, V. S. , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 1990 , doi =

    1990

  12. [12]

    and Pati, S

    Barik, S. and Pati, S. and Sarma, B. K. , title =. SIAM Journal on Discrete Mathematics , volume =. 2007 , doi =

    2007

  13. [13]

    The spectrum of the edge corona of two graphs

    Yaoping Hou and SHIU, Wai Chee. The spectrum of the edge corona of two graphs. Electronic Journal of Linear Algebra. 2010. doi:10.13001/1081-3810.1395

    work page doi:10.13001/1081-3810.1395 2010

  14. [14]

    Acta Math

    Bendixson, Ivar , TITLE =. Acta Math. , FJOURNAL =. 1902 , NUMBER =. doi:10.1007/BF02419030 , URL =

    work page doi:10.1007/bf02419030 1902

  15. [15]

    Electron

    Yang, Xiuwen and Liu, Xiaogang and Wang, Ligong , TITLE =. Electron. J. Linear Algebra , FJOURNAL =. 2023 , PAGES =. doi:10.13001/ela.2023.7503 , URL =

    work page doi:10.13001/ela.2023.7503 2023

  16. [16]

    Electron

    Caughman IV, John S and Veerman, JJ Peter , TITLE =. Electron. J. Combin. , FJOURNAL =. 2006 , NUMBER =. doi:10.37236/1065 , URL =

    work page doi:10.37236/1065 2006

  17. [17]

    Chebolu, Prasad and Frieze, Alan , TITLE =. SIAM J. Discrete Math. , FJOURNAL =. 2008 , NUMBER =. doi:10.1137/060670808 , URL =

    work page doi:10.1137/060670808 2008

  18. [18]

    Cvetković and P

    D. Cvetković and P. Rowlinson and S. Simić , title =. Linear Algebra Appl. , volume =

  19. [19]

    Grone and R

    R. Grone and R. Merris and V.S. Sunder , title =. SIAM J. Matrix Anal. Appl. , volume =

  20. [20]

    H. A. Ganie and Y. Shang , title =. Heliyon , volume =

  21. [21]

    and Johnson, Charles R

    Horn, Roger A. and Johnson, Charles R. , TITLE =. 2013 , PAGES =

    2013

  22. [22]

    , TITLE =

    Meyer, Carl D. , TITLE =. [2023] 2023 , PAGES =

    2023

  23. [23]

    Linear Algebra Appl

    Cavers, Michael and Miraftab, Babak , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2025 , PAGES =. doi:10.1016/j.laa.2024.10.028 , URL =

    work page doi:10.1016/j.laa.2024.10.028 2025

  24. [24]

    Linear Algebra Appl

    Spectra of corona products of digraphs , author=. Linear Algebra Appl. , FJOURNAL =. 2026 , PAGES =. doi:10.1016/j.laa.2026.05.023 , URL =

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

  25. [25]

    Hoffman, Kenneth and Kunze, Ray , title =

  26. [26]

    Matrix Analysis , author =

  27. [27]

    Internet Math

    Li, Yanhua and Zhang, Zhi-Li , TITLE =. Internet Math. , FJOURNAL =. 2012 , NUMBER =. doi:10.1080/15427951.2012.708890 , URL =

    work page doi:10.1080/15427951.2012.708890 2012

  28. [28]

    Linear Algebra Appl

    Ostrander, Aaron , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2015 , PAGES =. doi:10.1016/j.laa.2015.04.031 , URL =

    work page doi:10.1016/j.laa.2015.04.031 2015

  29. [29]

    and Evans, Emily and Hall, H

    Barrett, Wayne and Cameron, Thomas R. and Evans, Emily and Hall, H. Tracy and Kempton, Mark , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2023 , PAGES =. doi:10.1016/j.laa.2023.01.016 , URL =

    work page doi:10.1016/j.laa.2023.01.016 2023

  30. [30]

    , TITLE =

    Brualdi, Richard A. , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2010 , NUMBER =. doi:10.1016/j.laa.2009.02.033 , URL =

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

  31. [31]

    Linear Algebra Appl

    Boley, Daniel and Ranjan, Gyan and Zhang, Zhi-Li , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2011 , NUMBER =. doi:10.1016/j.laa.2011.01.030 , URL =

    work page doi:10.1016/j.laa.2011.01.030 2011

  32. [32]

    and Ryser, Herbert J

    Brualdi, Richard A. and Ryser, Herbert J. , TITLE =. 1991 , PAGES =. doi:10.1017/CBO9781107325708 , URL =

    work page doi:10.1017/cbo9781107325708 1991

  33. [33]

    Linear Algebra Appl

    McLeman, Cam and McNicholas, Erin , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2011 , NUMBER =. doi:10.1016/j.laa.2011.02.007 , URL =

    work page doi:10.1016/j.laa.2011.02.007 2011

  34. [34]

    Linear Algebra Appl

    Cui, Shu-Yu and Tian, Gui-Xian , TITLE =. Linear Algebra Appl. , FJOURNAL =. 2012 , NUMBER =. doi:10.1016/j.laa.2012.05.019 , URL =

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

  35. [35]

    arXiv preprint arXiv:2509.14481 , year=

    Digraph Laplacians , author=. arXiv preprint arXiv:2509.14481 , year=

    arXiv

  36. [36]

    and Johnson, Charles R

    Horn, Roger A. and Johnson, Charles R. , TITLE =. 1985 , PAGES =. doi:10.1017/CBO9780511810817 , URL =

    work page doi:10.1017/cbo9780511810817 1985

  37. [37]

    Izvestiya Akademii Nauk SSSR, Otdelenie Fiziko-Matematicheskikh Nauk , number =

    Ger. Izvestiya Akademii Nauk SSSR, Otdelenie Fiziko-Matematicheskikh Nauk , number =

  38. [38]

    , TITLE =

    Varga, Richard S. , TITLE =. 2004 , PAGES =. doi:10.1007/978-3-642-17798-9 , URL =

    work page doi:10.1007/978-3-642-17798-9 2004

  39. [39]

    Acta Mathematica , volume =

    Bendixson, Ivar , title =. Acta Mathematica , volume =. 1902 , doi =

    1902

  40. [40]

    preprint , year=

    Eigenvalue Bounds and Spectral Properties of Digraph Laplacians , author=. preprint , year=

  41. [41]

    2026 , eprint=

    Spectra of subdivision products of digraphs , author=. 2026 , eprint=

    2026