Inequalities Connecting the Annihilation and Independence Numbers
share
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 α(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 μ(G). If α(G) + μ(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 ≤ d_2 ≤⋯≤ 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 α(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) - α(G) ≤μ(G) - 1/2 for trees, a(G) - α(G) ≤ 2 + μ(G) - 2√(1 + μ(G)) for bipartite graphs and a(G) - α(G) ≤μ(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 μ(G).
READ FULL TEXT