Fehr, Melodie; Gosselin, Shonda; Oellermann, Ortrud R. The partition dimension of Cayley digraphs. (English) Zbl 1086.05024 Aequationes Math. 71, No. 1-2, 1-18 (2006). Summary: Let \(G\) be a (di)graph and \(S\) a set of vertices of \(G\). We say \(S\) resolves two vertices \(u\) and \(v\) of \(G\) if \(d(u,S) \not= d(v,S)\). A partition \(\prod = \{P_1,P_2,\dots,P_k\}\) of \(V(G)\) is a resolving partition of \(G\) if every two vertices of \(G\) are resolved by \(P_i\) for some \(i\) (\(1\leq i \leq k\)). The smallest cardinality of a resolving partition of \(G\), denoted by \(\text{pd}(G)\), is called the partition dimension of \(G\). A vertex \(r\) of \(G\) resolves a pair \(u, v\) of vertices of \(G\) if \(d(u,r) \not= d(v,r)\). A set \(R\) of vertices of \(G\) is a resolving set for \(G\) if every two vertices of \(G\) are resolved by some vertex of \(R\). The smallest cardinality of a resolving set of vertices, denoted by \(\dim(G)\), is called the metric dimension of \(G\). We begin by disproving a conjecture made by Chartrand, Salehi and Zhang regarding the partition dimension of products of graphs. The partition dimension of Cayley digraphs of abelian groups with a specific minimal set of generators is shown to be at most one more than the number of generators with equality for one or two generators. It is known that \(\text{pd}(G) \leq \dim(G)+1\). It is pointed out that for every positive integer \(M\) there are Cayley digraphs \(D\) for which \(\dim(D) - \text{pd}(D) \geq M\), and that there are classes of Cayley digraphs \(D\) such that \(\frac{\text{pd}(D)}{\dim(D)} \to 0\) as \(| V(D)| \to \infty\). Moreover, it is shown that the partition dimension of the Cayley digraph for the dihedral group of order \(2n\) (\(n \geq 3\)) with a minimum set of generators is 3. We conclude by introducing a more general class of problems for which the problems of finding the metric dimension and partition dimension of a (di)graph are the two extremes and provide an interpretation of the transition between these two invariants. Cited in 20 Documents MSC: 05C12 Distance in graphs 05C20 Directed graphs (digraphs), tournaments 05C90 Applications of graph theory Keywords:Metric dimension PDFBibTeX XMLCite \textit{M. Fehr} et al., Aequationes Math. 71, No. 1--2, 1--18 (2006; Zbl 1086.05024) Full Text: DOI