Graphs with equal independence and annihilation numbers (Q640438)

Given a graph \(G\) with degree sequence \((d_1, \dots, d_n)\), the annihilation number \(a(G)\) of \(G\) is the largest index \(a\) for which the sum \(\sum_{i=1}^a d_i\) is at most the number edges in \(G\). The annihilation number is a polynomial time computable upper bound on the independence number. In the paper under review, the authors give two characterizations of the graphs with equal independence numbers and annihilation numbers -- one in terms of the critical independence number and one in terms of König-Egerváry graphs, maximum independent sets, and maximum annihilation sets. Both characterizations imply that it can be determined in polymial time whether or not the independence number and annihilation number of a given graph are equal.