Generalization of independent set to distance at least 3

Question

We know that in graph theory, an independent set is a set of vertices, such that no two of which are adjacent. There is rich theory about independent set, including approximation algorithm for finding maximal independent set, estimation of the size of the maximal independent set in random graphs, etc.

I wonder whether we can extend the definition, and define second-order independent set - any two vertices of which have distance at least 3? I.e., they can not have shared neighbor. Moreover, can we derive corresponding theory for such second-order independent set?

Answer 1

I am not familiar with the study of such a notion, but it does seem like a natural direction. Independent sets are in some sense extremely fundamental to graphs, because you can tell immediately if a set is independent (does it contain an edge?). Independent sets are dual notions to cliques. Graph coloring is a partition of the vertex set into independent sets. You could define analogous notions for these. However, in my opinion, these notions might not not have as rich of a theory as that of independent sets, as it is less fundamental in some sense.

On a more positive note, there is something in the literature called an $(\alpha, \beta)$-ruling set, which is a subset $S$ of vertices such that that the distance between any two vertices in $S$ is at least $\alpha$, and the distance between any vertex and the closest vertex in $S$ is at most $\beta$. This notion generalizes maximum independent sets, which are $(2,1)$-ruling sets.

Answer 2

This generalization of independent set is called distance-$d$ independent set or $d$-scattered set in the literature.

Answer 3

The size of any distance-2 independent set (or second-order independent set as you call it) gives a lower bound on the domination number (the minimum size of a dominating set) because every vertex of this independent set must be dominated by either itself, either one of its neighbors and as these neighborhoods are disjoint, they cannot dominate two vertices of this independent set in the same time.

A lower bound on the domination number is useful to compute it (especially when the domination number is high), because it can cut the brute force branching method when a dominating set of such a size has been found.