Narjes Seyedi, Hamid Reza Maimani

DOI Number
First page
Last page


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 \left\lbrace w\right\rbrace $ for each $w$ in $W'$, is also a resolving set and the fault-tolerant metric dimension of $G$ is the minimum cardinality of such a set, denoted by $\beta'(G)$. The circulant graph is a graph with vertex set $\mathbb{Z}_{n}$, an additive group of integers modulo $n$, and two vertices labeled $i$ and $j$ adjacent if and only if $i -j \left( mod \ n \right)  \in C$, where $C \in \mathbb{Z}_{n}$ has the property that $C=-C$ and $0 \notin C$. The circulant graph is denoted by $X_{n,\bigtriangleup}$ where $\bigtriangleup = \vert C\vert$. 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$.


Circulant graphs; resolving set; fault-tolerant metric dimension

Full Text:



A. Borchert and S. Gosselin, The metric dimension of circulant graphs and Cayley hypergraphs, To appear in Util. Math.

P.S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hungar., 46(1)(2003) 9-15.

Z. Beerloiva, F. Eberhard, T. Erlebach. A. Hall, M. Hoffmann, M. Mihalak, L. Ram, Network discovery and verification, IEEE J. Selected Area in Commun., 24(2006) 2168-2181.

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.

G. Chartrand, P. Zhang, The theory and applications of resolvability in graphs: A survey, Congr. Numer., 160(2003) 47-68.

M.A. Chaudhry, I. Javaid, M. Salman, Fault-Tolerant Metric and Partition Dimension of Graphs, Util. Math., 83(2010) 187-199.

C. Godsil and G. Royle, Algebraic graph theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, NewYork, (2001).

F. Harary, R.A. Melter, On the metric dimension of a graph, Ars. Combin., 2(1976) 191-195.

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. So-

ciety Lecture Notes, 5(2008) 81-85.

I. Javaid, M.T. Rahim and K. Ali, Families of regular graphs with constant metric dimension, Util. Math., 75 (2008) 21-33.

I. Javaid, M. Salman, M.A. Chaudhry, S. Shokat, Fault-Tolerance in Resolvability, Util. Math., 80(2009) 263-275.

S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70(1996) 217-229.

K. Liu, N. Abu-Ghazaleh, Virtual coordinate back tracking for void travarsal in geographic routing, Lecture Notes Comp. Sci., 4104(2006) 46-59.

M. Salman, I. Javaid, M.A. Chaudhry, Resolvability in circulant graphs, Acta Mathematica Sinica, English Series, 9(2012) 1851-1864.

P.J. Slater, Leaves of trees, Cong. Numer., 14(1975) 549-559.

DOI: https://doi.org/10.22190/FUMI1904781S


  • There are currently no refbacks.

© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)