Graphs with equal independence and annihilation numbers

C. E. Larson ; R. Pepper

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

The annihilation number $a$ of a graph is an upper bound of the independence number $\alpha$ of a graph. In this article we characterize graphs with equal independence and annihilation numbers. In particular, we show that $\alpha=a$ if, and only if, either (1) $a\geq \frac{n}{2}$ and $\alpha' =a$, or (2) $a < \frac{n}{2}$ and there is a vertex $v\in V(G)$ such that $\alpha' (G-v)=a(G)$, where $\alpha'$ is the critical independence number of the graph. Furthermore, we show that it can be determined in polynomial time whether $\alpha=a$. Finally we show that a graph where $\alpha=a$ is either König-Egerváry or almost König-Egerváry.

Détail

DOI : 10.37236/667

Classification : 05C69, 05C75
Mots-clés : Independence number, annihilation number, critical independence number, König-Egerváry graphs