2015/05/19 by Zhiwei Guo, Guo, Zhiwei, Haixing Zhao +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1505.04867
openalex publication_date 2015/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.