On an Annihilation Number Conjecture

Abstract

Let $\alpha (G)$ denote the cardinality of a maximum independent set, while $\mu (G)$ be the size of a maximum matching in the graph $G=\left(V,E\right)$. If $\alpha (G)+\mu (G)=\left|V\right|$, then $G$ is a König-Egerváry graph. If $d_1\le d_2\le \cdots \le d_n$ is the degree sequence of $G$, then the annihilation number $h\left(G\right)$ of $G$ is the largest integer $k$ such that $\sum _{i=1}^k{d}_i\le \left|E\right|$ (Pepper 2004, Pepper 2009). A set $A\subseteq V$ satisfying $\sum _{a\in A}deg(a)\le \left|E\right|$ is an annihilation set, if, in addition, $deg\left(v\right)+\sum _{a\in A}deg(a)>\left|E\right|$, for every vertex $v\in V(G)-A$, then $A$ is a maximal annihilation set in $G$. In (Larson & Pepper 2011) it was conjectured that the following assertions are equivalent: (i) $\alpha \left(G\right)=h\left(G\right)$; (ii) $G$ is a König-Egerváry graph and every maximum independent set is a maximal annihilating set. In this paper, we prove that the implication "(i) $⟹$ (ii)" is correct, while for the opposite direction we provide a series of generic counterexamples. Keywords: maximum independent set, matching, tree, bipartite graph, König-Egerváry graph, annihilation set, annihilation number.

17 pages, 11 figures