{
  "id": "2112.01910",
  "version": "v2",
  "published": "2021-12-03T13:52:46.000Z",
  "updated": "2022-06-12T10:57:36.000Z",
  "title": "Locating-dominating sets: from graphs to oriented graphs",
  "authors": [
    "Nicolas Bousquet",
    "Quentin Deschamps",
    "Tuomo Lehtilä",
    "Aline Parreau"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A locating-dominating set in an undirected graph is a subset of vertices $S$ such that $S$ is dominating and for every $u,v \\notin S$, we have $N(u)\\cap S\\ne N(v)\\cap S$. In this paper, we consider the oriented version of the problem. A locating-dominating set in an oriented graph is a set $S$ such that for every $w\\in V$, $N[w]^-\\cap S=\\emptyset$ and for each pair of vertices $u,v\\in V\\setminus S$, $N^-(u)\\cap S\\ne N^-(v)\\cap S$. We consider the following two parameters. Given an undirected graph $G$, we look for $\\overset{\\rightarrow}{\\gamma}_{LD}(G)$ ($\\overset{\\rightarrow}{\\Gamma}_{LD}(G))$ which is the size of the smallest (largest) optimal locating-dominating set over all orientations of $G$. In particular, if $D$ is an orientation of $G$, then $\\overset{\\rightarrow}{\\gamma}_{LD}(G)\\leq{\\gamma}_{LD}(D)\\leq\\overset{\\rightarrow}{\\Gamma}_{LD}(G)$. For the best orientation, we prove that, for every twin-free graph $G$ on $n$ vertices, $\\overset{\\rightarrow}{\\gamma}_{LD}(G)\\le n/2$ proving a ``directed version'' of a conjecture on $\\gamma_{LD}(G)$. Moreover, we give some bounds for $\\overset{\\rightarrow}{\\gamma}_{LD}(G)$ on many graph classes and drastically improve the value $n/2$ for (almost) $d$-regular graphs by showing that $\\overset{\\rightarrow}{\\gamma}_{LD}(G)\\in O(\\log d/d\\cdot n)$ using a probabilistic argument. While $\\overset{\\rightarrow}{\\gamma}_{LD}(G)\\leq\\gamma_{LD}(G)$ holds for every graph $G$, we give some graph classes graphs for which $\\overset{\\rightarrow}{\\Gamma}_{LD}(G)\\geq{\\gamma}_{LD}(G)$ and some for which $\\overset{\\rightarrow}{\\Gamma}_{LD}(G)\\leq {\\gamma}_{LD}(G)$. We also give general bounds for $\\overset{\\rightarrow}{\\Gamma}_{LD}(G)$. Finally, we show that for many graph classes $\\overset{\\rightarrow}{\\Gamma}_{LD}(G)$ is polynomial on $n$ but we leave open the question whether there exist graphs with $\\overset{\\rightarrow}{\\Gamma}_{LD}(G)\\in O(\\log n)$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-06-12T10:57:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C69"
    ],
    "keywords": [
      "oriented graph",
      "undirected graph",
      "graph classes graphs",
      "twin-free graph",
      "optimal locating-dominating set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}