Counterexamples to the Characterisation of Graphs with Equal Independence and Annihilation Number

The Electronic Journal of Combinatorics, vol. 30

Abstract

In this paper, we disprove the claimed characterisation of graphs with equal independence and annihilation number as proposed by Larson and Pepper [Electron. J. Comb. 2011]. The annihilation number of a graph is defined as the largest integer $p$ such that the sum of its smallest $p$ degrees is greater than or equal to its size, i.e., its number of edges. Larson and Pepper claimed that for a given graph $G=(V,E)$, its independence number $\alpha(G)$ equals its annihilation number $a(G)$ if and only if $$\begin{array}{ll}(1)~~ a(G)\geq \frac n2:& \alpha'(G)=a(G)\\[2mm](2)~~ a(G)= \frac{n-1}{2}:& \alpha'(G-v)=a(G) ~\text{ for some } v\in V.\end{array}$$This paper provides series of counterexamples with an arbitrarily large number of vertices, an arbitrarily large number of components, an arbitrarily large independence number, and an arbitrarily large difference between the critical and the regular independence number. Furthermore, we identify the error in the proof of Larson and Pepper's theorem. Yet, we show that the theorem still holds for bipartite graphs and connected claw-free graphs.

Authors 1

1. Michaela Hiller corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University