# Independent set where two vertices need to have distance >= c

An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices.

I am interested in the generalization $c$-IS where two nodes in $V' \subseteq V(G)$ need to have distance at least $c$ to any other vertex in $V'$.

Has this problem been studied before?

• Distance-$d$ Independent Set. – Pål GD Apr 8 '13 at 8:53

Yes, this is called ruling set. An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that the distance between $u$ and $v$ is at most $\beta$. So a maximal independent set is a $(2,1)$-ruling set. (This is defined in [1] but there might be prior references.)