Inequalities Connecting the Annihilation and Independence Numbers

Abstract

Given a graph $G$, the number of its vertices is represented by $n(G)$, while the number of its edges is denoted as $m(G)$. An independent set in a graph is a set of vertices where no two vertices are adjacent to each other and the size of the maximum independent set is denoted by $\alpha (G)$. A matching in a graph refers to a set of edges where no two edges share a common vertex and the maximum matching size is denoted by $\mu (G)$. If $\alpha (G)+\mu (G)=n(G)$, then the graph $G$ is called a König-Egerváry graph. Considering a graph $G$ with a degree sequence $d_1\le d_2\le \cdots \le d_n$, the annihilation number $a(G)$ is defined as the largest integer $k$ such that the sum of the first $k$ degrees in the sequence is less than or equal to $m(G)$ (Pepper, 2004). It is a known fact that $\alpha (G)$ is less than or equal to $a(G)$ for any graph $G$. Our goal is to estimate the difference between these two parameters. Specifically, we prove a series of inequalities, including $a(G)-\alpha (G)\le \frac{\mu (G)-1}{2}$ for trees, $a(G)-\alpha (G)\le 2+\mu (G)-2\sqrt{1+\mu (G)}$ for bipartite graphs and $a(G)-\alpha (G)\le \mu (G)-2$ for König-Egerváry graphs. Furthermore, we demonstrate that these inequalities serve as tight upper bounds for the difference between the annihilation and independence numbers, regardless of the assigned value for $\mu (G)$.

17 pages, 10 figures