On an annihilation number conjecture

english

2020

volume 18, issue 2

annihilation number   annihilation set   König-Egerváry graph   maximum independent set   maximum matching

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Let ?$\alpha(G)$? denote the cardinality of a maximum independent set, while ?$\mu(G)$? be the size of a maximum matching in the graph ?$G=(V, E)$?. If ?$\alpha(G)+\mu(G)=|V|$?, then ?$G$? is a König-Egerváry graph. If ?$d_1 \leq d_2 \leq \cdots \leq 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 |E|$?. A set ?$A\subseteq V$? satisfying ?$\sum_{v\in A} \text{deg}(v)\leq |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) ?$\alpha(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.

28.04.2021