On an annihilation number conjecture - Levit, Vadim E. (Ars mathematica contemporanea, 2020)
Let ?$α(G)$? denote the cardinality of a maximum independent set, while ?$μ(G)$? be the size of a maximum matching in the graph ?$G=(V, E)$?. If ?$α(G)+μ(G)=|V|$?, then ?$G$? is a König-Egerváry graph. If ?$d_1 ≤ d_2 ≤ … ≤ d_n$? is the degree sequence of ?$G$?, then the annihilation number ?$a(G)$? of ?$G$? is the largest integer ?$k$? such that ?$\sum_{i=1}^{k}d_i ≤ |E|$?. A set ?$A\subseteq V$? satisfying ?$\sum_{v\in A} \text{deg}(v)≤ |E|$? is an annihilation set, if, in addition, ?$\text{deg}(x) +\sum_{v\in A} \text{deg}(v)>|E|$?, for every vertex ?$x\in V(G)-A$?, then ?$A$? is a maximal annihilation set in ?$G$?. In 2011, Larson and Pepper conjectured that the following assertions are equivalent: (i) ?$α(G) =a(G)$?; (ii) ?$G$? is a König-Egerváry graph and every maximum independent set is a maximal annihilating set. It turns out that the implication "(i) ?$\Longrightarrow$? (ii)" is correct. In this paper, we show that the opposite direction is not valid, by providing a series of generic counterexamples.
Keywords: annihilation number; annihilation set; König-Egerváry graph; König-Egerváryjev graf; maksimalna neodvisna množica; maksimalno prirejanje; maximum independent set; maximum matching; množica s pragom; prag