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

CREATORAniruddha Samanta
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text