New approach to the k-independence number of a graph

作者：Caro Yair^*; Han**erg Adriana

来源：Electronic Journal of Combinatorics, 2013, 20(1): P33.

• k-independence
• average degree

Let G = (V, E) be a graph and k >= 0 an integer. A k-independent set S subset of V is a set of vertices such that the maximum degree in the graph induced by S is at most k. With alpha(k) (G) we denote the maximum cardinality of a k-independent set of G. We prove that, for a graph G on n vertices and average degree d, alpha(k)(G) >= k+1/inverted right perpendiculardinverted left perpendicular+k+1n, improving the hitherto best general lower bound due to Caro and Tuza [Improved lower bounds on k-independence, J. Graph Theory 15 (1991), 99-107].

• 出版日期2013-2-12