Total graph of a signed graph

Francesco Belardo; Thomas Zaslavsky; Zoran Stani\'c

REVIEW 3 major objections 5 minor 18 references

Total graph of a signed graph

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Signed graphs get two total-graph constructions, and for regular roots the full spectra are given by closed formulas in the root eigenvalues.

desk verdict A genuinely new construction — two total signed graphs — with a correct regular-case spectral theorem and honest treatment of limitations; a solid, incremental paper that deserves a serious referee. read the letter →

arxiv 1908.02001 v3 pith:GLZAHHIT submitted 2019-08-06 math.CO

Francesco Belardo , Zoran Stanić , Thomas Zaslavsky This is my paper · ORCID

classification math.CO MSC 05C5005C7605C22

keywords BidirectedgraphsignedlinetotaleigenvaluesregularCartesianproduct

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper builds the total-graph construction—the graph obtained from a graph, its line graph, and the vertex–edge incidences between them—for signed graphs. It defines two signed total graphs, the combinatorial $T_C(\Sigma)$ and the spectral $T_S(\Sigma)$, corresponding to the two standard signed line graphs, and proves that both are well defined up to switching and reorientation. The central spectral result is that when the underlying graph is $r$-regular, the full adjacency spectrum of each total graph is written explicitly from $n$, $r$, and the eigenvalues $\lambda_i$ of the root signed graph. A reader would care because this reduces the spectrum of a larger, more complicated signed graph to the spectrum of a smaller one, provides interval bounds on those spectra, and allows iteration and composition of total graphs with known spectra.

What carries the argument

The central object is the signed vertex–edge incidence matrix $B_\eta$ of an oriented signed graph, together with the block-matrix realization of the total graph as $\begin{pmatrix} A_\Sigma & B_\eta \\ B_\eta^\top & A_{L_*}(\Sigma_\eta) \end{pmatrix}$. The orientation rules (O1)–(O3) give the identities $B_\eta B_\eta^\top = D_G - A_\Sigma$, $A_{L_C} = 2I - B_\eta^\top B_\eta$, and $A_{L_S} = B_\eta^\top B_\eta - 2I$. For an $r$-regular root, $B_\eta B_\eta^\top = rI - A_\Sigma$, and substituting this identity into the characteristic determinant of the block matrix, followed by row and column block eliminations, factors the spectrum into a constant eigenvalue plus quadratic factors in the eigenvalues of $A_\Sigma$. The same matrix machinery also proves switching stability, because changing the orientation multiplies $B$ on the right by a diagonal $\pm1$ matrix, which conjugates the total block matrix by a signed permutation matrix.

What would settle it

Directly construct a small regular signed graph—for instance a 2-regular signed cycle of length 4 with one negative edge—write its total adjacency matrices from (4), compute their characteristic polynomials, and compare them with the formulas of Theorem 4.1; any mismatch would refute the claimed universality of the spectral formulas.

Watch

Extended reading notes

Core claim

The paper's central claim is that signed graphs admit a natural total graph that behaves like the unsigned total graph: it is built from the root signed graph, a signed line graph, and the signed incidences between them, and it is well defined up to switching. The combinatorial total graph $T_C$ uses the line graph with adjacency matrix $2I - B^\top B$; the spectral total graph $T_S$ uses $B^\top B - 2I$; in both cases $B$ is the vertex–edge incidence matrix of an orientation of the signed graph satisfying rules (O1)–(O3). The main theorem states that if $\Sigma$ is $r$-regular with eigenvalues $\lambda_1,\dots,\lambda_n$, then $T_C(\Sigma)$ has eigenvalue $2$ with multiplicity $(\frac{r}{2}-1)n$ and the $n$ pairs $\frac{1}{2}(2+2\lambda_i-r\pm\sqrt{r^2-4\lambda_i+4})$, while $T_S(\Sigma)$ has eigenvalue $-2$ with multiplicity $(\frac{r}{2}-1)n$ and the $n$ pairs $\frac{1}{2}(r-2\pm\sqrt{(r-2\lambda_i)^2+4(\lambda_i+1)})$. Beyond the spectrum formula, the paper characterizes balance of the total graphs, bounds their frustration index and number, counts positive and negative triangles, proves spectral interval containment, and determines the spectra of certain Cartesian-product compositions, including a case with exactly two main eigenvalues.

Load-bearing premise

The spectral reduction rests on the signed incidence identity $BB^\top = D_G - A_\Sigma$ for every admissible orientation; if some orientation satisfying (O1)–(O3) failed that identity, the block-matrix simplification and all Theorem 4.1 formulas would collapse.

Editorial extensions

If this is right

For an $r$-regular signed graph, the entire adjacency spectrum of either $T_C$ or $T_S$ is available from the root eigenvalues alone, so cospectral regular roots give cospectral total graphs.
The interval bounds in Corollary 4.2 locate all total-graph eigenvalues using only the largest and smallest root eigenvalues, without computing the full spectrum.
Theorem 4.3 makes iterated spectral total graphs tractable: the vertex count follows the explicit product formula $n_i = n\prod_{j=2}^{i}(2^{j-3}r+1)$, and each stage's spectrum is generated recursively from the previous stage's eigenvalues.
Theorem 4.4 shows that for an all-positive regular signed graph with an Eulerian orientation, the spectral total graph has exactly two main eigenvalues, $r$ and $-2$, so the quotient-matrix method gives them without diagonalizing.
The switching invariance established in Lemmas 3.1 and 3.2 means all these spectral and imbalance invariants are properties of the switching isomorphism class of the root signed graph, not of a chosen orientation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An untested extension: the two-main-eigenvalue theorem should hold for any $r$-regular signed graph that admits an orientation with zero incidence row sums, because the proof uses only those row sums and not the all-positive signature.
The combinatorial total graph $T_C$, which the paper notes satisfies $T_C(-G)=-T(G)$, gives a natural convention for treating unsigned graphs as all-negative signed graphs; classical unsigned total-graph spectral theorems could then be recovered as the all-negative special case of the signed theory.
The inequalities of Theorem 3.8(iii) and the counterexample in Remark 3.9 suggest that the frustration number of $T_C(\Sigma)$ is controlled by the negative triangles of types (c) and (d), so the explicit triangle counts of Theorem 3.6 may yield refined vertex-deletion bounds for the combinatorial total graph.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Here's my read on Belardo–Stanić–Zaslavsky's total graph paper. The headline: the construction is genuinely new — two total signed graphs built from the two competing signed line graphs — and the regular-case spectral formula is correct and proved by a clean block-determinant argument. The paper deserves a serious referee, not a desk reject.

The new content is the definition of T_C and T_S, proof that they are switching stable, the structural results on balance and frustration, and Theorem 4.1 giving complete spectra for regular signed graphs. The main spectral proof checks out. The stress-test note flags a typo in the printed block matrix: the bottom-right block should be xI - 2I + B^T B, not xI - 2I + BB^T. With that correction, the row/column operations do give the stated multiplicities and quadratics. Spot checks on K_3 and signed 4-cycles match. The switching-stability lemmas are also clean.

The soft spots are real but not load-bearing. Theorem 3.8's equality cases — particularly (iv) and (v) about frustration index and number — are argued informally. The reasoning about deleting edges and vertex covers is plausible but not fully detailed, and the authors themselves say exact formulas seem difficult. That's minor because the main theorems don't depend on it. The composition result in Theorem 4.3 is an iteration of the regular case, fine but incremental. Also, the reader should keep in mind that T_S doesn't generalize the unsigned total graph under the usual all-positive convention; the paper is honest about that in Remark 3.4.

No circularity: the eigenvalues are derived from incidence identities and standard determinant manipulations, no fitting. The citation pattern looks right: Zaslavsky's line graphs are cited, and the Sinha–Garg total graph is explicitly distinguished. The novelty claim stands.

Who is this for? Anyone working in spectral theory of signed graphs. It's a useful toolbox paper: the definitions and the regular-case spectra will get cited. It doesn't open a new research program, but it does a needed job carefully.

My recommendation: send it to review. The referee should check the block determinant carefully — there's that typo — and might ask for a bit more rigor in the equality cases, but the central argument is sound.

Referee Report

3 major / 5 minor

Summary. The paper defines two signed analogues of the total graph of a graph, denoted T_C(Σ) and T_S(Σ), built from the vertex-edge incidence matrix of a signed graph and from two different signed line graph constructions. It proves that both constructions are well defined up to switching, studies balance, the frustration index and frustration number, and gives explicit spectra of T_C(Σ) and T_S(Σ) when the underlying graph is regular: Theorem 4.1 expresses the eigenvalues of the two total graphs in terms of the eigenvalues of the root signed graph. The paper also treats a Cartesian-product composition of spectral total graphs and proves a result on main eigenvalues for Eulerian orientations of all-positive regular signed graphs.

Significance. If the results hold, the paper gives a coherent extension of the classical total graph construction to signed graphs, with clean closed-form spectral formulas in the regular case. The main spectral theorem is a genuine contribution and is supported by a complete block-determinant derivation; it also specializes correctly to known unsigned cases, for example reproducing the octahedron spectrum for T(K_3). The paper also provides useful structural facts, including switching invariance, triangle counts, and frustration bounds. The main weakness is that several of the structural proofs, especially equality cases in Theorem 3.8, are argued too informally and, in at least one case, the stated reason is not valid as written; these need repair before the paper can be regarded as fully rigorous.

major comments (3)

[§3.2, Theorem 3.8(iii)] The proof of the equality l(T_S(Σ)) = m + l(L_S(Σ)) is not valid as written. The sentence "Equality holds for TS(Σ) because the triangles of type (c) are positive" does not address cycles that use cross edges together with line-graph edges. Concretely, for Σ = +K_3 with the cyclic orientation, the 6-cycle v1-e1-v2-e2-v3-e3-v1 in T_S(Σ) has sign (-1)^3 = -1; it survives after deleting all three edges of Σ and one line edge, so the deletion construction suggested in the proof does not balance T_S(Σ). The lower-bound argument is also not rigorously justified as stated, because after deleting an arbitrary set of m edges that hits all type-(d) triangles, the remaining graph is not just L_S(Σ). Since Theorem 3.8(iv) depends on (iii), the equality cases require a complete proof or a corrected argument.
[§4.4, Theorem 4.4] The proof of the main-eigenvalue claim is insufficient and contains an invalid inference. The statement that if T_S(Σ_η) had exactly one main eigenvalue then "j is associated with the unique main eigenvalue" does not follow: a main eigenvalue may have an eigenspace of dimension greater than one, and j need not be an eigenvector. The assertion "The spectrum of Q contains the main part of the spectrum" also needs a precise formulation and a proof or a specific citation. A direct argument is available: because the orientation is Eulerian, the vectors (j_n, 0) and (0, j_m) are eigenvectors of T_S(Σ_η) with eigenvalues r and -2, respectively, and every eigenvector orthogonal to both is orthogonal to the all-1 vector; this would establish exactly two main eigenvalues.
[§3.2, Theorem 3.8(v)] The proof of the equality condition in (v) is not complete. The statement says equality holds when ∗ = S and Σ is antibalanced, but the proof only observes that equality is obtained "for example" for T_S(-G). To prove the claimed implication, the argument must show that for every antibalanced Σ a minimum vertex cover of Σ yields a balancing set of vertices in T_S(Σ) of size τ; as written, the example does not establish the general statement.

minor comments (5)

[§4.1, Theorem 4.1 proof] There are two typographical errors in the block-determinant calculation: the bottom-right block xI - 2I + BB^T should be xI - 2I + B^T B, and the expression "(x - k - 1)B^T + B^TBB^T" should read "(x - r - 1)B^T + B^TBB^T". The displayed formulas are correct after these corrections.
[§4.1, Corollary 4.2 proof] The proof of part (i) contains a garbled interval expression: "[1/2(r-2-f2(λ_n)), 1/2(r-2+f1(λ_n))]" should be [f2(λ_n), f1(λ_1)] to match the statement. The argument is otherwise correct.
[§4.1, Theorem 4.1] The phrase "eigenvalues ... are 2 with multiplicity (r/2 - 1)n" should be read as a multiset union, because a root of the displayed quadratic can coincide with 2 (or -2). Adding a sentence to this effect would prevent a possible multiplicity confusion.
[§3.1, Theorem 3.6 proof] The proof of Theorem 3.6 is correct but briefly confusing: the sentence about type (a) triangles says "t− negative triangles for TS(Σ)", which is correct, but the immediately preceding sentence about line-graph triangles could mislead the reader into thinking type (a) triangles are the ones transformed by LS. Separating the discussion of induced-root triangles from line-graph triangles would improve clarity.
[§2.2, Theorem 2.4(iv)] The claim "Each edge of the line graph is in only one vertex clique" should be qualified in the presence of digons, since Remark 2.2 explicitly allows multiple edges. In the reduced matrix definition, digons may cancel, but the combinatorial definition can create an edge that lies in two vertex cliques when two parallel edges share both endpoints.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the spectral derivation is self-contained.

full rationale

Theorem 4.1 derives the spectra of both total signed graphs directly from the incidence identity BB^T = D_G - A_Sigma and the definitional identities A_LC = 2I - B^T B and A_LS = B^T B - 2I, followed by a block-determinant reduction. No fitted parameter is introduced, no normalization is chosen to force the result, and the target spectrum is not assumed as an input. The cited external results (Cvetkovic's total-graph proof, Cartesian-product spectra, equitable-partition theory) are used as tools, not as containers of the paper's formulas. The self-citations define the line graph and incidence-matrix framework, but the load-bearing algebra is verified in the paper itself. The proof's displayed block determinant contains a dimension typo (the bottom-right block is printed as xI - 2I + BB^T, which has the wrong size and should be xI - 2I + B^T B), but correcting it reproduces the stated eigenvalues by elementary row/column operations; a typographical error is not circularity. Theorem 2.3's use of [13] is supported by an independent orientation-based proof, and Theorem 4.4's equitable-partition step is standard and additionally cited to [6] and [1]. I find no self-definitional, fitted-input, self-citation-chain, or ansatz-smuggling circularity in the claimed derivation chain.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The paper has no free parameters. Its dependencies are standard results in signed graph theory, including switching invariance of invariants, the incidence matrix identity BB^T = D_G - A_Σ, Cartesian product spectra, and the quotient matrix theory for main eigenvalues. The two total graph variants T_C and T_S are explicitly constructed definitions, not hidden postulates.

assumptions (5)

standard math Switching equivalence preserves balance, frustration index and frustration number.
Used throughout Section 3, e.g., to justify treating T*(Σ) up to switching; cited from Zaslavsky [14].
standard math For an oriented signed graph satisfying (O1)-(O3), B B^T = D_G - A_Σ and A_LC = 2I - B^T B.
Central to Lemmas 3.1, 3.2 and Theorem 4.1; derived in Section 2.
standard math The spectrum of the Cartesian product of signed graphs is the multiset of sums of eigenvalues of the factors.
Used in the proof of Theorem 4.3; cited from Germina et al. [8].
standard math For a matrix with an equitable partition, the main eigenvalues are determined by the quotient matrix.
Used in Theorem 4.4; cited from Stanić [12].
standard math Perron-Frobenius and eigenvalue interlacing imply the least eigenvalue of a signed graph with at least one edge is at most -1.
Used without proof in Corollary 4.2 to sandwich the spectral interval for TS(Σ).

invented entities (2)

Combinatorial total signed graph T_C(Σ)
purpose: New graph construction combining Σ, LC(Σ), and incidences; object of study for balance and spectrum.
Explicitly constructed in Definition 3.1; not a hidden postulate. Its switching stability is proven in Lemmas 3.1-3.2.
Spectral total signed graph T_S(Σ)
purpose: New graph construction based on the spectral line graph; studied for its spectrum and main eigenvalues.
Explicitly constructed in Definition 3.1; the paper proves its switching stability and derives its regular-case spectrum.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Total graph of a signed graph." pith.science (2026). https://pith.science/paper/GLZAHHIT

@misc{pith2026190802001,
  author       = {Pith},
  title        = {Pith review of: Total graph of a signed graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GLZAHHIT}},
  note         = {Machine review of arXiv:1908.02001}
}

read the original abstract

The total graph is built by joining the graph to its line graph by means of the incidences. We introduce a similar construction for signed graphs. Under two similar definitions of the line signed graph, we define the corresponding total signed graph and we show that it is stable under switching. We consider balance, the frustration index and frustration number, and the largest eigenvalue. In the regular case we compute the spectrum of the adjacency matrix of the total graph and the spectra of certain compositions, and we determine some with exactly two main eigenvalues.

Figures

Figures reproduced from arXiv: 1908.02001 by the authors.

**Figure 2.** The combinatorial and the spectral total graphs re [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Atik, On equitable partition of matrices and its appli cations, Linear Multilinear Algebra, 68 (2020) 2143–2156

F. Atik, On equitable partition of matrices and its appli cations, Linear Multilinear Algebra, 68 (2020) 2143–2156

work page 2020
[2]

Belardo, T

F. Belardo, T. Pisanski, S. K. Simi´ c, On graphs whose lea st eigenvalue is greater than −2, Linear Multilinear Algebra, 64 (2016) 1570–1582

work page 2016
[3]

Belardo, S

F. Belardo, S. K. Simi´ c, On the Laplacian coeﬃcients of s igned graphs, Linear Algebra Appl., 475 (2015) 94–113

work page 2015
[4]

D. M. Cardoso, P. Carvalho, P. Rama, S. K. Simi´ c, Z. Stani ´ c, Lexicographic polynomials of graphs and their spectra, Appl. Anal. Discrete Math., 11 (20 17) 258–272

work page
[5]

D. M. Cardoso, M. A. A. de Freitas, E. A. Martins, M. Robbia no, Spectra of graphs obtained by a generalization of the join graph operation, Discrete Ma th., 313 (2013) 733–741

work page 2013
[6]

D. M. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs, Jo hann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995

work page 1995
[7]

Edmonds, E.L

J. Edmonds, E.L. Johnson, Matching: A well-solved class of linear programs, in: M. J¨ unger et al. (Eds.), Combinatorial Optimization (Edmonds Festsc hrift), Springer, Berlin, 2003, pp. 27–30

work page 2003
[8]

K. A. Germina, S. Hameed K, T. Zaslavsky, On products and l ine graphs of signed graphs, their eigenvalues and energy, Linear Algebra Appl., 435 (20 11) 2432–2450. 14

work page

Show all 18 references

[9]

A. J. Hoﬀman, On graphs whose least eigenvalue exceeds −1 − √ 2, Linear Algebra Appl., 16 (1977) 153–165

1977
[10]

Sinha, P

D. Sinha, P. Garg, Balance and consistency of total sign ed graphs. Indian J. Math., 53(1) (2011) 71–81

2011
[11]

Stani´ c, Some bounds for the largest eigenvalue of a s igned graph, Bull

Z. Stani´ c, Some bounds for the largest eigenvalue of a s igned graph, Bull. Math. Soc. Sci. Math. Roumanie, 62(110) (2019) 175–181

2019
[12]

Stani´ c, Main eigenvalues of real symmetric matrice s with application to signed graphs, Czech

Z. Stani´ c, Main eigenvalues of real symmetric matrice s with application to signed graphs, Czech. Math. J., 70 (2020) 1091–1102

2020
[13]

Zaslavsky, Characterizations of signed graphs, J

T. Zaslavsky, Characterizations of signed graphs, J. G raph Theory, 5 (1981) 401–406

1981
[14]

Zaslavsky, Signed graphs, Discrete Appl

T. Zaslavsky, Signed graphs, Discrete Appl. Math., 4 (1 982) 47–74
[15]

Zaslavsky, Signed graph coloring, Discrete Math., 3 9 (1982) 215–228

T. Zaslavsky, Signed graph coloring, Discrete Math., 3 9 (1982) 215–228

1982
[16]

Zaslavsky, Line graphs of switching classes, in Repo rt of the XVIIIth O.S.U

T. Zaslavsky, Line graphs of switching classes, in Repo rt of the XVIIIth O.S.U. Denison Maths Conference (Granville, Ohio, 1984), pp. 2–4, Dept. of Math., Ohio State University, Columbus, Ohio, 1984

1984
[17]

Zaslavsky, Orientation of signed graphs, Eur

T. Zaslavsky, Orientation of signed graphs, Eur. J. Com bin., 12 (1991) 361–375

1991
[18]

Zaslavsky, Matrices in the theory of signed simple gr aphs, in B

T. Zaslavsky, Matrices in the theory of signed simple gr aphs, in B. D. Acharya, G. O. H. Katona, J. Neˇ setˇ ril (Eds.), Advances in Discrete Mathematics and Applications: Mysore 2008, Ramanujan Math. Soc., Mysore, 2010, pp. 207–229. 15

2008

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Atik, On equitable partition of matrices and its appli cations, Linear Multilinear Algebra, 68 (2020) 2143–2156

F. Atik, On equitable partition of matrices and its appli cations, Linear Multilinear Algebra, 68 (2020) 2143–2156

work page 2020

[2] [2]

Belardo, T

F. Belardo, T. Pisanski, S. K. Simi´ c, On graphs whose lea st eigenvalue is greater than −2, Linear Multilinear Algebra, 64 (2016) 1570–1582

work page 2016

[3] [3]

Belardo, S

F. Belardo, S. K. Simi´ c, On the Laplacian coeﬃcients of s igned graphs, Linear Algebra Appl., 475 (2015) 94–113

work page 2015

[4] [4]

D. M. Cardoso, P. Carvalho, P. Rama, S. K. Simi´ c, Z. Stani ´ c, Lexicographic polynomials of graphs and their spectra, Appl. Anal. Discrete Math., 11 (20 17) 258–272

work page

[5] [5]

D. M. Cardoso, M. A. A. de Freitas, E. A. Martins, M. Robbia no, Spectra of graphs obtained by a generalization of the join graph operation, Discrete Ma th., 313 (2013) 733–741

work page 2013

[6] [6]

D. M. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs, Jo hann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995

work page 1995

[7] [7]

Edmonds, E.L

J. Edmonds, E.L. Johnson, Matching: A well-solved class of linear programs, in: M. J¨ unger et al. (Eds.), Combinatorial Optimization (Edmonds Festsc hrift), Springer, Berlin, 2003, pp. 27–30

work page 2003

[8] [8]

K. A. Germina, S. Hameed K, T. Zaslavsky, On products and l ine graphs of signed graphs, their eigenvalues and energy, Linear Algebra Appl., 435 (20 11) 2432–2450. 14

work page