Distance $k$-resolving domination number of graphs

Dwi Agustin Retnowardani, Muhammad Imam Utoyo, Dafik, Liliek Susilowati, Kamal Dliou

Published 2021-11-17, updated 2022-02-04Version 2

For $k \geq 1$, in a graph $G=(V,E)$, a set of vertices $D$ is a distance $k$-dominating set of $G$, if any vertex in $V$ not in $D$ is at distance at most $k$ from some vertex in $D$. An ordered set of vertices $W=\{w_1,w_2,\ldots,w_r\}$ is a resolving set of $G$, if for any two distinct vertices $x$ and $y$ in $V\setminus W$, there exists $1\leq i\leq r$, such that $d_G(x,w_i)\neq d_G(y,w_i)$. The minimum cardinality of such set is the metric dimension of the graph $G$, and is denoted by $dim(G)$. In this paper, we introduce the study of distance $k$-resolving dominating set, which is a subset of $V$ that is both a distance $k$-dominating set and a resolving set of $G$. The minimum cardinality of any distance $k$-resolving dominating set of $G$ is called the distance $k$-resolving domination number, and is denoted by $\gamma^r_{k}(G)$. First, we give sharp bounds for $\gamma^r_{k}(G)$ with the metric dimension $dim(G)$ and the distance $k$-domination number $\gamma_k(G)$. Afterwards, we generalize some existing results in the case where $k=1$, to all $k \geq 2$. We give necessary and sufficient condition between $\gamma^r_{k}(G)$ and $dim(G)$ for $k \geq 2$, then we characterize the connected graphs having the distance $k$-resolving domination number respectively equal to $1$, $n-2$, and $n-1$. Afterwards, we provide an upper bound for $\gamma^r_{k}(G)$ involving the order $n$ of $G$ and its diameter, and we bound the order in terms of $\gamma^r_{k}(G)$, while showing graphs achieving these bounds for any $k\geq 1$. Later, we construct graphs realizing all possible triple $(dim(G),\gamma_k(G),\gamma^r_k (G))$, for all $k\geq 2$. Finally, we establish Nordhaus-Gaddum bounds for the distance $k$-resolving domination number, for all $k\geq 2$.