Metric dimension and pattern avoidance in graphs

Jesse Geneson

Published 2018-07-22Version 1

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$.