{
  "id": "2002.11048",
  "version": "v1",
  "published": "2020-02-25T17:19:09.000Z",
  "updated": "2020-02-25T17:19:09.000Z",
  "title": "The Threshold Dimension and Irreducible Graphs",
  "authors": [
    "Lucas Mol",
    "Matthew J. H. Murphy",
    "Ortrud R. Oellermann"
  ],
  "comment": "15 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $G$ be a graph, and let $u$, $v$, and $w$ be vertices of $G$. If the distance between $u$ and $w$ does not equal the distance between $v$ and $w$, then $w$ is said to resolve $u$ and $v$. The metric dimension of $G$, denoted $\\beta(G)$, is the cardinality of a smallest set $W$ of vertices such that every pair of vertices of $G$ is resolved by some vertex of $W$. The threshold dimension of $G$, denoted $\\tau(G)$, is the minimum metric dimension among all graphs $H$ having $G$ as a spanning subgraph. In other words, the threshold dimension of $G$ is the minimum metric dimension among all graphs obtained from $G$ by adding edges. If $\\beta(G) = \\tau(G)$, then $G$ is said to be irreducible. We give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, we show that every planar graph of order $n$ has threshold dimension $O (\\log_2 n)$. We show that several infinite families of graphs, known to have metric dimension $3$, are in fact irreducible. Finally, we show that for any integers $n$ and $b$ with $1 \\leq b < n$, there is an irreducible graph of order $n$ and metric dimension $b$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-02-25T17:19:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C69"
    ],
    "keywords": [
      "threshold dimension",
      "irreducible graph",
      "minimum metric dimension",
      "smallest set",
      "upper bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}