Lower bounds for the independence and k k -independence number of graphs using the concept of degenerate degrees
Let G G be a graph and v v be any vertex of G G . We define the degenerate degree of v v , denoted by ?(v) ? ( v ) as ? ( v ) = max H : v ? H ? ( H ) , where the maximum is taken over all subgraphs of G G containing the vertex v v . We show that the degenerate degree sequence of any graph can be determined by an efficient algorithm. A k k -independent set in G G is any set S S of vertices such that ?(G[S])?k ? ( G [ S ] ) ? k . The largest cardinality of any k k -independent set is denoted by ?k(G) ? k ( G ) . For k?{1,2,3} k ? { 1 , 2 , 3 } , we prove that ?k?1(G)??v?Gmin{1,1/(?(v)+(1/k))} ? k ? 1 ( G ) ? ? v ? G min { 1 , 1 / ( ? ( 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 CaroWei bound and also the best known bounds for ?1(G) ? 1 ( G ) and ?2(G) ? 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 ?k(G) ? k ( G ) which are designed by the concept of cheap sets. At the end, a bound for ?k(G) ? k ( G ) is presented, where G G is a forest and k k an arbitrary non-negative integer.
independent set k k -independent set k k k k k degeneracy greedy algorithm