On an Annihilation Number Conjecture
share
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 h(G) of G is the largest integer k such that ∑_i=1^kd_i≤ E (Pepper 2004, Pepper 2009). A set A⊆ V satisfying ∑_a∈ A deg(a)≤ E is an annihilation set, if, in addition, deg(v) +∑_a∈ A deg(a)> E , for every vertex v∈ V(G)-A, then A is a maximal annihilation set in G. In (Larson & Pepper 2011) it was conjectured that the following assertions are equivalent: (i) α(G) =h(G) ; (ii) G is a König-Egerváry graph and every maximum independent set is a maximal annihilating set. In this paper, we prove that the implication "(i) (ii)" is correct, while for the opposite direction we provide a series of generic counterexamples. Keywords: maximum independent set, matching, tree, bipartite graph, König-Egerváry graph, annihilation set, annihilation number.
READ FULL TEXT