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₁ ≤ d₂ ≤ ⋯ ≤ 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 ⊆ V satisfying ∑_v ∈ Adeg (v) ≤ |E| is an annihilation set; if, in addition, deg (x) + ∑_v ∈ Adeg (v) > |E|, 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.