Energy of signed graphs and the vertex cover number

Abstract

The energy ℰ(Γ) of a signed graph Γ=(G,σ) is the sum of the absolute values of the eigenvalues of its adjacency matrix A(Γ). In this article, we prove that ℰ(Γ)≥ 2τ(G), where τ(G) is the vertex cover number of G. The case of unsigned graphs, a 1980s conjecture proved only recently, is a special case of this result. Moreover, we completely characterize the equality case: equality holds if and only if every connected component of Γ is switching equivalent to an \emph{additive rook graph} Rook_N(a,b). This graph is constructed on an N× N board with a_i+b_j vertices on square (i,j). Two vertices are joined by a positive edge if they share only a row, and by a negative edge if they share only a column. As consequences, we obtain a balanced/antibalanced trichotomy for the extremal signed graphs and deduce the characterization of the extremal unsigned graphs. Finally, an example shows that the bound does not extend to the Hermitian adjacency matrices of mixed graphs or to complex unit gain graphs.

Weak and strong Lefschetz properties for vertex cover Artinian algebras associated to graphs
Trung Chau, Tran Quang Hoa, Dang Thi Kieu Uyen
arXiv29 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Sharp Bounds on Torsional Rigidity of Metric Graphs with Signed Delta-Vertex Strengths
Sedef Özcan
arXiv28 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEs Combinatorics & discrete mathematicsarXiv
Graphs with Large Vertex–Edge Roman {2}-Domination Number
Ahlam Almulhim
Mathematics20 Oct 2026Peer-reviewedCC BY 4.0General mathematicsCrossref
Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
Saieed Akbari, Arash Beikmohammadi
arXiv7 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
On Eternal Connected Vertex Cover
Rajat Adak, Saraswati Girish Nanoti
arXiv30 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{samanta2026energy,
  title = {{Energy of signed graphs and the vertex cover number}},
  author = {Aniruddha Samanta and Deepshikha and Kinkar Chandra Das},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.24146},
  eprint = {2610.24146},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.24146},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Energy of signed graphs and the vertex cover number
AU  - Aniruddha Samanta
AU  - Deepshikha
AU  - Kinkar Chandra Das
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.24146
UR  - https://arxiv.org/abs/2610.24146
AB  - The energy ℰ(Γ) of a signed graph Γ=(G,σ) is the sum of the absolute values of the eigenvalues of its adjacency matrix A(Γ). In this article, we prove that ℰ(Γ)≥ 2τ(G), where τ(G) is the vertex cover number of G. The case of unsigned graphs, a 1980s conjecture proved only recently, is a special case of this result. Moreover, we completely characterize the equality case: equality holds if and only if every connected component of Γ is switching equivalent to an \emph{additive rook graph} Rook_N(a,b). This graph is constructed on an N× N board with a_i+b_j vertices on square (i,j). Two vertices are joined by a positive edge if they share only a row, and by a negative edge if they share only a column. As consequences, we obtain a balanced/antibalanced trichotomy for the extremal signed graphs and deduce the characterization of the extremal unsigned graphs. Finally, an example shows that the bound does not extend to the Hermitian adjacency matrices of mixed graphs or to complex unit gain graphs.
ER  -

Abstract

Related

Cite