TY - JOUR

T1 - On the metric dimension and diameter of circulant graphs with three jumps

AU - Imran, Muhammad

AU - Baig, A. Q.

AU - Rashid, Saima

AU - Semaničová-Feňovčíková, Andrea

N1 - Publisher Copyright:
© 2018 World Scientific Publishing Company.

PY - 2018/2/1

Y1 - 2018/2/1

N2 - Let G be a connected graph and d(u,v) be the distance between the vertices u and v in V (G). The diameter of G is defined as maxu,v V (G)d(u,v) and is denoted by diam(G). A subset of vertices W = {w1,w2,...,wk} is called a resolving set for G if for every two distinct vertices u,v V (G), there is a vertex wi W, 1 ≤ i ≤ k, such that d(u,wi)≠d(v,wi). A resolving set containing the minimum number of vertices is called a metric basis for G and the number of vertices in a metric basis is its metric dimension, denoted by dim(G). Metric dimension is a generalization of affine dimension to arbitrary metric spaces (provided a resolving set exists). Let F be a family of connected graphs Gn:F = (Gn)n ≥ 1 depending on n as follows: the order |V (G)| = φ(n) and limn→∞φ(n) = ∞. If there exists a constant C > 0 such that dim(Gn) ≤ C for every n ≥ 1 then we shall say that F has bounded metric dimension, otherwise F has unbounded metric dimension. If all graphs in F have the same metric dimension, then F is called a family of graphs with constant metric dimension. In this paper, we study the metric properties of an infinite class of circulant graphs with three generators denoted by Cn(1, 2,k) for any positive integer n ≥ 11 and when k = 5. We compute the diameter and determine the exact value of the metric dimension of these circulant graphs.

AB - Let G be a connected graph and d(u,v) be the distance between the vertices u and v in V (G). The diameter of G is defined as maxu,v V (G)d(u,v) and is denoted by diam(G). A subset of vertices W = {w1,w2,...,wk} is called a resolving set for G if for every two distinct vertices u,v V (G), there is a vertex wi W, 1 ≤ i ≤ k, such that d(u,wi)≠d(v,wi). A resolving set containing the minimum number of vertices is called a metric basis for G and the number of vertices in a metric basis is its metric dimension, denoted by dim(G). Metric dimension is a generalization of affine dimension to arbitrary metric spaces (provided a resolving set exists). Let F be a family of connected graphs Gn:F = (Gn)n ≥ 1 depending on n as follows: the order |V (G)| = φ(n) and limn→∞φ(n) = ∞. If there exists a constant C > 0 such that dim(Gn) ≤ C for every n ≥ 1 then we shall say that F has bounded metric dimension, otherwise F has unbounded metric dimension. If all graphs in F have the same metric dimension, then F is called a family of graphs with constant metric dimension. In this paper, we study the metric properties of an infinite class of circulant graphs with three generators denoted by Cn(1, 2,k) for any positive integer n ≥ 11 and when k = 5. We compute the diameter and determine the exact value of the metric dimension of these circulant graphs.

KW - Metric dimension

KW - basis

KW - circulant graph

KW - diameter

KW - resolving set

UR - http://www.scopus.com/inward/record.url?scp=85038968528&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85038968528&partnerID=8YFLogxK

U2 - 10.1142/S1793830918500088

DO - 10.1142/S1793830918500088

M3 - Article

AN - SCOPUS:85038968528

SN - 1793-8309

VL - 10

JO - Discrete Mathematics, Algorithms and Applications

JF - Discrete Mathematics, Algorithms and Applications

IS - 1

M1 - 1850008

ER -