Metric dimension and pattern avoidance in graphs
share
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 (2D/3 +1)^k+k ∑_i = 1^D/3 (2i-1)^k-1, sharpening the bound of k2+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 ≤ 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 ≤ k can contain the complete bipartite graph K_n,n as a subgraph is 2^θ(k). Furthermore, we show that the maximum value of n such that a graph of edge metric dimension ≤ 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 ≤ k can contain K_1,n as a subgraph is 3^k-O(k). In addition, we prove that the d-dimensional grid ∏_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.
READ FULL TEXT