Improved bound of graph energy in terms of vertex cover number
Aniruddha Samanta · 2025
Read Improved bound of graph energy in terms of vertex cover number by Aniruddha Samanta (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00798.txt.
Introduction
Aniruddha Samanta proved a stronger lower bound on the energy of a graph, a quantity built from the eigenvalues of its adjacency matrix. A vertex cover is a set of vertices touching every edge, and its smallest size is the cover number. An older result bounded graph energy below by twice the cover number minus a correction for odd cycles. Samanta shows the correction can be dropped entirely for several classes of graphs, so energy is at least twice the cover number there.
Catalog record
| CREATOR | Aniruddha Samanta |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-00798
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved bound of graph energy in terms of vertex cover number Aniruddha Samanta Abstract Let G G be a simple graph with the vertex cover number τ \tau . The energy ℰ ( G ) \mathcal{E}(G) of G G is the sum of the absolute values of all the adjacency eigenvalues of G G . In this article, we establish ℰ ( G ) ≥ 2 τ \mathcal{E}(G)\geq 2\tau for several classes of graphs. The result significantly improves the known result ℰ ( G ) ≥ 2 τ − 2 c \mathcal{E}(G)\geq 2\tau-2c for many classes of graphs, where c c is the number of odd cycles. Mathematics Subject Classification(2010): 05C22(primary); 05C50, 05C35(secondary). Keywords. Adjacency matrix, Graph energy, Vertex cover number. 1 Introduction Throughout this article, we consider G to be a simple undirected graph with vertex set V(G)=\{v_{1},v_{2},\dots,v_{n}\} and edge set E(G) . If two vertices v_{i} and v_{j} are connected by an edge, then we write v_{i}\sim v_{j} and the edge between them is denoted by e_{ij} . The adjacency matrix A(G)=(a_{ij})_{n\times n} of G is an n\times n symmetric matrix, defined as a_{ij}=1 if v_{i}\sim v_{j} and zero otherwise. Let \lambda_{1},\lambda_{2},\dots,\lambda_{n} be the eigenvalues of A(G) . Then the energy of G is defined as \mathcal{E}(G):=\sum\limits_{i=1}^{n}|\lambda_{i}| , where |\lambda_{i}| is the absolute value of \lambda_{i} . This graph invariant was formally introduced by Gutman in 1978. It has a great significance in connection with the total \pi -electron energy in conjugated hydrocarbon in chemistry. Since then, graph energy has been studied extensively by many researchers. Studies of graph eigenvalues have a long history in the mathematics literature. Many beautiful results and bounds have been discovered on the largest and smallest eigenvalues of a graph. However, handling other eigenvalues is difficult, and that results in a very few literature on such eigenvalues. Since, the energy of a graph G is dependent on all eigenvalues of G , so it is quite hard to analyses its properties. Therefore, researchers mainly focused on bounding energy in terms of algebraic and combinatorial parameters of a graphs such as matching number, vertex degree, number of vertices, number of edges, vertex cover number, etc. A vertex cover X of a graph G is a subset of V(G) such that any edge of G is adjacent to at least one vertex of X . The vertex cover number of G , denoted by \tau(G) , is the cardinality of a vertex cover of G with minimum number of vertices. A matching of a graph G is a set of independent edges, that is any two edges have no common vertices. The matching number of G is the cardinality of a matching with maximum number of edges, and it is denoted by \mu(G) . For a graph G , it is well known that \tau(G)\geq\mu(G) . Wang and Ma [ 4 ] , established the following lower bound of \mathcal{E}(G) in terms of vertex cover number \tau(G) and the number of odd cycles c(G) . \mathcal{E}(G)\geq 2\tau(G)-2c(G). (1) For any graph G with matching number \mu(G) , Wong et.al [ 5 ] proved that \mathcal{E}(G)\geq 2\mu(G). (2) Later, many authors extended results ( 1 ) and ( 2 ) for mixed graphs, digraphs, complex unit gain graphs, etc., see references [ 3 ] . In this article, we present several classes of graphs G for which \mathcal{E}(G)\geq 2\tau(G) , which significantly improves the above bounds ( 1 ) and ( 2 ) for such classes. 2 Definitions, notation and preliminary results Let G be an undirected simple graph with vertex set V(G)=\{v_{1},v_{2},\dots,v_{n}\} and edge set E(G) . A subset S of the edge set E(G) is called a cut set of G if the deletion of all edges of S from G increase the number of connected components of G . If S is a cut set of G then G-S denotes the resulting graph after deletion of all edges of S from G and it is defined as G-S:=G_{1}\oplus G_{2}\oplus\cdots\oplus G_{r} , where G_{i}^{\prime}s are the connected components in G-S . For a vertex v in G , we denote G-v as an induced subgraph of G with vertex set V(G)\setminus{v} . A vertex v\in V(G) is said to be a cut vertex of G if G-v increases the number of connected components. A block of the graph G is a maximal connected subgraph of G that has no cut-vertex. For an edge e\in E(G) , we denote G-[e] as an induce subgraph of G obtained by removing e , edges adjacent with e and the vertices joining e . We denote a complete graph and a cycle with n vertices as K_{n} and C_{n} , respectively. A complete bipartite graph with vertex partition size p and q is denoted by K_{p,q} . Let us first present the following bound which we are going to improve in this article for several classes of graphs. Theorem 2.1 . [ 4 , Theorem 4.2] Let G be a graph with vertex cover number \tau and number of odd cycles c . Then \mathcal{E}(G)\geq 2\tau-2c . Equality occurs if and only if G is the disjoint union of some K_{p,p} , for some p and isolated vertices. The following two results we use frequently in the later sections. Theorem 2.2 . [ 2 , Theorem 3.4] If G is a graph with a simple cut set E , then \mathcal{E}(G)\geq\mathcal{E}(G-E) . Theorem 2.3 . [ 2 , Theorem 3.6] If E is a cut set between complimentary induced subgraphs M and N of G . Suppose the edges of E form a star, then \mathcal{E}(G)>\mathcal{E}(G-E) . Lemma 2.1 . For any cycle C_{n} with n vertices, \mathcal{E}(C_{n})=\left\{\begin{array}[]{ccc}4\frac{\cos\frac{\pi}{n}}{\sin\frac{\pi}{n}}&\mbox{for}&n\equiv 0\mbox{ mod 4}\\ \frac{4}{\sin\frac{\pi}{n}}&\mbox{for}&n\equiv 2\mbox{ mod 4}\\ \frac{2}{\sin\frac{\pi}{2n}}&\mbox{for}&n\equiv 1\mbox{ mod 2}.\end{array}\right. 3 Graph energy in terms of the vertex cover number We begin this section with some basic class of graphs G for which \mathcal{E}(G)\geq 2\tau(G) holds. Proposition 3.1 . (1) Let G be a complete graph. Then \mathcal{E}(G)=2\tau(G) . (2) Let G be a bipartite graph. Then \mathcal{E}(G)\geq 2\tau(G) . (3) Let G be a cycle. Then \mathcal{E}(G)\geq 2\tau(G) . Proof. Part (1) and (2) are easy to observe. (3) If n is even, then C_{n} is bipartite. Then \mathcal{E}(C_{n})\geq 2\mu(C_{n})=2\tau(C_{n}) . If n is odd. Then n\equiv 1 mod 2 . That is n=2k+1 , for k=1,2,\cdots . Now \frac{\pi}{2n}<\frac{\pi}{4} , so \sin x<x . Therefore, \sin\frac{\pi}{2n}<\frac{\pi}{2n} . Now by Lemma 2.1 , \mathcal{E}(C_{n})=\frac{2}{\sin\frac{\pi}{2n}}>\frac{2}{\pi/2n}=\frac{4n}{\pi} . If \frac{4n}{\pi}\geq 2\tau(C_{n}), (3) where \tau(C_{n})=\frac{n+1}{2}=k+1 . Now ( 3 ) is true if and only if \frac{4(2k+1)}{\pi}\geq 2(k+1) , i.e., k\geq 2 . For k=1 , C_{3} is complete. Thus the result follows. ∎ Lemma 3.1 . Let u be a quasi-pendent vertex of G and \mathcal{E}(G-u)\geq 2\tau(G-u) . Then \mathcal{E}(G)\geq 2\tau(G) . Proof. Let v be a pendent vertex of G such that u\sim v . Then any minimum vertex cover, say U of G must contain either u or v . If it contains v , then we can replace v by u , and it will be still a minimum vertex cover of G . Now we remove vertex u , then \tau(G-u)=\tau(G)-1