On the regular k-independence number of graphs

Abstract

The \emph{regular independence number}, introduced by Albertson and Boutin in 1990, is the maximum cardinality of an independent set of $G$ in which all vertices have equal degree in $G$. Recently, Caro, Hansberg and Pepper introduced the concept of regular $k$-independence number, which is a natural generalization of the regular independence number. A \emph{$k$-independent set} is a set of vertices whose induced subgraph has maximum degree at most $k$. The \emph{regular $k$-independence number} of $G$, denoted by $\hat{I}{\pm }_{k-reg}(G)$, is defined as the maximum cardinality of a $k$-independent set of $G$ in which all vertices have equal degree in $G$. In this paper, the exact values of the regular $k$-independence numbers of some special graphs are obtained. We also get some lower and upper bounds for the regular $k$-independence number of trees with given diameter, and the lower bounds for the regular $k$-independence number of line graphs. For a simple graph $G$ of order $n$, we show that $1\le \hat{I}{\pm }_{k-reg}(G)\le n$ and characterize the extremal graphs. The Nordhaus-Gaddum-type results for the regular $k$-independence number of graphs are also obtained.

18 pages, 3 figures. arXiv admin note: text overlap with arXiv:1306.5026 by other authors