×

The partition dimension of Cayley digraphs. (English) Zbl 1086.05024

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.

MSC:

05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI