Metric dimension and pattern avoidance in graphs

In this paper, we prove a number of results about pattern avoidance in graphs with bounded metric dimension or edge metric dimension. We show that the maximum possible number of edges in a graph of diameter D and edge metric dimension k is at most (left perpendicular2D/3 right perpendicaular + 1)(k) + k Sigma(inverted right perpendicular D/3 inverted left perpendicular)(i=1) (2i)(k-1), sharpening the bound of ((k)(2)) +kD(k-1) + D-k from Zubrilina (2018). We also show that the maximum value of n for which some graph of metric dimension <= k contains the complete graph k(n) as a subgraph is n = 2(k). We prove that the maximum value of n for which some graph of metric dimension <= k contains the complete bipartite graph k(n,n) as a subgraph is 2(Theta(k)). Furthermore, we show that the maximum value of n for which some graph of edge metric dimension <= k contains K-1,K-n as a subgraph is n = 2 k. We also show that the maximum value of n for which some graph of metric dimension <= k contains K1-n as a subgraph is 3(k) - O(k). In addition, we prove that the d-dimensional grids Pi P-d(i-1)ri, have edge metric dimension at most d. This generalizes two results of Kelenc et al. (2016), that nonpath 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. (C) 2020 Elsevier B.V. All rights reserved.