{
  "id": "2111.09095",
  "version": "v2",
  "published": "2021-11-17T13:22:45.000Z",
  "updated": "2022-02-04T02:49:03.000Z",
  "title": "Distance $k$-resolving domination number of graphs",
  "authors": [
    "Dwi Agustin Retnowardani",
    "Muhammad Imam Utoyo",
    "Dafik",
    "Liliek Susilowati",
    "Kamal Dliou"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-02-04T02:49:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C12",
      "05C35",
      "G.2.2"
    ],
    "keywords": [
      "metric dimension",
      "resolving dominating set",
      "minimum cardinality",
      "resolving domination number respectively equal",
      "resolving set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}