pith. sign in

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

On digraphs determined by their singular values

Mushtaq A. Bhat , Peer Abdul Manan This is my paper

Pith reviewed 2026-05-13 17:13 UTC · model grok-4.3

classification 🧮 math.CO
keywords digraphssingular valuesLaplacian matrixsignless Laplaciandetermined by spectradirected pathdirected cycleoriented star
0
0 comments X

The pith

Directed paths, cycles, and a specific oriented star are uniquely determined by the singular values of their Laplacian and signless Laplacian matrices.

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

The paper computes explicit singular values for the Laplacian matrices of directed paths, directed cycles, and all orientations of stars. It shows that bipartite digraphs have identical singular values for the Laplacian and signless Laplacian matrices, allowing transfer of formulas between them. The authors then prove that the directed path, directed cycle, and one particular oriented star are the only digraphs sharing those exact singular value lists. The same uniqueness fails when using singular values from the adjacency matrix instead.

Core claim

The directed path, the directed cycle, and the oriented star with all arcs outgoing from the center are determined by their Laplacian and signless Laplacian singular values but are not determined by their adjacency singular values, with explicit formulas supplied for the singular values and trace norms in each case.

What carries the argument

The Laplacian matrix L(D) = Δ⁺ − A(D) and signless Laplacian Q(D) = Δ⁺ + A(D) of a digraph D, whose singular values are computed directly for the three families to establish uniqueness.

If this is right

  • The directed path, cycle, and chosen star can be reconstructed from the singular values of L or Q alone.
  • For any bipartite digraph the singular values of L and Q coincide, so formulas transfer directly.
  • Adjacency singular values do not suffice to distinguish these digraphs from non-isomorphic examples.
  • Exact closed-form expressions exist for the trace norms of L and Q on these digraphs.

Where Pith is reading between the lines

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

  • Laplacian singular values appear stronger than adjacency singular values for recovering orientation information in these families.
  • The same explicit computation technique might apply to other small digraph families such as tournaments or directed trees.
  • Numerical checks of singular-value multisets could serve as a practical filter for directed-graph isomorphism on modest orders.
  • The bipartiteness link between L and Q suggests analogous equalities could be sought for other matrix pairs on oriented graphs.

Load-bearing premise

The digraphs are simple with the stated orientations and the equality of singular values between L and Q relies on the bipartiteness condition.

What would settle it

Exhibiting any digraph not isomorphic to one of the three families yet sharing exactly the same multiset of Laplacian singular values would disprove the determination claim.

Figures

Figures reproduced from arXiv: 2604.03615 by Mushtaq A. Bhat, Peer Abdul Manan.

Figure 1
Figure 1. Figure 1: An oriented Star S⃗ n(x, y) Let Jy be the all-ones matrix of order y × y, E be a square matrix of order x + 1 with E11 = 1, Eij = 0 for (i, j) ̸= (1, 1) and F be a square matrix of order x + 1 with F1j = 1 for j = 2, 3, . . . , x + 1; Fij = 0 otherwise, and G be a matrix of order y × (x + 1) with Gi1 = 1 for i = 1, 2, . . . , y; Gij = 0 for (i, j) ̸= (1, 1),(2, 1), . . . ,(y, 1). 10 [PITH_FULL_IMAGE:figur… view at source ↗
Figure 2
Figure 2. Figure 2: Oriented trees on 4 vertices with outdegree sequence [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: U1, unicyclic digraph with outdegree sequence [14 ] v3 v4 v5 v1 v2 U2 v1 v2 v3 v4 v5 U3 v1 v2 v3 v5 v4 U4 v1 v2 v3 v4 v5 T4 [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Possible subdigraphs U2, U3, U4 and T4 for n ≥ 5. If D is an acyclic digraph with n vertices and n arcs, then the outdegree sequence of D differs from [1n ] and Zg+(D) > n. If D is not connected and has k ≥ 2 components, since L( −→C n) has 0 as a singular value with multiplicity 1, whereas D has 0 as a singular value with multiplicity at least k ≥ 2 and so D and −→C n cannot have same singular values. 16 … view at source ↗
Figure 5
Figure 5. Figure 5: Oriented trees with outdegree sequence [14 , 0]. (ii). We will compare −→C n with the class of unicyclic digraphs and proof for other cases is similar to part (i). From [Lemma 2.9, [4]], we see that for any U ∈ U(n), σ Q 1 (U) ≥ 2 with equality if and only if U = −→C n, hence no U ∈ U(n) \ −→C n and −→C n have same Q singular values. The proof that −→P n is determined by Q singular values is similar. (iii)… view at source ↗
read the original abstract

Let $D$ be an digraph of order $n$ with adjacency matrix $A(D)$ and outdegree matrix $\Delta^+=\Delta^+(D)$. Then the Laplacian and signless Laplacian matrices of $D$ are respectively defined as $L(D)=\Delta^+-A(D)$ and $Q(D)=\Delta^++A(D)$. In this paper, we compute singular values and an exact formula for the trace norm of Laplacian matrices of the directed path $\overrightarrow{P_n}$, the directed cycle $\overrightarrow{C_n}$ and all orientations of a star. We show that for a bipartite digraph $D$, the matrices $L(D)$ and $Q(D)$ have same singular values and use this to compute the singular values and trace norm of signless Laplacian matrices. We study the problem of determination of digraphs by their singular values and prove the directed path $\overrightarrow{P_n}$, the directed cycle $\overrightarrow{C_n}$ and oriented star $\overrightarrow{S}_n(n-1,0)$ are determined by their Laplacian and signless Laplacian singular values but are not determined by their adjacency singular values.

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

2 major / 2 minor

Summary. The paper defines Laplacian L(D) = Δ⁺ - A(D) and signless Laplacian Q(D) = Δ⁺ + A(D) for a digraph D. It derives explicit singular values and trace-norm formulas for L of the directed path P_n, directed cycle C_n, and all orientations of the star S_n. It proves that L(D) and Q(D) share the same singular values precisely when D is bipartite, then uses this to obtain the singular values and trace norms for Q on the listed families. Finally, it shows that P_n, C_n, and the oriented star S_n(n-1,0) are uniquely determined by their L and Q singular values but not by their adjacency singular values.

Significance. If the derivations hold, the explicit singular-value formulas and trace-norm expressions for these standard digraph families, together with the determination results, add concrete data to the spectral theory of directed graphs. The bipartiteness lemma is a useful technical tool, and the contrast between L/Q determination and adjacency non-determination is a clear, falsifiable contribution.

major comments (2)
  1. [Proof of determination for C_n (signless-Laplacian case)] The equality of singular values between L(D) and Q(D) is established only for bipartite digraphs. For the directed cycle C_n with odd n the underlying undirected cycle is non-bipartite, so the equality does not apply. The determination claim for the signless-Laplacian singular values of all C_n therefore requires either an explicit direct computation of the Q singular values for odd n or an extension of the equality that is not stated in the manuscript.
  2. [Section on oriented stars] The uniqueness argument for the oriented star S_n(n-1,0) under L and Q singular values appears to rest on the explicit formulas derived earlier; if those formulas contain an unverified step for the non-bipartite case (or for the out-degree sequence), the uniqueness claim is unsupported. A concrete check that the multiset of singular values distinguishes this orientation from all other orientations of the same star is needed.
minor comments (2)
  1. [Introduction] Notation for the oriented star S_n(n-1,0) should be defined explicitly at first use, including the precise out-degree sequence.
  2. [Computation of trace norms] The trace-norm formulas are stated without a displayed equation number; cross-referencing them in the determination proofs would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. We address each major comment below and will revise the manuscript to incorporate the requested additions and clarifications.

read point-by-point responses

  1. Referee: [Proof of determination for C_n (signless-Laplacian case)] The equality of singular values between L(D) and Q(D) is established only for bipartite digraphs. For the directed cycle C_n with odd n the underlying undirected cycle is non-bipartite, so the equality does not apply. The determination claim for the signless-Laplacian singular values of all C_n therefore requires either an explicit direct computation of the Q singular values for odd n or an extension of the equality that is not stated in the manuscript.

    Authors: We agree that the equality L(D) and Q(D) share the same singular values only when D is bipartite, as proved in the manuscript. For odd n the directed cycle is non-bipartite, so that lemma does not apply. In the revised version we will add a direct computation of the singular values of Q(C_n) for odd n. Since every vertex has out-degree 1, Q(C_n) = I + A(C_n), where A(C_n) is the circulant adjacency matrix of the directed cycle. Its eigenvalues are 1 + exp(2 pi i k / n) for k = 0 to n-1; the singular values are therefore the moduli of these complex numbers, which we will list explicitly. With the resulting closed-form multiset we then verify that no other digraph on n vertices shares the same singular values, completing the determination proof for all n. revision: yes

  2. Referee: [Section on oriented stars] The uniqueness argument for the oriented star S_n(n-1,0) under L and Q singular values appears to rest on the explicit formulas derived earlier; if those formulas contain an unverified step for the non-bipartite case (or for the out-degree sequence), the uniqueness claim is unsupported. A concrete check that the multiset of singular values distinguishes this orientation from all other orientations of the same star is needed.

    Authors: The underlying undirected graph of any orientation of the star is a tree and therefore bipartite, so the L-Q singular-value equality applies without issue. The explicit singular-value formulas for both L and Q of the out-star S_n(n-1,0) are obtained directly from the matrix definitions (Delta^+ has a single nonzero entry n-1 on the diagonal and A encodes the n-1 outgoing arcs). To strengthen the uniqueness claim we will insert, in the revised manuscript, a short argument showing that any other orientation of S_n produces a different out-degree sequence and hence a different multiset of singular values. Concretely, the trace norm (sum of singular values) equals the sum of the out-degrees plus a non-negative term that depends on the arc directions; this quantity already separates the out-star from all other orientations, and the full singular-value multisets are likewise distinct. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit computations for fixed families with independent bipartiteness lemma

full rationale

The derivation computes singular values of L(D) directly from the definitions of Δ⁺ and A(D) for the specific families P_n, C_n and oriented stars, then invokes a general lemma that L and Q share singular values precisely when the digraph is bipartite. This lemma is applied only to the bipartite cases (even cycles, paths, stars) to obtain the Q singular values; for odd cycles the paper must rely on separate direct computation of Q, which is not shown to reduce to the L values by definition. Determination statements follow by comparing the resulting explicit multisets against other digraphs of the same order. No equation is defined in terms of its own output, no fitted parameter is relabeled as a prediction, and no load-bearing step rests on a self-citation. The chain is therefore self-contained through matrix algebra rather than circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard linear-algebra facts about singular values and matrix norms for digraph matrices; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)
  • standard math Singular values and trace norm are well-defined for any real matrix via the SVD.
    Invoked for all computations of L(D) and Q(D).

pith-pipeline@v0.9.0 · 5491 in / 1075 out tokens · 26007 ms · 2026-05-13T17:13:16.632244+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

15 extracted references · 15 canonical work pages

  1. [1]

    Agudelo, J

    N. Agudelo, J. Rada, Lower bounds of Nikiforov’s energy over digraphs, Linear Algebra Appl. 496 (2016) 156-164

    work page 2016

  2. [2]

    Agudelo, J

    N. Agudelo, J. Rada, M. Rivera, Upper bound for the trace norm of the Laplacian matrix of a digraph and normally regular digraphs, Linear Algebra Appl. 552 (2018) 194-209

    work page 2018

  3. [3]

    Akbari, F

    S. Akbari, F. Belardo, E. Dodongeh, M. Nematollahi, Spectral characterizations of signed cycles, Linear Algebra Appl. 553 (2018) 307-327

    work page 2018

  4. [4]

    M. A. Bhat, P. A. Manan, Bounds for the trace norm ofAα matrix of digraphs, Discrete Math. 348 (2025) 114491

    work page 2025

  5. [5]

    Bravo, F

    D. Bravo, F. Cubria, J. Rada, Energy of matrices, Appl. Math. Comput. 312 (2017) 149-157

    work page 2017

  6. [6]

    K. C. Das, M. Liu, Kite graphs determined by their spectra, Appl. Math. Comput. 297 (2017) 74-78

    work page 2017

  7. [7]

    E. Dam, W. Haemers, Which graphs are determined by their spectrum? Linear Algebra Appl. 373 (2003) 241-272

    work page 2003

  8. [8]

    M. Doob, W. Haemers, The complement of the path is determined by its spectrum, Linear Algebra Appl. 356 (2002) 57-65

    work page 2002

  9. [9]

    H. A. Ganie, S. Pirzada, On the first outdegree Zagreb index of a digraph, Discrete Math. 347 (2024) 113726

    work page 2024

  10. [10]

    R. A. Horn, C. R. Jhonson, Matrix Analysis, Cambridge University Press (2013)

    work page 2013

  11. [11]

    X. Li, Y. Shi, I. Gutman, Graph Energy, Springer-Verlag, New York, 2012

    work page 2012

  12. [12]

    Monsalve, J

    J. Monsalve, J. Rada, Y. Shi, Extremal values of energy over oriented bicyclic graphs, Appl. Math. Comput. 342 (2019) 26-34. 18

    work page 2019

  13. [13]

    V.Nikiforov, Theenergyofgraphsandmatrices, J.Math.Anal.Appl.326(2007)1472-1475

    work page 2007

  14. [14]

    I. Peña, J. Rada, Energy of digraphs, Linear Multilinear Algebra, 56 (5) (2008) 565-579

    work page 2008

  15. [15]

    Topcu, S

    H. Topcu, S. Sorgun, The kite graph is determined by its adjacency spectrum, Appl. Math. Comput. 330 (2018) 134-142. 19

    work page 2018