A study of a combination of distance domination and resolvability in graphs

Abstract

For $k\ge 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\setminus D$ is at distance at most $k$ from some vertex in $D$. The minimum cardinality of a distance $k$-dominating set of $G$ is the distance $k$-domination number, denoted by ${\gamma }_k(G)$. An ordered set of vertices $W=\{w_1,w_2,\dots ,w_r\}$ is a resolving set of $G$, if for any two distinct vertices $x$ and $y$ in $V\setminus W$, there exists $1\le i\le r$, such that $d_G(x,w_i)\ne d_G(y,w_i)$. The minimum cardinality of a resolving set of $G$ is the metric dimension of the graph $G$, denoted by $dim(G)$. In this paper, we introduce the 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 a distance $k$-resolving dominating set of $G$ is called the distance $k$-resolving domination number and is denoted by ${\gamma }_k^r(G)$. We give several bounds for ${\gamma }_k^r(G)$ some in terms of the metric dimension $dim(G)$ and the distance $k$-domination number ${\gamma }_k(G)$. We determine ${\gamma }_k^r(G)$ when $G$ is a path or a cycle. Afterwards, we characterize the connected graphs of order $n$ having ${\gamma }_k^r(G)$ equal to $1$, $n-2$, and $n-1$, for $k\ge 2$. Then, we construct graphs realizing all the possible triples $(dim(G),{\gamma }_k(G),{\gamma }_k^r(G))$, for all $k\ge 2$. Later, we determine the maximum order of a graph $G$ having distance $k$-resolving domination number ${\gamma }_k^r(G)={\gamma }_k^r\ge 1$, we provide graphs achieving this maximum order for any positive integers $k$ and ${\gamma }_k^r$. Finally, we establish Nordhaus-Gaddum bounds for ${\gamma }_k^r(G)$, for $k\ge 2$.