### On an annihilation number conjecture

#### Abstract

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} \leq\left\vert E\right\vert$. A set *A* ⊆ *V* satisfying ∑_{v ∈ A}deg (*v*) ≤ |*E*| is an *annihilation set*; if, in addition, $\deg\left( x\right) +\sum\limits_{v\in A}\deg(v)>\left\vert E\right\vert$, for every vertex *x* ∈ *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)* ⇒ *(ii)*“ is correct.

In this paper, we show that the opposite direction is not valid, by providing a series of generic counterexamples.

#### Keywords

#### Full Text:

MANUSCRIPTDOI: https://doi.org/10.26493/1855-3974.1950.8bd

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications