Nordhaus-Gaddum-Type Results for the k-Independent Number of Graphs

The concept of k-independent set, introduced by Fink and Jacobson in 1986, is a natural generalization of classical independence set. A k-independent set is a set of vertices whose induced subgraph has maximum degree at most k. The k-independence number of G, denoted by alpha(k)(G), is defined as the maximum cardinality of a k-independent set of G. As a natural counterpart of the k-independence number, we introduced the concept of k-edge-independence number. An edge set M in E(G) is called k-edge-independent if the maximum degree of the subgraph induced by the edges in M is less or equal to k. The k-edge-independence number, denoted beta(k)(G), is defined as the maximum cardinality of a k-edge-independent set. In this paper, we study the Nordhaus{Gaddum-type results for the parameter alpha(k)(G) and beta(k)(G). We obtain sharp upper and lower bounds of alpha(k)(G)+alpha(r)((G) over bar), alpha(k)(G) center dot alpha(r)((G) over bar), beta(k)(G) + beta(r)((G) over bar) and beta(k)(G) center dot beta(r)((G) over bar) for a graph G of order n. Some graph classes attaining these bounds are also given.