Edge metric dimension of some classes of circulant graphs

被引:8
作者
Ahsan, Muhammad [1 ]
Zahid, Zohaib [1 ]
Zafar, Sohail [1 ]
机构
[1] Univ Management & Technol UMT, Dept Math, Lahore, Pakistan
来源
ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA | 2020年 / 28卷 / 03期
关键词
Edge metric dimension; edge metric generator; basis; resolving set; circulant graphs;
D O I
10.2478/auom-2020-0032
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G = (V (G), E (G)) be a connected graph and x, y is an element of V(G), d(x , y) = min{ length of x - y path } and for e is an element of E(G), d(x,e) = min{d(x, a), d(x , b)} , where e = ab. A vertex x distinguishes two edges e(1) and e(2), if d(e(1), x) not equal d(e(2), x). Let W-E = {w(1),w(2), ...,w(k)} be an ordered set in V(G) and let e is an element of E(G). The representation r(e vertical bar W-E) of e with respect to W-E is the k-tuple (d (e, w(1)) , d(e, w(2)) , ..., d(e,w(k))). If distinct edges of G have distinct representation with respect to W-E, then W-E is called an edge metric generator for G. An edge metric generator of minimum cardinality is an edge metric basis for G, and its cardinality is called edge metric dimension of G, denoted by edim(G). The circulant graph C-n (1, m) has vertex set {v(1), v(2), ..., v(n)} and edge set {v(i)v(i+1) : 1 <= i <= n - 1}boolean OR{v(n)v(1)}boolean OR{v(i)v(i+m) : 1 <= i <= n - m}boolean OR(v(n-m+i)v(i) : 1 <= i <= m}. In this paper, it is shown that the edge metric dimension of circulant graphs C-n (1, 2) and C-n (1, 3) is constant.
引用
收藏
页码:15 / 37
页数:23
相关论文
共 21 条
[1]   On the metric dimension of cartesian products of graphs [J].
Caceres, Jose ;
Hernando, Carmen ;
Mora, Merce ;
Pelayo, Ignacio M. ;
Puertas, Maria L. ;
Seara, Carlos ;
Wood, David R. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (02) :423-441
[2]   Resolvability and the upper dimension of graphs [J].
Chartrand, G ;
Poisson, C ;
Zhang, P .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2000, 39 (12) :19-28
[3]  
Chau K, 2017, OPUSC MATH, V37, P509, DOI 10.7494/OpMath.2017.37.4.509
[4]  
Harary F., 1976, ARS COMBINATORIA, V2, P191
[5]   A linear time algorithm for metric dimension of cactus block graphs [J].
Hoffmann, Stefan ;
Elterman, Alina ;
Wanke, Egon .
THEORETICAL COMPUTER SCIENCE, 2016, 630 :43-62
[6]   The metric dimension of Zn x Zn x Zn is [3n/2] [J].
Jager, Gerold ;
Drewes, Frank .
THEORETICAL COMPUTER SCIENCE, 2020, 806 :344-362
[7]  
Javaid I., 2012, WORLD APPL SCI J, V18, P1705, DOI [10.5829/idosi.wasj.2012.18.12.1590, DOI 10.5829/idosi.wasj.2012.18.12.1590]
[8]  
Javaid I., 2012, WORLD APPL SCI J, V18, P1800, DOI [DOI 10.5829/idosi.wasj.2012.18.12.11112, 10.5829/idosi.wasj.2012.18.12.11112]
[9]  
Javaid I, 2008, UTILITAS MATHEMATICA, V75, P21
[10]  
Johnson M, 1993, J Biopharm Stat, V3, P203, DOI 10.1080/10543409308835060