An Extremal Problem in Distance-\(k\) Domination

Abstract

The distance-\( k \) domination number of graph \( G \), \( \gamma_{\leq k}(G) \), is the cardinality of a smallest set of vertices, \( S \), such that every vertex not in \( S \) is no more than distance \( k \) from at least one vertex of \( S \). Carrington, Harary, and Haynes showed \( |V^0| \geq 2|V^+| \) where \( V^0 = \{u \in V: \gamma_{\leq 1}(G-v) = \gamma_{\leq 1}(G)\} \) and \( V^+ = \{v \in V: \gamma_{\leq 1}(G-v) > \gamma_{\leq 1}(G)\} \). This paper extends the result to distance-\( k \) domination, with the obvious change in definition of \( V^0 \) and \( V^+ \), to show \( |V^0| \geq \frac{2}{2k-1}|V^+| \). Extremal graphs are characterized when \( k = 1 \) and some progress is mentioned on the characterization problem when \( k > 1 \).