On the complexity of the k-independence number and the h-diameter of a graph

The k-independence number of a graph, which extends the
classical independence number, is the maximum size of a set of vertices
at pairwise distance greater than k. The associated decision problem is
known to be NP-complete for general graphs, and it is also known to
remain NP-complete for regular bipartite graphs when k ∈ {2,3,4} and for
planar bipartite graphs of maximum degree 3 for all k ≥ 2. We continue
this line of research by showing that the problem remains NP-complete
when considering several other graph classes. Moreover, we establish a
new connection between the k-independence number and the h-diameter,
which is a natural generalization of the graph diameter. Finally, we use this
new link to show the (parametrized) complexity of the decision problem
associated to computing the h-diameter.