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 $\sum_{i=1}^{k} d_{i} \leq\left\vert E\right\vert$. A set A ⊆ V satisfying ∑v ∈ Adeg (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.


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