Bounds on the Metric and Partition Dimensions of a Graph

Abstract

Given a graph \(G\), we say \(S \subseteq V(G)\) is \({resolving}\) if for each pair of distinct \(u, v \in V(G)\) there is a vertex \(x \in S\) where \(d(u, x) \neq d(v, x)\). The metric dimension of \(G\) is the minimum cardinality of all resolving sets. For \(w \in V(G)\), the distance from \(w\) to \(S\), denoted \(d(w, S)\), is the minimum distance between \(w\) and the vertices of \(S\). Given \(\mathcal{P} = \{P_1, P_2, \ldots, P_k\}\) an ordered partition of \(V(G)\), we say \(P\) is resolving if for each pair of distinct \(u, v \in V(G)\) there is a part \(P_i\) where \(d(u, P_i) \neq d(v, P_i)\). The partition dimension is the minimum order of all resolving partitions. In this paper, we consider relationships between metric dimension, partition dimension, diameter, and other graph parameters. We construct “universal examples” of graphs with given partition dimension, and we use these to provide bounds on various graph parameters based on metric and partition dimensions. We form a construction showing that for all integers \(a\) and \(b\) with \(3 \leq a \leq \beta + 1\), there exists a graph \(G\) with partition dimension \(\alpha\) and metric dimension \(\beta\), answering a question of Chartrand, Salehi, and Zhang \([3]\).