LOWER BOUNDS ON THE STABILITY NUMBER OF GRAPHS COMPUTED IN TERMS OF DEGREES

Wei discovered that the stability number, alpha(G), of a graph, G, with degree sequence d1, d2,...,d(n) is at least [GRAPHICS] It is shown that this bound can be replaced by a function b(G), computable from d1, d2,...,d(n) using only O(n) additions and comparisons. For all graphs, b(G) greater-than-or-equal-to [w(G)], the inequality sometimes holding as strict. In addition, it is shown that Wei's bound can be increased by (w(G) - 1)/DELTA(DELTA + 1) when G is connected, by w(G)k/2DELTA(DELTA + 1) when G is k-connected but not complete, and by (w(G) + m - n)/DELTA(DELTA + 1) when G is triangle-free; in each case, DELTA, n, and m denote the largest degree of a vertex in G, the number of vertices of G, and the number of edges of G, respectively.