{
  "id": "1807.08334",
  "version": "v1",
  "published": "2018-07-22T18:17:08.000Z",
  "updated": "2018-07-22T18:17:08.000Z",
  "title": "Metric dimension and pattern avoidance in graphs",
  "authors": [
    "Jesse Geneson"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In this paper, we prove a number of results about pattern avoidance in graphs with bounded metric dimension or edge metric dimension. First we prove that the maximum possible number of edges in a graph of diameter $D$ and edge metric dimension $k$ is at most $(\\lfloor \\frac{2D}{3}\\rfloor +1)^{k}+k \\sum_{i = 1}^{\\lceil \\frac{D}{3}\\rceil } (2i-1)^{k-1}$, sharpening the bound of $\\binom{k}{2}+k D^{k-1}+D^{k}$ from Zubrilina (2018). Moreover, we prove that the maximum value of $n$ such that a graph of metric dimension $\\leq k$ can contain the complete graph $K_{n}$ as a subgraph is $n = 2^{k}$. We also prove that the maximum value of $n$ such that a graph of metric dimension or edge metric dimension $\\leq k$ can contain the complete bipartite graph $K_{n,n}$ as a subgraph is $2^{\\theta(k)}$. Furthermore, we show that the maximum value of $n$ such that a graph of edge metric dimension $\\leq k$ can contain $K_{1,n}$ as a subgraph is $n = 2^{k}$. We also show that the maximum value of $n$ such that a graph of metric dimension $\\leq k$ can contain $K_{1,n}$ as a subgraph is $3^{k}-O(k)$. In addition, we prove that the $d$-dimensional grid $\\prod_{i = 1}^{d} P_{r_{i}}$ has edge metric dimension at most $d$. This generalizes two results of Kelenc et al (2016), that non-path grids have edge metric dimension $2$ and that $d$-dimensional hypercubes have edge metric dimension at most $d$. We also provide a characterization of $n$-vertex graphs with edge metric dimension $n-2$, answering a question of Zubrilina. As a result of this characterization, we prove that any connected $n$-vertex graph $G$ such that $edim(G) = n-2$ has diameter at most $5$. More generally, we prove that any connected $n$-vertex graph with edge metric dimension $n-k$ has diameter at most $3k-1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-22T18:17:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C90"
    ],
    "keywords": [
      "edge metric dimension",
      "pattern avoidance",
      "maximum value",
      "vertex graph",
      "complete bipartite graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}