×

Fault-tolerant metric dimension of circulant graphs. (English) Zbl 1474.05119

Summary: A set \(W\) of vertices in a graph \(G\) is called a resolving set for \(G\) if for every pair of distinct vertices \(u\) and \(v\) of \(G\) there exists a vertex \(w \in W\) such that the distance between \(u\) and \(w\) is different from the distance between \(v\) and \(w\). The cardinality of a minimum resolving set is called the metric dimension of \(G\), denoted by \(\beta(G)\). A resolving set \(W\) for \(G\) is fault-tolerant if \(W\setminus \lbrace w\rbrace\) for each \(w\) in \(W\). The fault-tolerant metric dimension of \(G\) is the size of a smallest fault-tolerant resolving set for \(G\), denoted by \(\beta'(G)\). In this paper, we study the fault-tolerant metric dimension of a family of circulant graphs \(X_{n,3}\) with connection set \(C=\lbrace 1,\dfrac{n}{2},n-1\rbrace\) and circulant graphs \(X_{n,4}\) with connection set \(C=\lbrace \pm 1,\pm 2\rbrace \).

MSC:

05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Borchert and S. Gosselin,The metric dimension of circulant graphs and Cayley hypergraphs, To appear in Util. Math. · Zbl 1485.05041
[2] P.S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang,On k-dimensional graphs and their bases, Period. Math. Hungar., 46(1)(2003) 9-15. · Zbl 1026.05033
[3] Z. Beerloiva, F. Eberhard, T. Erlebach. A. Hall, M. Hoffmann, M. Mihal´ak, L. Ram, Network discovery and verification, IEEE J. Selected Area in Commun., 24(2006) 21682181.
[4] G. Chartrand, L. Eroh, M.A. Johnson, O. R. Oellermann,Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105(2000) 99-113. · Zbl 0958.05042
[5] G. Chartrand, P. Zhang,The theory and applications of resolvability in graphs: A survey, Congr. Numer., 160(2003) 47-68. · Zbl 1039.05029
[6] M.A. Chaudhry, I. Javaid, M. Salman,Fault-Tolerant Metric and Partition Dimension of Graphs, Util. Math., 83(2010) 187-199. · Zbl 1242.05079
[7] C. Godsil and G. Royle,Algebraic graph theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, NewYork, (2001). · Zbl 0968.05002
[8] F. Harary, R.A. Melter,On the metric dimension of a graph, Ars. Combin., 2(1976) 191-195. · Zbl 0349.05118
[9] C. Hernando, M. Mora, P.J. Slater, D.R. Wood,Fault-Tolerant metric dimension of graphs, Proc. Internat. Conf. Convexity in Discrete Structures, Ramanujan Math. Society Lecture Notes, 5(2008) 81-85. · Zbl 1170.05306
[10] I. Javaid, M.T. Rahim and K. Ali,Families of regular graphs with constant metric dimension, Util. Math., 75 (2008) 21-33. · Zbl 1178.05037
[11] I. Javaid, M. Salman, M.A. Chaudhry, S. Shokat,Fault-Tolerance in Resolvability, Util. Math., 80(2009) 263-275. · Zbl 1197.05041
[12] S. Khuller, B. Raghavachari, A. Rosenfeld,Landmarks in graphs, Discrete Appl. Math., 70(1996) 217-229. · Zbl 0865.68090
[13] K. Liu, N. Abu-Ghazaleh,Virtual coordinate back tracking for void travarsal in geographic routing, Lecture Notes Comp. Sci., 4104(2006) 46-59.
[14] M. Salman, I. Javaid, M.A. Chaudhry,Resolvability in circulant graphs, Acta Mathematica Sinica, English Series, 9(2012) 1851-1864. · Zbl 1260.05053
[15] P.J. Slater,Leaves of trees, Cong. Numer., 14(1975) 549-559. Narjes Seyedi Department of Mathematics Science and Research Branch, Islamic Azad University Tehran, Iran seyedi.narjes@gmail.com Hamid Reza Maimani Mathematics Section, Department of Basic Sciences Shahid Rajaee Teacher Training University P.O. Box 16785-163 Tehran, Iran maimani@ipm
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.