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

Muhammad Imran, A. Q. Baig, Saima Rashid, Andrea Semaničová-Feňovčíková

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number1850008
JournalDiscrete Mathematics, Algorithms and Applications
Volume10
Issue number1
DOIs
Publication statusPublished - Feb 1 2018

Keywords

  • Metric dimension
  • basis
  • circulant graph
  • diameter
  • resolving set

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On the metric dimension and diameter of circulant graphs with three jumps'. Together they form a unique fingerprint.

Cite this