An Extremal Problem in Distance-$k$ Domination

Abstract

The distance-$k$ domination number of graph $G$, ${\gamma }_{\le 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|\ge 2|V^{+}|$ where $V^0=\{u\in V:{\gamma }_{\le 1}(G-v)={\gamma }_{\le 1}(G)\}$ and $V^{+}=\{v\in V:{\gamma }_{\le 1}(G-v)>{\gamma }_{\le 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|\ge \frac{2}{2k-1}|V^{+}|$. Extremal graphs are characterized when $k=1$ and some progress is mentioned on the characterization problem when $k>1$.