Fehr, Melodie; Gosselin, Shonda; Oellermann, Ortrud R. The metric dimension of Cayley digraphs. (English) Zbl 1085.05034 Discrete Math. 306, No. 1, 31-41 (2006). Summary: A vertex \(x\) in a digraph \(D\) is said to resolve a pair \(u\), \(v\) of vertices of \(D\) if the distance from \(u\) to \(x\) does not equal the distance from \(v\) to \(x\). A set \(S\) of vertices of \(D\) is a resolving set for \(D\) if every pair of vertices of \(D\) is resolved by some vertex of \(S\). The smallest cardinality of a resolving set for \(D\), denoted by \(\dim(D)\), is called the metric dimension for \(D\). Sharp upper and lower bounds for the metric dimension of the Cayley digraphs Cay\((\Delta:\Gamma)\), where \(\Gamma\) is the group \(\mathbb Z_{n_1}\oplus \mathbb Z_{n_2} \oplus \cdots \oplus \mathbb Z_{n_m}\) and \(\Delta\) is the canonical set of generators, are established. The exact value for the metric dimension of Cay\((\{(0,1),(1,0)\}:\mathbb Z_n \oplus \mathbb Z_m)\) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group \(D_{n}\) of order \(2n\) with a minimum set of generators is established. The metric dimension of a (di)graph is formulated as an integer programme. The corresponding linear programming formulation naturally gives rise to a fractional version of the metric dimension of a (di)graph. The fractional dual implies an integer dual for the metric dimension of a (di)graph which is referred to as the metric independence of the (di)graph. The metric independence of a (di)graph is the maximum number of pairs of vertices such that no two pairs are resolved by the same vertex. The metric independence of the \(n\)-cube and the Cayley digraph Cay\((\Delta:D_{n})\), where \(\Delta\) is a minimum set of generators for \(D_{n}\), are established. Cited in 1 ReviewCited in 43 Documents MSC: 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 05C20 Directed graphs (digraphs), tournaments 05C12 Distance in graphs 90C05 Linear programming 90C10 Integer programming Keywords:metric independence; integer programming; linear programming PDFBibTeX XMLCite \textit{M. Fehr} et al., Discrete Math. 306, No. 1, 31--41 (2006; Zbl 1085.05034) Full Text: DOI References: [1] Chartrand, G.; Eroh, L.; Johnson, M.; Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105, 99-113 (2000) · Zbl 0958.05042 [2] Chartrand, G.; Raines, M.; Zhang, P., The directed distance dimension of oriented graphs, Math. Bohemica, 125, 155-168 (2000) · Zbl 0963.05045 [3] Chartrand, G.; Raines, M.; Zhang, P., On the dimension of oriented graphs, Utilitas Math., 60, 139-151 (2001) · Zbl 1011.05020 [4] Currie, J.; Oellermann, O. R., The metric dimension and metric independence of a graph, J. Combin. Math. Combin. Comput., 39, 157-167 (2001) · Zbl 0986.05040 [5] Gallian, J. A., Contemporary Abstract Algebra (2002), Houghton Mifflin Company: Houghton Mifflin Company New York · Zbl 1051.00001 [6] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 [7] Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118 [8] S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report, 1994.; S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report, 1994. · Zbl 0865.68090 [9] O.R. Oellermann, C. Pawluck, A. Stokke, The metric dimension of Cayley digraphs of abelian groups, Ars Combin. 81 (2006), to appear.; O.R. Oellermann, C. Pawluck, A. Stokke, The metric dimension of Cayley digraphs of abelian groups, Ars Combin. 81 (2006), to appear. · Zbl 1189.05055 [10] Peters-Fransen, J.; Oellermann, O. R., The metric dimension of Cartesian products of graphs, Utilitas Math., 69, 33-41 (2006) · Zbl 1109.05041 [11] Scheinerman, E. R.; Ullman, D. H., Fractional Graph Theory (1997), Wiley: Wiley New York [12] Sebö, A.; Tannier, E., On metric generators of graphs, Informs, 29, 2, 383-393 (2004) · Zbl 1082.05032 [13] Slater, P. J., Leaves of trees, Congr. Numer., 14, 549-559 (1975) [14] Slater, P. J., Dominating and reference sets in a graph, J. Math. Phys. Sci., 22, 445-455 (1988) · Zbl 0656.05057 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.