betaFeedback

WorksMathematics

Energy of signed graphs and the vertex cover number

Abstract

The energy E(Γ)\mathcal{E}(Γ) of a signed graph Γ=(G,σ)Γ=(G,σ) is the sum of the absolute values of the eigenvalues of its adjacency matrix A(Γ)A(Γ). In this article, we prove that E(Γ)≥2τ(G)\mathcal{E}(Γ)\geq 2τ(G), where τ(G)τ(G) is the vertex cover number of GG. 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 additive rook graph \Rook_N(a,b). This graph is constructed on an N×NN\times N board with ai+bja_i+b_j vertices on square (i,j)(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.

Introduction

Throughout this article, GG denotes a simple undirected graph with vertex set V(G)V(G) (or simply VV) and edge set E(G)E(G). If two vertices uu and vv are adjacent, we write u∼vu\sim v and denote the edge between them by uvuv. Let λ1≥λ2≥⋯≥λn\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n be the eigenvalues of the adjacency matrix A(G)A(G). The energy of GG is

E(G)=∑i=1n∣λi∣.\mathcal{E}(G)=\sum_{i=1}^{n}|\lambda_i|.

Gutman introduced graph energy in 1978 [22], motivated by its connection with the total π\pi-electron energy of conjugated hydrocarbons. Since then it has been studied extensively; see [26, 3, 17, 37, 14, 13, 16] and the references therein. Because the energy depends on the whole spectrum, it can rarely be computed in closed form. Much of the literature is therefore devoted to bounding it in terms of simpler graph parameters, such as the number of vertices or edges, the chromatic number, the matching number and the vertex cover number, see [2, 32, 43, 23].

A set S⊆V(G)S \subseteq V(G) is a vertex cover of GG if every edge of GG has at least one end in SS. The vertex cover number τ(G)\tau(G) is the size of a minimum vertex cover. A set of vertices is independent if no two of its vertices are adjacent, and the independence number α(G)\alpha(G) is the size of a maximum independent set. The complement of a vertex cover is an independent set and vice versa, so τ(G)+α(G)=n\tau(G) + \alpha(G) = n.

In the 1980s, Fajtlowicz [19, 18] conjectured, on the basis of his computer program Graffiti, that every graph GG satisfies

E(G)≥2τ(G);(1)\mathcal{E}(G) \ge2\tau(G); \tag*{(1)}

see also [5 Conjecture 543] and [29]. The conjecture attracted considerable attention. Wang and Ma [40] proved the weaker bound E(G)≥2τ(G)−2c(G)\mathcal{E}(G) \ge2\tau(G) - 2c(G), where c(G)c(G) is the number of odd cycles of GG, and Samanta and Kannan [36] extended it to complex unit gain graphs. Wong, Wang and Chu [42] proved E(G)≥2μ(G)\mathcal{E}(G) \ge2\mu(G) in terms of the matching number μ(G)\mu(G), with analogues for oriented graphs [39], mixed graphs [41] and complex unit gain graphs [27]. Since τ(G)≥μ(G)\tau(G) \ge\mu(G), inequality (1) improves this last bound. Inequality (1) was verified for several classes of graphs in [4, 34], and Abiad, Coutinho, Juliano and Reijnders [1] obtained further partial results using semidefinite programming. The conjecture was finally settled by Kumar and Pragada [25], who proved that (1) holds for every graph. Shortly afterwards, Mojallal [31] determined all graphs attaining equality.

It is natural to ask whether (1) survives when the edges carry weights. A signed graph [44] Γ=(G,σ)\Gamma= (G,\sigma) consists of an underlying graph GG together with a signature σ:E(G)→{−1,+1}\sigma: E(G) \to\{-1,+1\}. Its adjacency matrix A(Γ)A(\Gamma) is a symmetric ∣V∣×∣V∣|V| \times|V| matrix, defined by

(u,v)-th entry of A(Γ)=A(Γ)uv={σ(uv),if u∼v,0,otherwise,(u,v)\text{-th entry of } A(\Gamma) = A(\Gamma)_{uv} = \begin{cases} \sigma(uv), & \text{if } u \sim v,\\ 0, & \text{otherwise,} \end{cases}

and its energy E(Γ)\mathcal{E}(\Gamma) is the sum of the absolute values of the eigenvalues of A(Γ)A(\Gamma). An unsigned graph is the special case in which every edge is positive, that is, A(G)=A((G,+1))A(G) = A((G,+1)). Signed graphs are in turn a special case of the complex unit gain graphs (T-gain graphs) introduced by Reff [33], whose edges carry complex numbers of modulus one. Switching at a vertex set UU reverses the sign of every edge with exactly one end in UU; it does not change the spectrum. A signed graph is balanced if it can be switched to the all-positive signature, and antibalanced if (G,−σ)(G,-\sigma) is balanced.

In this article, we prove that (1) holds for every signed graph and we completely characterize the case of equality. The extremal signed graphs are described by the following family. Let N≥1N \ge1 and let a=(a1,…,aN)a=(a_1,\ldots,a_N) and b(b1,…,bN)b(b_1,\ldots,b_N) be vectors of nonnegative integers. The additive rook graph Rook⁡N(a,b)\operatorname{Rook}_N(a,b) is the signed graph built on an N×NN \times N board with ai+bja_i+b_j vertices on square (i,j)(i,j), in which two vertices are joined by a positive edge if they lie in the same row but in different columns, and by a negative edge if they lie in the same column but in different rows. All other pairs of vertices are non-adjacent. Our main result is the following.

Theorem 0.1. Let Γ=(G,σ)\Gamma=(G,\sigma) be a signed graph with vertex cover number τ(G)\tau(G). Then

E(Γ)≥2τ(G).(2)\mathcal{E}(\Gamma) \ge2\tau(G). \tag*{(2)}

Equality holds if and only if every connected component of Γ\Gamma is switching equivalent to an additive rook graph Rook⁡N(a,b)\operatorname{Rook}_{N}(a,b).

Theorem 0.1 reveals features that do not appear in the unsigned case. The class of underlying graphs that attain equality is strictly larger than for unsigned graphs, and equality is attained by some signed graphs that are neither balanced nor antibalanced. This leads to a balanced/antibalanced trichotomy for the extremal signed graphs. Restricting Theorem 0.1 to unsigned graphs, we recover Mojallal’s characterization [31]. On the other hand, the bound does not extend further: we give an example showing that (2) fails for the Hermitian adjacency matrices of mixed graphs and for T\mathbb{T}-gain graphs.

The article is organized as follows. § 2 collects the notation, definitions and preliminary results used throughout. In § 3, we introduce additive rook graphs and establish their basic properties. § 4 contains the proof of (2). § 5 characterizes equality in two steps: we first show that every additive rook graph attains equality, and then prove the converse, namely that every signed graph attaining equality is switching equivalent to a disjoint union of additive rook graphs. Finally, in § 7, we state Mojallal’s theorem in full and deduce it from Theorem 0.1, and we present an example showing that the bound cannot be extended to Hermitian adjacency matrices of mixed graphs or to T\mathbb{T}-gain graphs.

Preliminaries

Throughout this article, GG denotes a finite simple undirected graph with vertex set V(G)V(G) and edge set E(G)E(G). We put n=∣V(G)∣n=|V(G)| and m=∣E(G)∣m=|E(G)|. The edge joining two vertices uu and vv is written uvuv, and we write u∼vu\sim v when uv∈E(G)uv\in E(G). For a vertex vv, the set N(v)={u∈V(G):u∼v}N(v)=\{u\in V(G):u\sim v\} is its neighbourhood, N[v]=N(v)∪{v}N[v]=N(v)\cup\{v\} is its closed neighbourhood, and dv=∣N(v)∣d_v=|N(v)| is its degree. For a signed graph Γ=(G,σ)\Gamma=(G,\sigma), every purely graph-theoretic notion is taken from the underlying graph GG. So the vertex covers and the independent sets of Γ\Gamma are those of GG, and we write τ(Γ)=τ(G)\tau(\Gamma)=\tau(G) and α(Γ)=α(G)\alpha(\Gamma)=\alpha(G). For U⊆V(G)U\subseteq V(G), the signed graph induced by Γ\Gamma on V(G)∖UV(G)\setminus U is denoted by Γ−U\Gamma-U, and its edges keep their signs from Γ\Gamma.

If the rows and columns of a matrix MM are indexed by V(G)V(G), then the (u,v)(u,v)-th entry of MM is written MuvM_{uv}. The adjacency matrix A(Γ)A(\Gamma) is the real symmetric matrix with A(Γ)uv=σ(uv)A(\Gamma)_{uv}=\sigma(uv) if u∼vu\sim v, and A(Γ)uv=0A(\Gamma)_{uv}=0 otherwise. If λ1≥⋯≥λn\lambda_1\ge\cdots\ge\lambda_n are the eigenvalues of A(Γ)A(\Gamma), the energy of Γ\Gamma is defined as E(Γ)=∑k=1n∣λk∣\mathcal{E}(\Gamma)=\sum_{k=1}^{n}|\lambda_k|.

A switching function is a map ζ:V(G)→{1,−1}\zeta:V(G)\to\{1,-1\}. It turns Γ=(G,σ)\Gamma=(G,\sigma) into the signed graph Γζ=(G,σζ)\Gamma^\zeta=(G,\sigma^\zeta), where σζ(uv)=ζ(u)σ(uv)ζ(v)\sigma^\zeta(uv)=\zeta(u)\sigma(uv)\zeta(v) for every edge uvuv. We then say that Γ\Gamma and Γζ\Gamma^\zeta are switching equivalent, and write Γ∼Γζ\Gamma\sim\Gamma^\zeta. With D=diag⁡(ζ(v))v∈V(G)D=\operatorname{diag}(\zeta(v))_{v\in V(G)} we have A(Γζ)=DA(Γ)DA(\Gamma^\zeta)=D A(\Gamma)D, and we also write ΓD\Gamma^D for Γζ\Gamma^\zeta. As D−1=DD^{-1}=D, switching equivalent signed graphs have the same eigenvalues, and so the same energy. The sign of a cycle is the product of the signs of its edges, and the cycle is positive when this product equals 11. A signed graph is balanced if all of its cycles are positive. The negation of Γ\Gamma is −Γ=(G,−σ)-\Gamma=(G,-\sigma). Since A(−Γ)=−A(Γ)A(-\Gamma)=-A(\Gamma), we get E(−Γ)=E(Γ)\mathcal{E}(-\Gamma)=\mathcal{E}(\Gamma). We call Γ\Gamma antibalanced if −Γ-\Gamma is balanced.

For a real symmetric matrix SS, we write S⪰0S\succeq0 if SS is positive semidefinite, and S⪰TS\succeq T if S−T⪰0S-T\succeq0. We use JJ for the all-ones matrix and 1\mathbf{1} for the all-ones vector, and we write 1k\mathbf{1}_k when its length kk has to be shown. For other notation and basic facts from matrix theory, we refer to [24]. In addition, we shall repeatedly use the following standard facts.

(F1) Every real symmetric n×nn\times n matrix SS can be written as S=∑k=1nλkukukTS=\sum_{k=1}^{n}\lambda_k u_k u_k^{\mathsf{T}}, where λ1,…,λn\lambda_1,\ldots,\lambda_n are the eigenvalues of SS and u1,…,unu_1,\ldots,u_n is an orthonormal basis of corresponding eigenvectors.

(F2) For SS as in (F1), the matrices S+=∑λk>0λkukukTS_+=\sum_{\lambda_k>0}\lambda_k u_k u_k^{\mathsf{T}} and S−=−∑λk<0λkukukTS_-=-\sum_{\lambda_k<0}\lambda_k u_k u_k^{\mathsf{T}} satisfy S±⪰0S_\pm\succeq0, S+S−=S−S+=0S_+S_-=S_-S_+=0 and S=S+−S−S=S_+-S_-. We put ∣S∣=S++S−|S|=S_++S_-. Note that ∣S∣|S| is not the matrix of the absolute values of the entries of SS. The energy of SS is E(S)=tr⁡∣S∣=∑k∣λk∣\mathcal{E}(S)=\operatorname{tr}|S|=\sum_k|\lambda_k|. If in addition tr⁡S=0\operatorname{tr}S=0, then tr⁡S+=tr⁡S−=12E(S)\operatorname{tr}S_+=\operatorname{tr}S_-=\frac{1}{2}\mathcal{E}(S).

(F3) A matrix SS with rows and columns indexed by VV satisfies S⪰0S\succeq0 if and only if there are vectors svs_v (v∈Vv\in V) in some Rk\mathbb{R}^k such that Suv=⟨su,sv⟩S_{uv}=\langle s_u,s_v\rangle for all u,v∈Vu,v\in V. These vectors are called a Gram representation of SS.

References

  1. [1]A. Abiad, G. Coutinho, E. Juliano, L. Reijnders, A graph energy conjecture through the lenses of semidefinite programming, arXiv preprint, arXiv:2509.05814 [math.CO], 2025.arxiv.org/abs/2509.05814
  2. [2]S. Akbari, A. Alazemi, M. Andelić, Upper bounds on the energy of graphs in terms of matching number, Appl. Anal. Discrete Math. 15 (2021) 444–459.DOI
  3. [3]S. Akbari, M. Einollahzadeh, M.M. Karkhaneei, M.A. Nematollahi, Proof of a conjecture on the Seidel energy of graphs, European J. Combin. 86 (2020) 103078.arxiv.org/abs/1901.06692
  4. [4]S. Akbari, S. Küçükçifçi, H. Saveh, E.Ş. Yazıcı, A lower bound for the energy of graphs in terms of the vertex cover number, Discrete Math. 348 (2025) 114582.DOI
  5. [5]M. Aouchiche, P. Hansen, A survey of automated conjectures in spectral graph theory, Linear Algebra Appl. 432 (2010) 2293–2322.DOI
  6. [6]O. Arizmendi, J. Fernandez Hidalgo, O. Juarez-Romero, Energy of a vertex, Linear Algebra Appl. 557 (2018) 464–495.arxiv.org/abs/1805.05483
  7. [13]K.C. Das, S.A. Mojallal, Upper bounds for the energy of graphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 657–662.
  8. [14]K.C. Das, S.A. Mojallal, I. Gutman, Improving McClelland’s lower bound for energy, MATCH Commun. Math. Comput. Chem. 70 (2013) 663–668.
  9. [16]K.C. Das, S.A. Mojallal, S. Sun, On the sum of the k largest eigenvalues of graphs and maximal energy of bipartite graphs, Linear Algebra Appl. 569 (2019) 175–194.DOI
  10. [17]J. Day, W. So, Graph energy change due to edge deletion, Linear Algebra Appl. 428 (2008) 2070–2078.DOI
  11. [18]E. DeLaVina, Some history of the development of Graffiti, in: Graphs and Discovery, in: DIMACS Ser, Discrete Math. Theoret. Comput. Sci. 69 Amer. Math. Soc., Providence, RI, 2005, pp. 81–118.
  12. [19]S. Fajtlowicz, On conjectures of Graffiti. II, Congr. Numer. 60 (1987) 189–197.
  13. [21]K. Guo, B. Mohar, Hermitian adjacency matrix of digraphs and mixed graphs, J. Graph Theory 85 (2017) 217–248.DOI
  14. [22]I. Gutman, The energy of a graph, Ber. Math.-Statist. Sekt. Forschungsz. Graz 103 (1978) 1–22.
  15. [23]S. He, R.-X. Hao, F. Dong, The rank of a complex unit gain graph in terms of the matching number, Linear Algebra Appl. 589 (2020) 158–185.arxiv.org/abs/1909.07555
  16. [24]R.A. Horn, C.R. Johnson, Matrix Analysis, second ed., Cambridge University Press, Cambridge, 2013.
  17. [25]H. Kumar, S. Prยgada, Energy and independence number, arXiv preprint, arXiv:2607.19817 [math.CO], 2026.arxiv.org/abs/2607.19817
  18. [26]X. Li, Y. Shi, I. Gutman, Graph Energy, Springer, New York, 2012.
  19. [27]Y. Li, Lower bound of the energy of a complex unit gain graph in terms of the matching number of its underlying graph, arXiv preprint, arXiv:2005.01998 [math.CO], 2020.arxiv.org/abs/2005.01998
  20. [28]J. Liu, X. Li, Hermitian-adjacency matrices and Hermitian energies of mixed graphs, Linear Algebra Appl. 466 (2015) 182–207.DOI
  21. [29]L. Liu, B. Ning, Unsolved problems in spectral graph theory, Oper. Res. Trans. 27 (2023) 33–60.DOI
  22. [30]R. Mehatari, M.R. Kannan, A. Samanta, On the adjacency matrix of a complex unit gain graph, Linear Multilinear Algebra 70 (2022) 1798–1813.
  23. [31]S.A. Mojallal, Extremal graphs for the energy–independence number inequality, arXiv preprint, arXiv:2608.04367 [math.CO], 2026.arxiv.org/abs/2608.04367
  24. [32]V. Nikiforov, More spectral bounds on the clique and independence numbers, J. Combin. Theory Ser. B 99 (2009) 819–826.arxiv.org/abs/0706.0548
  25. [33]N. Reff, Spectral properties of complex unit gain graphs, Linear Algebra Appl. 436 (2012) 3165–3176.DOI
  26. [34]A. Samanta, Improved bound of graph energy in terms of vertex cover number, arXiv preprint, arXiv:2507.00798 [math.CO], 2025.arxiv.org/abs/2507.00798
  27. [35]A. Samanta, M.R. Kannan, On the spectrum of complex unit gain graphs, J. Ramanujan Math. Soc. 39 (2024) 131–142.
  28. [36]A. Samanta, M.R. Kannan, Bounds for the energy of a complex unit gain graph, Linear Algebra Appl. 612 (2021) 1–29.arxiv.org/abs/2005.08634
  29. [37]A. Samanta, M.R. Kannan, Bounds and extremal graphs for the energy of complex unit gain graphs, Linear Algebra Appl. 721 (2025) 844–866.arxiv.org/abs/2312.17152
  30. [39]F. Tian, D. Wong, Relation between the skew energy of an oriented graph and its matching number, Discrete Appl. Math. 222 (2017) 179–184.DOI
  31. [40]L. Wang, X. Ma, Bounds of graph energy in terms of vertex cover number, Linear Algebra Appl. 517 (2017) 207–216.DOI
  32. [41]W. Wei, S. Li, Relation between the Hermitian energy of a mixed graph and the matching number of its underlying graph, Linear Multilinear Algebra 68 (2020) 1395–1410.
  33. [42]D. Wong, X. Wang, R. Chu, Lower bounds of graph energy in terms of matching number, Linear Algebra Appl. 549 (2018) 276–286.DOI
  34. [43]F. Xu, Q. Zhou, D. Wong, F. Tian, Complex unit gain graphs of rank 2, Linear Algebra Appl. 597 (2020) 155–169.DOI
  35. [44]T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982) 47–74.

Paper details

vlnc:W_4qwmfqpa
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents