On the regular k-independence number of graphs

Original · EN

The 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 k-independent set is a set of vertices whose induced subgraph has maximum degree at most k. The regular k-independence number of G, denoted by α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≤αk-reg(G)≤ n and characterize the extremal graphs. The Nordhaus-Gaddum-type results for the regular k-independence number of graphs are also obtained.