On an annihilation number conjecture

Vadim E. Levit, Eugen Mandrescu


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 d1 ≤ d2 ≤ ⋯ ≤ dn is the degree sequence of G, then the annihilation number a(G) of G is the largest integer k such that sumi = 1k di ≤ |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.


Maximum independent set, matching, tree, bipartite graph, König-Egerváry graph, annihilation set, annihilation number

Full Text:


DOI: 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