Counterexamples to the characterisation of graphs with equal independence and annihilation number

Michaela Hiller¹

¹RWTH Aachen University

The electronic journal of combinatorics, Tome 30 (2023) no. 4

Résumé

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.

Détail

DOI : 10.37236/11458

Classification : 05C69, 05C75
Mots-clés : independence number, annihilation number, critical independence number