Distance-$k$ locating-dominating sets in graphs

Let $G$ be a graph with vertex set $V$, and let $k$ be a positive integer. A set $D\subseteq V$ is a \emph{distance-$k$ dominating set} of $G$ if, for each vertex $u\in V-D$, there exists a vertex $w\in D$ such that $d(u,w)\le k$, where $d(u,w)$ is the minimum number of edges linking $u$ and $w$ in $G$. Let $d_k(x,y)=\min \{d(x,y),k+1\}$. A set $R\subseteq V$ is a \emph{distance-$k$ resolving set} of $G$ if, for any pair of distinct $x,y\in V$, there exists a vertex $z\in R$ such that $d_k(x,z)\mathrm{\ne }{d}_k(y,z)$. The \emph{distance-$k$ domination number} ${\gamma }_k(G)$ (\emph{distance-$k$ dimension} ${\dim }_k(G)$, respectively) of $G$ is the minimum cardinality of all distance-$k$ dominating sets (distance-$k$ resolving sets, respectively) of $G$. The \emph{distance-$k$ location-domination number}, ${\gamma }_L^k(G)$, of $G$ is the minimum cardinality of all sets $S\subseteq V$ such that $S$ is both a distance-$k$ dominating set and a distance-$k$ resolving set of $G$. Note that ${\gamma }_L^1(G)$ is the well-known location-domination number introduced by Slater in 1988. For any connected graph $G$ of order $n\ge 2$, we obtain the following sharp bounds: (1) ${\gamma }_k(G)\le {\dim }_k(G)+1$; (2) $2\le {\gamma }_k(G)+{\dim }_k(G)\le n$; (3) $1\le \max{\gamma_k(G), \dim_k(G)} \le \gamma_L^k(G) \le \min{\dim_k(G)+1, n-1}$\mathrm{.}Wecharacterize$G$forwhich$\gamma_L^k(G)\in{1, |V|-1}$. We observe that $\frac{{\dim }_k(G)}{{\gamma }_k(G)}$ can be arbitrarily large. Moreover, for any tree $T$ of order $n\ge 2$, we show that $\gamma_L^k(T)\le n-ex(T)$,where$ex(T)$denotesthenumberofexteriormajorverticesof$T$, and we characterize trees $T$ achieving equality. We also examine the effect of edge deletion on the distance-$k$ location-domination number of graphs.