Pith. sign in

REVIEW 4 major objections 6 minor 16 references

Connected signed graphs with given inertia indices and given girth

T0 review · 4 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read For every connected signed graph, the negative inertia index is at least half the girth minus one, and the paper classifies every graph that attains this bound.

desk verdict The signed-graph lower bound on negative inertia in terms of girth is clean and correct; the equality characterizations are more conditional than the paper admits, leaning on an external classification and several unexpanded case checks. read the letter →

arxiv 2505.08539 v1 pith:IASUPTHC submitted 2025-05-13 math.SP

Beiyan Liu , Fang Duan This is my paper · ORCID
classification math.SP MSC 05C50
keywords signedgraphsinertiaindicesnegativeindexpositivenullitygirthcompletemultipartite
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

For any connected signed graph whose shortest cycle has length $g$, the paper proves that the number of negative eigenvalues of the adjacency matrix is at least $\lceil g/2\rceil - 1$. It then lists exactly which signed graphs achieve this lower bound: signed cycles of certain balance types determined by $g \bmod 4$, positive complete bipartite graphs, and signed complete multipartite graphs whose signed triangles are all unbalanced. The paper also classifies the next level, $i_-(\Gamma) = \lceil g/2\rceil$ for $g \ge 4$, and uses sign reversal to obtain matching statements for the positive inertia index and for the nullity. The upshot is that a signed graph's shortest cycle forces a minimal amount of negative spectral content, and the extremal graphs are rigid enough to be enumerated.

What carries the argument

The argument turns on three tools. Lemma 2.4 supplies explicit formulas for the negative inertia index of a signed cycle and path in terms of length modulo $4$ and whether the cycle is balanced; Lemma 2.3 transfers that bound from a shortest cycle to the entire graph by interlacing; Lemma 2.5 says deleting a pendant vertex together with its neighbor lowers both inertia indices by exactly $1$, which forces any extra structure to contribute too many negative eigenvalues. For the equality cases, Lemma 2.6, the classification of signed graphs with $i_- = 1$, is what identifies the complete bipartite and complete multipartite graphs appearing in Theorem 3.1.

What would settle it

Take a balanced $5$-cycle and attach one leaf to a cycle vertex. Lemma 2.5 together with Lemma 2.4 predicts negative inertia index $\lfloor 4/2\rfloor + 1 = 3$, which exceeds the Theorem 3.1 lower bound of $2$ for girth $5$. Directly diagonalizing the adjacency matrix of this six-vertex signed graph either confirms $3$, supporting the equality classification, or returns $2$, which would falsify it.

Watch

Extended reading notes

Core claim

The central result is Theorem 3.1: if $\Gamma$ is connected, has at least one cycle, and $g$ is its girth, then $i_-(\Gamma) \ge \lceil g/2\rceil - 1$. Equality holds exactly when $\Gamma$ is switching-equivalent to a signed cycle $C_g^{\sigma}$ that is balanced for $g \equiv 0,1 \pmod 4$ or unbalanced for $g \equiv 2,3 \pmod 4$, or to a positive complete bipartite graph $(K_{n_1,n_2},+)$, or to a signed complete multipartite graph $K^{\sigma}_{n_1,\ldots,n_l}$ with $l \ge 3$ whose signed triangles are all unbalanced. The proof restricts attention to a shortest cycle, uses interlacing to lift the cycle's negative-inertia bound to the whole graph, and then rules out extra vertices unless the graph is one of the listed multipartite forms. The same machinery, with the sign reversed, yields the analogous positive-inertia statements, and combining the two gives the nullity bound $\eta(\Gamma) \le n - g + 2$ with equality characterized.

Load-bearing premise

The whole bound rests on the quoted formulas for the negative inertia index of signed cycles and paths in Lemma 2.4; if those congruence-dependent formulas were off by one in some residue class, the lower bound and every listed equality case would have to be reworked.

Editorial extensions

If this is right

  • The lower bound is sharp for every girth: for each $g$ there are signed cycles and complete multipartite examples attaining $i_-(\Gamma) = \lceil g/2\rceil - 1$.
  • For girth at least $4$, the paper enumerates all connected signed graphs with $i_-(\Gamma) = \lceil g/2\rceil$, so the two smallest possible negative inertia values are completely understood.
  • Because negating all edge signs swaps positive and negative inertia, the identical classification holds for the positive inertia index $i_+(\Gamma)$.
  • The nullity of a connected signed graph of order $n$ and girth $g$ is at most $n - g + 2$, and equality is characterized by balanced or unbalanced shortest cycles of certain lengths or by positive complete bipartite graphs.
  • The equality dichotomy, either a shortest cycle alone or a complete multipartite graph, shows that minimal negative inertia is a strong structural constraint.

Reading between the lines

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

  • The mod-$4$ dependence of the equality cases mirrors the eigenvalue interlacing of cycles, so a natural test is whether the same lower bound survives for weighted signed graphs when the weighted cycle formulas obey the same congruence pattern.
  • The classification could serve as a fast certificate for minimal negative inertia: verify the girth and check the local extremal forms instead of computing the full spectrum.
  • A natural next step is to push the same two-step argument, shortest-cycle interlacing plus pendant-vertex deletion, to higher values of $i_-(\Gamma)$, expecting finite extremal families for each fixed excess above the lower bound.
  • The nonexistence of signed graphs with the mixed inertia pair $(\lceil g/2\rceil - 1, \lceil g/2\rceil)$ noted in Section 5 may reflect a parity obstruction worth isolating for girth $3$ separately.
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.

Referee Report

4 major / 6 minor

Summary. The paper studies the relation between the girth g of a connected signed graph Gamma and its negative inertia index i_-(Gamma). It proves the lower bound i_-(Gamma) >= ceil(g/2) - 1, characterizes the equality cases in Theorem 3.1 as signed cycles of certain balance classes and as positive complete bipartite or complete multipartite signed graphs with only unbalanced triangles, and then gives classifications of connected signed graphs with i_-(Gamma) = ceil(g/2) for g >= 4, separating canonical signed unicyclic graphs from non-canonical ones. The same framework is applied to the positive inertia index by negation, and the paper concludes with characterizations of connected signed graphs with given nullity and given girth.

Significance. If the results are correct, the paper provides a natural signed analogue of known unsigned girth-inertia bounds and a useful extremal classification. The proof of the lower bound is clean and elegant: it uses interlacing (Lemma 2.3), the signed-cycle inertia formulas (Lemma 2.4), and the pendant-vertex reduction (Lemma 2.5). The paper also makes a reasonable structural split between canonical unicyclic graphs and the general case. However, the classification half rests on many unexpanded case checks and on an external classification lemma (Lemma 2.6 from [4]), so the extremal characterizations are currently under-verified even though they are plausible. No machine-checked proofs or reproducible code are supplied; verification depends entirely on the printed arguments and cited references.

major comments (4)
  1. [Theorem 3.4, Subcase 2] The exclusion of the g = 6 unbalanced case is not self-contained. After stating that there is exactly one negative edge among x1y1, x1x2, and x2y2, the proof asserts that {x1,x2,y1,y2,y3,y4} induces a balanced 6-cycle, but it does not specify the vertex order of that cycle or compute its sign product. Because this assertion is what rules out the subcase, the parity computation must be written out explicitly; with the natural cycle x1-x2-y2-y3-y4-y1-x1, the sign product is -sigma(x1x2)sigma(x2y2)sigma(y1x1), which is indeed positive when exactly one of the three outside edges is negative, but the printed text leaves this to the reader.
  2. [Theorem 3.3, Case 1 and Theorem 3.4, Claims 1-3] Several crucial exclusions are asserted via 'by a simple operation' or 'by a simple observation' without displaying the relevant induced subgraphs or the inertia computations. For example, in the proof of Theorem 3.3, Case 1, the claim that a vertex x in N1(v,C5) can only be adjacent to y5, and the consequent lower bound i_-(Gamma[V(Gamma1) union {x}]) = 4, are not demonstrated. Similarly, in Theorem 3.4, Claim 2, the bound l <= floor(g/4) and the derived cycle bound are not justified. These steps are load-bearing for the classifications for g = 5 and g = 6; the authors should provide a table of the induced subgraphs with their inertia indices, or give full derivations for these claims.
  3. [Theorem 4.1(2)] The equality condition 'Gamma ~ (K^sigma_{n1,n2,...,nl}, +)' is ambiguous: the superscript sigma on K and the trailing '+', which in the paper's notation means the all-positive signature, are contradictory. The intended family is almost certainly the all-positive complete multipartite graph (K_{n1,...,nl}, +), with l = 2 allowed for girth 4 and l >= 3 for girth 3. The statement should specify the signature and the range of l explicitly; as printed, the theorem cannot be verified without guesswork.
  4. [Section 5, first paragraph] The sentence 'Unfortunately, there exists no signed graphs satisfying these conditions' asserts a nonexistence result with no proof. This nonexistence is used to justify the case split that leads to Theorems 5.2 and 5.3. The claim should either be proved directly, or derived explicitly by intersecting the equality cases of Theorems 3.1 and 3.4 with those of Theorems 4.1 and 4.3. As written, the 'if and only if' characterizations in Section 5 are not fully justified.
minor comments (6)
  1. [Section 3, definition of pendant star] The definition of a pendant star is hard to reconcile with the definition of a canonical signed unicyclic graph; the text should say explicitly that the center of the star is a cycle vertex and that the parameters l_i in Theorem 3.2 count the internal vertices of the cycle segments after removing the centers of the pendant stars.
  2. [Global] There are numerous typographical and grammatical errors, including 'it's girth', 'Denoted by g', 'a balance 6-cycle', and 'It suffice'; these should be corrected throughout.
  3. [Figures 3-5] The graphs B(4,3,4), B(4,4,4), H_i, and Gamma_i are only described in figures; please add explicit adjacency or sign descriptions in the text or an appendix so that the 'simple operation' checks can be reproduced without interpreting the drawings.
  4. [Theorems 4.1-4.3] The positive-inertia theorems are stated without proofs; a short paragraph explaining that they follow from the negation operation, including the modular-four parity changes, would significantly improve verifiability.
  5. [Theorem 3.2(2)-(3)] The phrase 'exactly one path between any two major vertices of V(C_g) has even order' should be rephrased as 'among the k cycle segments between consecutive major vertices, exactly one has even order', to avoid the ambiguity caused by the two paths that exist between any two vertices on a cycle.
  6. [Lemma 2.6] The typeset statement of Lemma 2.6 appears to be missing the switching-equivalence symbol; please check the PDF rendering so that the statement is unambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: self-citations are published lemmas, not the target result.

full rationale

The central derivation is not circular. The lower bound in Theorem 3.1 chains the induced-shortest-cycle observation with Lemma 2.3 (interlacing) and Lemma 2.4, where Lemma 2.4 is an external formula for negative inertia indices of signed cycles and paths. The equality half for the pure-cycle case follows directly from Lemma 2.4. For the non-cycle equality case, the proof first uses Lemmas 2.7 and 2.8 to force g = 3 or 4 and i_-(Γ) = 1, and only then applies Lemma 2.6, a published classification of all signed graphs with negative inertia index one. The assumption of Lemma 2.6 is i_- = 1, not the girth statement under proof, so the conclusion is not built into the input. Corollary 2.1 and the girth-4 cases use Theorem 2.2 from the same published paper by Duan and Yang, again as an external classification lemma rather than as a restatement of the theorem being proved. Theorem 3.2 adapts the method of the authors' earlier paper [5], but its proof is re-run in the text using Lemma 2.5 and Lemma 2.4. Sections 4 and 5 are formal consequences via negation and the identity i_+ + i_- + η = n. No fitted parameters are introduced, no predicted quantity is the definitional rename of an input, and no load-bearing step reduces by construction to a self-citation. The paper does rely on several external classifications and summarizes some routine inertia checks, but this affects completeness of exposition rather than circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces no free parameters and no new entities. The central claim rests on standard theorems (Sylvester's law, interlacing) and a set of published lemmas from the signed-graph literature, several of which come from the authors' own prior work. No ad hoc assumptions invented for this paper appear.

assumptions (7)
  • standard math Sylvester's law of inertia (Lemma 2.1): congruent real symmetric matrices have the same inertia.
    Used throughout for congruence transformations in Theorems 3.3 and 3.4.
  • standard math Interlacing theorem (Theorem 2.1): eigenvalues of a principal submatrix interlace those of the full matrix.
    Used to prove Lemma 2.3, which gives monotonicity of inertia indices under induced subgraphs.
  • domain assumption Lemma 2.4 (from [14,15,16]): inertia formulas for signed cycles and paths as functions of n mod 4.
    The main lower bound in Theorem 3.1 evaluates i_-(C^sigma_g) with these formulas. Not re-derived in this preprint.
  • domain assumption Lemma 2.5 (from [15]): deleting a pendant vertex and its neighbor reduces both i_+ and i_- by one in signed graphs.
    Used repeatedly in Lemmas 2.7-2.8 and in the equality characterizations of Theorems 3.2-3.4.
  • domain assumption Lemma 2.6 (from [4]): classification of all signed graphs with i_- = 1.
    Used to settle the girth 3 and 4 equality cases in Theorem 3.1 and Corollary 2.1.
  • domain assumption Theorem 2.2 (from [4]): classification of connected triangle-free reduced signed graphs with i_- = 2.
    Used to derive Corollary 2.1, which feeds into Theorems 3.3 and 3.4 for girth 4.
  • domain assumption Lemma 1.1 (from [7]): an unbalanced signed unicyclic graph is switching equivalent to one with exactly one negative edge on the cycle.
    Used in the case analyses for girth 5 and 6 in Theorems 3.3 and 3.4 to fix the sign pattern of the unique cycle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Connected signed graphs with given inertia indices and given girth." pith.science (2026). https://pith.science/paper/IASUPTHC

@misc{pith2026250508539,
  author       = {Pith},
  title        = {Pith review of: Connected signed graphs with given inertia indices and given girth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IASUPTHC}},
  note         = {Machine review of arXiv:2505.08539}
}
abstract

Suppose that $\Gamma=(G, \sigma)$ is a connected signed graph with at least one cycle. The number of positive, negative and zero eigenvalues of the adjacency matrix of $\Gamma$ are called positive inertia index, negative inertia index and nullity of $\Gamma$, which are denoted by $i_+(\Gamma)$, $i_-(\Gamma)$ and $\eta(\Gamma)$, respectively. Denoted by $g$ the girth, which is the length of the shortest cycle of $\Gamma$. We study relationships between the girth and the negative inertia index of $\Gamma$ in this article. We prove $i_{-}(\Gamma)\geq \lceil\frac{g}{2}\rceil-1$ and extremal signed graphs corresponding to the lower bound are characterized. Furthermore, the signed graph $\Gamma$ with $i_{-}(\Gamma)=\lceil\frac{g}{2}\rceil$ for $g\geq 4$ are given. As a by-product, the connected signed graphs with given positive inertia index, nullity and given girth are also determined, respectively.

Figures

Figures reproduced from arXiv: 2505.08539 by the authors.

Figure 1
Figure 1. The signed graphs G σ 1 and G σ 2 Corollary 2.1. Let Γ be a connected signed graph with girth g = 4. (1) If Γ contains an unbalanced 4-cycle, then i−(Γ) = 2 if and only if Γ can be obtained from Gσ 1 , Gσ 2 or unbalanced Cσ 4 by adding twin vertices; (2) If Γ contains no unbalanced 4-cycle, then i−(Γ) = 2 if and only if Γ can be obtained from Pσ 4 , Pσ 5 , balanced Cσ 5 or unbalanced Cσ 6 by adding twin vertices. Pr… view at source ↗
Figure 2
Figure 2. The canonical signed unicyclic graphs K σ 1 and K σ 2 Theorem 3.2. Let Γ be a canonical signed unicyclic graph with girth g and the unique cycle Cσ g . Then, the following statements hold: (1) If Γ is a cycle, then i−(Γ) = ⌈ g 2 ⌉ if and only if Γ  C σ g , where Cσ g is balanced and g ≡ 2, 3(mod 4), or unbalanced and g ≡ 0, 1(mod 4); (2) If Γ is not a cycle and g ≡ 1, 3(mod 4), then i−(Γ) = ⌈ g 2 ⌉ if and only if Γ… view at source ↗
Figure 3
Figure 3. The signed graphs (B(4, 3, 4), σ), (B(4, 4, 4), σ1), (B(4, 4, 4), σ2), H σ 4 , (B(4, 3, 5), σ) and (B(4, 4, 5), σ) Then, k = [l1 − 2i−(P σ l1 )] + [l2 − 2i−(P σ l2 )] + · · · + [lk − 2i−(P σ lk )]. By a similar discussion as Case 1, i−(Γ) = ⌈ g 2 ⌉ holds if and only if all of l1, . . . , lk are odd. It follows the desired conclusion. □ For those who are not canonical signed unicyclic graphs, we can only characterize… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The signed graphs H σ 1 , H σ 2 , (H3, +), H σ1 4 , (B(4, 3, 5), σ1), (B(4, 4, 5), σ1) and (B(4, 4, 5), σ2). Applying elementary congruence matrix operations on A((B(4, 4, 4), σ1)), we get that A ((B(4, 4, 4), σ1)) is congruent to B =  …
Figure 5
Figure 5. Figure 5: The signed graphs Γ1, Γ2, Γ3, (B(4, 3, 4), +), Γ4, H σ2 4 , H σ 5 , (B(4, 3, 5), σ2), (B(5, 2, 5), +), (B(5, 5, 5), +), (B(5, 3, 5), σ) and (B(5, 4, 5), σ). (3) (B(4, 3, 4), +), Γ4, Hσ2 4 , Hσ 5 , (B(4, 3, 5), σ2), (B(5, 2, 5), +), (B(5, 5, 5), +), (B(5, 3, 5), σ) and …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 11 canonical work pages

  1. [4]

    Duan, Y .H

    F. Duan, Y .H. Yang, Triangle-free signed graphs with small negative inertia index, Discrete Applied Mathematics, 357(2024) 135-142. https: //doi.org/10.1016/j.dam. 2024.06.012

    doi:10.1016/j.dam 2024

  2. [1]

    Belardo, S

    F. Belardo, S. Cioab´a, J. Koolen, J.F. Wang, Open problem in the spectral theory of signed graphs, Art Discrtete Applied Mathematics 1 (2018) 2-24. https://doi.org/ 10.48550/ arXiv.1907.04349

    arXiv doi:10.48550/arxiv.1907.04349 2018

  3. [2]

    Brunetti, Z

    M. Brunetti, Z. Stani´c, Ordering signed graphs with large index, Ars Mathematica Contemporanea, 22(2022) P4.05. https://doi.org/10.26493/1855-3974.2714.9b3

    work page arXiv 2022

  4. [3]

    Cvetkovi ´c, M

    D. Cvetkovi ´c, M. Doob, H. Sachs, Spectra of Graphs: Theory and Application. Academic Press, New York, 1980

    work page 1980

  5. [5]

    Duan, Characterizing the negative inertia index of connected graphs in terms of their girth, Discrete Mathematics, 347(2024) 113997

    F. Duan, Characterizing the negative inertia index of connected graphs in terms of their girth, Discrete Mathematics, 347(2024) 113997. https: //doi.org/10.1016/j. disc.2024.113997

    arXiv 2024

  6. [6]

    F. Duan, Q. Yang, On graphs with girth g and positive inertia index of ⌈ g 2⌉-1 and⌈ g 2⌉, Linear Algebra and its Applications, 683(2024) 98-110. https: //doi.org/ 10.1016/j.laa.2023.12.001

    work page doi:10.1016/j.laa.2023.12.001 2024

  7. [7]

    Y .Z. Fan, Y . Wang, Y . Wang, A note on the nullity of unicyclic signed graphs, Lin- ear Algebra and its Applications, 438(2013) 1193-1200. https: //doi.org/10.1016/j. laa.2012.08.027

    doi:10.1016/j 2013

  8. [8]

    Haemers, H

    W.H. Haemers, H. Topcu, On signed graphs with at most two eigenvalues un- equal to±1, Linear Algebra and its Applications, 670(2023) 68-77. https: //doi.org /10.1016/j.laa.2023.04.001

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

Show all 16 references
  1. [9]

    Harary, On the notion of balanced in a signed graph, Michigan Math

    F. Harary, On the notion of balanced in a signed graph, Michigan Math. J. 2 (1) (1953) 143-146. https://doi.org/10.1016/ j.laa.2023.04.001

    1953

  2. [10]

    Horn, C.R

    R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, 1985. 16

    1985

  3. [11]

    Hou, J.S

    Y .P. Hou, J.S. Li, Y .L. Pan, On the Laplacian eigenvalues of signed graphs, Linear Multilinear Algebra, 51(1)(2003) 21-30. https: //doi.org/10.1080/03081080310000 53611

    2003 doi

  4. [12]

    Oboudi, Characterization of graphs with exactly two non-negative eigenvalues, Ars Mathematica Contemporanea, 12(2017) 271-286

    M.R. Oboudi, Characterization of graphs with exactly two non-negative eigenvalues, Ars Mathematica Contemporanea, 12(2017) 271-286. https://doi.org/10.26493/1855-3974.1077.5b6

    2017

  5. [13]

    Q. Wu, Y . Lu, B.S. Tam, On connected signed graphs with rank equal to girth, Linear Algebra and its Applications 651 (2022) 90-115. https: //doi.org/10.1016/ j.laa.2022.06.019

    2022

  6. [14]

    G. H. Yu, L. H. Feng, Q. W. Wang, Bicyclic graphs with small positive in- dex of inertia, Linear Algebra and its Applications, 438 (2013) 2036-2045. https://doi.org/10.10 16/j.laa.2012.09.031

    2013

  7. [15]

    G.H. Yu, X.D. Zhang, L.H. Feng, The inertia of weighted unicyclic graphs, Lin- ear Algebra and its Applications, 44(2014) 130-152. https: //doi.org/10.1016/j.laa .2014.01.023

    2014 doi

  8. [16]

    G.H. Yu, L.H. Feng, Q.W. Wang, A. Ili´c, The minimal positive index of inertia of unicyclic signed graphs, Ars Combinatoria, 117(2014) 245-255

    2014

Pith tools

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