New approach to the $k$-independence number of a graph

Abstract

Let $G=(V,E)$ be a graph and $k\ge 0$ an integer. A $k$-independent set $S\subseteq 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)\ge \frac{k+1}{\lceil d\rceil +k+1}n$, 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].

16 pages

References in corpus (1)

• Partitions of graphs into small and large sets

Cited by in corpus (2)

• Degree Sequence Index Strategy
• Simultaneous Domination in Graphs