pith. sign in

arxiv: 2605.21775 · v1 · pith:LAWPCDUAnew · submitted 2026-05-20 · 🧮 math.CO

Spectra of Subdivision Products of Digraphs

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

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

classification 🧮 math.CO MSC 05C2005C50
keywords directed graphssubdivision productsgraph spectraadjacency spectrumLaplacian spectrumsignless Laplacianjoin productcorona product
0
0 comments X

The pith

Four subdivision products on directed graphs have spectra given directly by the spectra of their inputs.

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

The paper defines four new operations on simple directed graphs by first subdividing vertices or arcs and then applying join or corona constructions. These operations produce larger digraphs whose adjacency, Laplacian, and signless Laplacian spectra can be written in closed form from the spectra of the two input graphs. A reader would care because the formulas let one compute eigenvalues of the combined object without assembling or diagonalizing the big matrix, extending known undirected-graph results to the directed setting where edge direction affects flow and connectivity.

Core claim

The authors introduce the subdivision-vertex join, subdivision-arc join, subdivision-vertex corona, and subdivision-arc corona for simple directed graphs. They derive explicit expressions for the adjacency spectrum, Laplacian spectrum, and signless Laplacian spectrum of each product in terms of the corresponding spectra of the original digraphs, while also recording basic structural features such as order, size, and degree sequences.

What carries the argument

The four subdivision products, each formed by subdividing all vertices or all arcs of one digraph and then joining or corona-attaching it to a second digraph, which together carry the spectral formulas.

If this is right

  • The spectra of the new digraphs are obtained directly from the spectra of the input digraphs without forming the large matrices.
  • Both adjacency and Laplacian-type spectra receive closed-form expressions for all four products.
  • Structural parameters such as number of vertices, arcs, and degrees of the product follow immediately from the inputs.
  • The same constructions that work for undirected graphs remain well-defined when directions are added.

Where Pith is reading between the lines

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

  • The formulas could be used to build families of digraphs whose eigenvalues are known in advance for use in directed-network models.
  • Similar subdivision products might be defined for other matrices such as the distance matrix or the normalized Laplacian.
  • Connections to other directed-graph products, such as the directed Cartesian product, could be investigated using the same subdivision technique.

Load-bearing premise

Extending the subdivision-join and subdivision-corona operations from undirected graphs to directed graphs produces well-defined digraphs whose matrix spectra admit clean closed-form descriptions in terms of the spectra of the input graphs.

What would settle it

Compute the adjacency eigenvalues of the subdivision-vertex join of two small concrete digraphs by hand and check whether they exactly match the eigenvalues predicted by the paper's formula that combines the eigenvalues of the two inputs.

Figures

Figures reproduced from arXiv: 2605.21775 by Babak Miraftab, Farzad Maghsoudi, Michael Cavers.

Figure 1
Figure 1. Figure 1: Above, D1 = P3 (the directed path on three vertices) and D2 is an arbitrary digraph. The dashed (red) lines represent all possible arcs in both directions between vertices in V (D2) and vertices in V (D1) (for D1 ∨˙ D2) or I(D1) (for D1 ∨ D2). Proof. Let D = D1 ∨˙ D2. Observe that V (D) = I(D1) ∪ V (D1) ∪ V (D2) and every vertex in V (D1) is connected to every vertex in V (D2) by a 2-cycle in D, i.e., D ha… view at source ↗
Figure 2
Figure 2. Figure 2: Above, D1 = P3 (the directed path on three vertices) and D2 is an arbitrary digraph. The dashed (red) lines represent all possible arcs in both directions between a vertex v in V (D1) (for D1 ⊙ D2) or I(D1) (for D1 ⊖ D2), and all vertices in the copy of D2 corresponding to v. By ordering of the vertices of D1 ⊙ D2 as V (D1), I(D1), F v∈V (D1) V (D (v) 2 )  , the adjacency, Laplacian and signless Laplacian… view at source ↗
read the original abstract

This paper introduces four types of subdivision products for simple directed graphs extending those from the undirected case, in particular, the subdivision-vertex join, subdivision-arc join, subdivision-vertex corona and subdivision-arc corona. Structural and spectral properties of these constructions are analyzed, with a focus on adjacency, Laplacian and signless Laplacian spectra.

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 / 4 minor

Summary. The paper introduces four subdivision products for simple directed graphs extending the undirected case: the subdivision-vertex join, subdivision-arc join, subdivision-vertex corona, and subdivision-arc corona. It analyzes their structural properties and derives closed-form expressions for the adjacency, Laplacian, and signless Laplacian spectra of the resulting digraphs in terms of the spectra of the input graphs, using standard block-matrix techniques for the characteristic polynomials.

Significance. If the derivations hold, the work supplies explicit spectral formulas for new directed-graph operations, extending a line of research from undirected graphs. This is useful in spectral graph theory for digraphs, where closed-form spectra can aid analysis of network properties such as connectivity or eigenvalue-based stability. The constructions appear well-defined for simple digraphs and the matrix approach follows established patterns without evident circularity or unstated connectivity assumptions.

minor comments (4)
  1. [§2] §2, Definition 2.3: the subdivision-arc join is defined via an auxiliary vertex set; clarify whether the resulting digraph remains simple (no multiple arcs) when the input digraphs contain symmetric arcs.
  2. [Theorem 3.4] Theorem 3.4: the signless-Laplacian spectrum formula for the subdivision-vertex corona factors nicely, but the proof sketch omits the explicit computation of the determinant for the off-diagonal block; adding one intermediate matrix identity would improve readability.
  3. [Figure 2] Figure 2: the diagram for the subdivision-arc corona does not label the new vertices consistently with the block-matrix ordering used in §4; this makes it harder to verify the spectrum claims against the figure.
  4. [References] The bibliography lists several undirected-graph references but omits recent works on Laplacian spectra of directed graphs (e.g., papers on directed corona products); adding two or three such citations would better situate the contribution.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript on subdivision products of digraphs and for recommending minor revision. The summary accurately captures the introduction of the four operations and the spectral derivations via block matrices. Since the report lists no specific major comments, we have used the opportunity to perform a careful review for minor improvements in exposition and notation.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines four explicit subdivision products on digraphs by direct extension of undirected constructions, then derives closed-form spectral expressions for the adjacency, Laplacian, and signless Laplacian matrices via standard block-matrix characteristic polynomial calculations. These derivations depend only on the input graphs' spectra and the explicit block structures of the new products; no parameters are fitted to target results, no self-citations serve as load-bearing uniqueness theorems, and no step reduces by construction to a renaming or redefinition of its own inputs. The chain is therefore self-contained through ordinary linear algebra.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 4 invented entities

The central claims rest on standard linear-algebra facts about adjacency and Laplacian matrices of digraphs together with the new product definitions introduced in the paper.

axioms (1)
  • standard math Adjacency, Laplacian, and signless Laplacian matrices of a digraph are defined in the usual way from its arc set.
    Invoked when the spectra of the new products are expressed in terms of the spectra of the factors.
invented entities (4)
  • subdivision-vertex join no independent evidence
    purpose: New directed-graph product combining subdivision and join operations
    Introduced as one of the four main constructions.
  • subdivision-arc join no independent evidence
    purpose: New directed-graph product combining subdivision and join operations
    Introduced as one of the four main constructions.
  • subdivision-vertex corona no independent evidence
    purpose: New directed-graph product combining subdivision and corona operations
    Introduced as one of the four main constructions.
  • subdivision-arc corona no independent evidence
    purpose: New directed-graph product combining subdivision and corona operations
    Introduced as one of the four main constructions.

pith-pipeline@v0.9.0 · 5567 in / 1367 out tokens · 39281 ms · 2026-05-22T08:22:12.133284+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · 1 internal anchor

  1. [1]

    Barik, D

    S. Barik, D. Kalita, S. Pati, and G. Sahoo. Spectra of graphs resulting from various graph operations and products: a survey.Spec. Matrices, 6:323–342, 2018

    work page 2018

  2. [2]

    Barik and G

    S. Barik and G. Sahoo. On the Laplacian spectra of some variants of corona.Linear Algebra Appl., 512:32–47, 2017

    work page 2017

  3. [3]

    A. E. Brouwer and W. H. Haemers.Spectra of Graphs. Springer, 2012

    work page 2012

  4. [4]

    R. A. Brualdi. Spectra of digraphs.Linear Algebra Appl., 432(9):2181–2213, 2010

    work page 2010

  5. [5]

    Catral, L

    M. Catral, L. Ciardo, L. Hogben, and C. Reinhart. Spectra of products of digraphs.Electron. J. Linear Algebra, 36:744–763, 2020. 14

    work page 2020

  6. [6]

    Cavers, F

    M. Cavers, F. Maghsoudi, and B. Miraftab. Spectra of corona products of digraphs.arXiv preprint arXiv:2509.14481, 2025

    work page arXiv 2025

  7. [7]

    Cavers and B

    M. Cavers and B. Miraftab. Digraphs with few distinct eigenvalues.Linear Algebra Appl., 705:129–142, 2025

    work page 2025

  8. [8]

    Cui and G.-X

    S.-Y. Cui and G.-X. Tian. The spectrum and the signless Laplacian spectrum of coronae.Linear Algebra Appl., 437(7):1692–1703, 2012

    work page 2012

  9. [9]

    Cvetković, M

    D. Cvetković, M. Doob, and H. Sachs.Spectra of Graphs: Theory and Application. Academic Press, 1980

    work page 1980

  10. [10]

    Das and P

    A. Das and P. Panigrahi. Normalized Laplacian spectrum of some subdivision-coronas of two regular graphs.Linear Multilinear Algebra, 65(5):962–972, 2017

    work page 2017

  11. [11]

    Deng and A

    A. Deng and A. Kelmans. Spectra of digraph transformations.Linear Algebra Appl., 439(1):106–132, 2013

    work page 2013

  12. [12]

    M. A. Fiol and M. Mitjana. The spectra of some families of digraphs.Linear Algebra Appl., 423(1):109– 118, 2007

    work page 2007

  13. [13]

    Godsil and G

    C. Godsil and G. Royle.Algebraic Graph Theory. Springer, 2001

    work page 2001

  14. [14]

    Imrich and S

    W. Imrich and S. Klavžar.Product Graphs: Structure and Recognition. Wiley, 2000

    work page 2000

  15. [15]

    G. Indulal. Spectrum of two new joins of graphs and infinite families of integral graphs.Kragujevac J. Math, 36(38):133–139, 2012

    work page 2012

  16. [16]

    F. A. Laali, L. C. J. Dehkharghani, and M. Baroonian. Four new subdivision coronas of two graphs. Wavelet and Linear Algebra, 10(1):1–11, 2023

    work page 2023

  17. [17]

    Liu and P

    X. Liu and P. Lu. Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae.Linear Algebra Appl., 438(8):3547–3559, 2013

    work page 2013

  18. [18]

    Liu and Z

    X. Liu and Z. Zhang. Spectra of subdivision-vertex join and subdivision-edge join of two graphs.Bull. Malays. Math. Sci. Soc., 42(1):15–31, 2019

    work page 2019

  19. [19]

    McLeman and E

    C. McLeman and E. McNicholas. Spectra of coronae.Linear Algebra Appl., 435(5):998–1007, 2011

    work page 2011

  20. [20]

    C. D. Meyer.Matrix Analysis and Applied Linear Algebra. SIAM, 2023

    work page 2023

  21. [21]

    Pavithra and R

    R. Pavithra and R. Rajkumar. On the characteristic polynomial of the subdivision-vertex join of graphs. InInternational Conference on Mathematical Modelling and Computational Intelligence Techniques, volume 376 ofSpringer Proceedings in Mathematics & Statistics, pages 283–294. Springer, Singapore, 2021

    work page 2021

  22. [22]

    Spectra of the subdivision-vertex and subdivision-edge coronae

    L. Pengli and Y. Miao. Spectra of the subdivision-vertex and subdivision-edge coronae.arXiv preprint arXiv:1302.0457, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  23. [23]

    S. Shinoda. On the characteristic polynomial of the adjacency matrix of the subdivision graph of a graph.Discrete Appl. Math., 2:349–351, 1980

    work page 1980

  24. [24]

    R. P. Varghese and K. R. Kumar. Spectra of a new join of two graphs.Advances in Theoretical and Applied Mathematics, 11(4):459–470, 2016

    work page 2016

  25. [25]

    Zhang and Z

    F. Zhang and Z. Chen. Limit points of eigenvalues of (di) graphs.Czechoslovak Math. J., 56(3):895–902, 2006. 15

    work page 2006

  26. [26]

    Zhang, G

    F. Zhang, G. Lin, and J. Meng. The characteristic polynomials of digraphs formed by some unary operations.J. Xinjiang Univ, 4:1–6, 1987. 16

    work page 1987