Lower bounds for the independence and k-independence number of graphs using the concept of degenerate degrees

Let G be a graph and v be any vertex of G. We define the degenerate degree of v, denoted by (v) as zeta (v) = max(H:v is an element of H) delta(H), where the maximum is taken over all subgraphs of G containing the vertex v. We show that the degenerate degree sequence of any graph can be determined by an efficient algorithm. A k-independent set in G is any set S of vertices such that Delta(G[S]) <= k. The largest cardinality of any k-independent set is denoted by alpha(k)(G). For k is an element of {1, 2, 3}, we prove that alpha(k-1) (G) >= Sigma(v is an element of G) min{1, 1/(zeta(v) + (1/k))}. Using the concept of cheap vertices we strengthen our bound for the independence number. The resulting lower bounds improve greatly the famous Caro Wei bound and also the best known bounds for alpha(1)(G) and alpha(2)(G) for some families of graphs. We show that the equality in our bound for the independence number happens for a large class of graphs. Our bounds are achieved by Cheap-Greedy algorithms for alpha(k)(G) which are designed by the concept of cheap sets. At the end, a bound for alpha(k)(G) is presented, where G is a forest and k an arbitrary non-negative integer. (C) 2015 Elsevier B.V. All rights reserved.