# On Adjacency Metric Dimension of Some Families of Graph

Authors: Ali N. A. Koam; Ali Ahmad; Muhammad Azeem; Adnan Khalil; Muhammad Faisal Nadeem
Journal: Journal of Function Spaces
 (2022)

---

## Abstract

Metric dimension of a graph is a well-studied concept. Recently, adjacency metric dimension of graph has been introduced. A setQa⊂VG is considered to be an adjacency metric generator for G if u1,u2∈V\Qa (supposing each pair); there must exist a vertex q∈Qa along with the condition that q is indeed adjacent to one of u1,u2. The minimum number of elements in adjacency metric generator is the adjacency metric dimension of G, denoted by dimaG. In this work, we compute exact values of the adjacency metric dimension of circulant graph Cn1,2, Möbius ladder, hexagonal Möbius ladder, and the ladder graph.


---

## Body

## 1. Introduction

LetG be a simple connected graph with vertex set V and edge set E. Let N be a set of nonnegative integers; we assume a function dG:V×V⟶N defined as
(1)dGx,y=lengthoftheshortestpathbetweenxandy.Then,V,dG is a metric space. A subset A⊂V is called a metric generator for G if it is the generator of the metric space V,dG; that is, every point of the space is uniquely determined by its distances from the elements of A. A minimum metric generator is the metric basis, and its cardinality is the metric dimension of G, denoted by dimG; for further detail of metric and their parameters, see [1–6]. The concept of metric dimension was first introduced by [7] in the problem of uniquely determining the location of an intruder in a network and was named as a locating set instead of metric generators. The same concept of metric generators or locating set was introduced by [8], and this time, they named it as resolving sets. Application of metric dimension to the navigation of robots in networks is studied in [9] and to chemistry in [10, 11]. This concept was further studied by many researchers (for instance, see [12, 13]); different studies of metric and its related parameters are studied in literature; for example, metric dimension of bilinear form graphs is found in [14], distance-regular graph is available in [15], in terms of dominating set [16], study of the corona product is found in [17], and some computer fields are attached to this topic found in [18, 19]. Several metric generators have since been developed and researched, including independent resolving sets [20], resolving dominant sets [21], strong resolving sets [22], and local metric sets [23].A subsetQa⊂V of the set of vertices is an adjacency metric generator of G if for every two vertices u1,u2∈V\Qa, there exists a vertex q∈Qa such that q is indeed adjacent to one of u1,u2. The minimum number of elements in the adjacency metric generator is the adjacency metric dimension of G and symbolized by dimaG. The idea of adjacency metric dimension was put forward by [24], and it is closed related to 1-locating dominating set [25]. The goal of this definition is to look at the metric dimension of the lexicographic product of graphs in terms of graph adjacency. For two graphs with n,K-orders, the researchers in [26, 27] had taken the corona product of both graphs; the resulted graph has (local) metric dimension n times the (local) adjacency metric dimension. They demonstrated that calculating the adjacency metric dimension is NP-hard as a result of this tight relationship.The adjacency metric generator of any graphG can be a metric generator in a correctly selected metric space, as pointed out in [26, 27]. Assume q is a positive number. Assume the dG,q:V×V⟶N is a distance function, which is defined as
(2)dG,qx,y=mindGx,y,q.Then, the metric dimension ofV,dG,2 is equal to the adjacency metric dimension of G. A subset Qa⊂V is the k adjacency metric generator for a graph G, if for each pair of vertices u1,u2∈V, there are at least k vertices v1,v2,⋯,vk∈Qa as a result dG,2u1,vi≠dG,2u2,vi, for each 1≤i≤k. For the minimum number (k) of members in the adjacency metric generator, the definition will be called as k adjacency metric dimension of a graph G, and here, it is symbolized by dima,jG.The adjacency metric dimension is an NP-hard problem [25, 28], and it is very important to determine its exact values for well-known families of graphs. The primary goal of this work is to determine the exact values of the adjacency metric dimension of particular graph families, notably circulant graphs Cn1,2, ladder, Möbius ladder, and hexagonal ladder graphs. To compute the adjacency metric dimension of these classes, we need the following proposition by Moreno et al. [29].Proposition 1 (see [29]).
IfG is a graph with G=n≥2, then dima,jG=j if and only if j∈1,2 and G∈P1,P2,.Remark 2 (see [29]).
IfG is a graph with G=n≥7, then dima,1G≥3.


## 2. Construction of Graphs

Circulant graphs are a type of graph that may be utilised in the construction of local area networks. Letv1,v2,⋯,vzz and n be the nonnegative with given conditions, vμ≠vν∀1≤μ<ν≤z, where 1≤vμ≤n/2. With the collection of vertices in an undirected graph V=v1,v2,⋯,vn and the set of edges E=vμvμ+vν:1≤μ≤n,1≤ν≤z, the indices are considered to be taken in modulo n condition, called a circulant graph, and it is symbolized by Cnv1,v2,⋯,vz. The generators are v1,v2,⋯,vz-numbers, and the edge vμvμ+vν is of type vν. Actually, we can observe that the Cnv1,v2,⋯,vz circulant graph is an r-regular graph, and the r given is
(3)c=2z,otherwise;.1cm,2z−1,ifn2∈v1,v2,⋯,vz.Möbius ladderMLm is built by a grid of m×1, and twist this grid at 180°; now, paste the extreme most left and right path of vertices as seen in Figure 1. It contains m-horizontal cycles of order four. For more study on ladder-type networks, see [30, 31]. The metric dimension of MLm is three [32].Figure 1
Möbius ladder graphMLm.Hexagonal Möbius ladderHMLm is built in [33], it can construct by dividing each horizontal edge of a square grid by inserting a new vertex, and it becomes a grid of m×1 with each cycle having order six; now, twist this grid at 180° and paste the extreme most left and right path of vertices as shown in Figure 2. This graph contains m-horizontal cycles of order six. The metric dimension of the hexagonal Möbius ladder network is three [33].Figure 2
Hexagonal Möbius ladder graphHMLm.LetLm be a ladder graph [34], with n≥3. We label the ladder graph as shown in Figure 3. The order and size of the ladder graph are 2n and 3n−2, respectively.Figure 3
Ladder graphLn.


## 3. Results on Adjacency Metric Dimension of Graphs

We compute the adjacency metric dimension of certain graph families in this section. LetCn1,2 be a circulant graph obtained from Cn by joining all the vertices at distance 2. Let n≥6; then, VCn1,2=n and ECn1,2=2n. In the next theorem, we compute the exact value of the adjacency metric dimension of the circulant graph Cn1,2.Theorem 3.
LetG=Cn1,2 be a circulant graph. Then,
(4)dimaG=3,ifn=6,7,8;.1cm,2n+36,ifn≡0,3,4,5mod6,n≥9,2n+36+1,ifn≡1,2mod6,n≥13.Proof.
We divide the proof of the theorem into three parts.
Part A. For the inequalitydimaG≤3, when n=6,7,8, let Qa=v1,v2,v3 as an adjacency metric generator; then, the representation of v1,v2,v3 are as follows v1=0,1,1,v2=1,0,1, and v3=1,1,0. For any vertex vk≠v1,v2,v3, we have the following representation:
(5)rvk∣Qa=a,b,c.where a=2, when k=4,⋯,n−2; otherwise, a=1. Also, b=1 when k=4,n, and c=1, when k=4,5; otherwise, both b,c are 0.
From the above discussion, we can say thatdimaG≤3.
Converse: on the contrary, assume thatdimaG=2, for n=7,8. Let Qa′=v1,v2 be a resolving set for adjacency metric dimension. Then, for any v∈VG\Qa′, the distance dv1,v,dv2,v∈1,1,1,2,2,1,2,2. Given VG−Qa′≥5, by the principle of Dirichlet’s box, two or more components of VG\Qa′ resulted in identical vectors of distance, and further, this implied as a contradiction. Now, for n=6, let Qa′=v1,vi,2≤i≤6; we have the same representations, that is, either rv2∣Qa′=rv5∣Qa′ or rv3∣Qa′=rv6∣Qa′. Let the adjacency metric generator Qa′=v2,vi,3≤i≤6; then, we have the same representations, that is, either rv1∣Qa′=rv4∣Qa′ or rv3∣Qa′=rv6∣Qa′. Let Qa′=vi,vj,3≤i≤5,4≤j≤6; then, we have the same representations, that is, rv1∣Qa′=rv4∣Qa′, rv3∣Qa′=rv5∣Qa′, or rv2∣Qa′=rv5∣Qa′. Therefore, dimaG≥3, concluding that dimaG=3.
Part B. Whenn≡0,3,4,5mod6,n≥9, we intend to use the induction method on the order of cycle; set the base step as n=9, which implies that dimaC9=4. Let Qa=v1,v2,v3,v4 be a resolving set for adjacency metric dimension. All vertices have the following representations:
(6)rvk∣Qa=a,b,c,d,k=1,2,⋯,n.where a,b,c,d=0, when k=1,2,3,4, respectively, and a=1 when k=2,3,8,9, b=1 when k=1,3,4,9, c=1 when k=1,2,4,5, and d=1 when k=2,3,5,6; otherwise, all values of a,b,c,d are 2. All the representations are different so
(7)dimaC9≤4.
On the contrary, assume thatdimaC9=3. On this contradiction, the following are some cases to defend it.Case 1.
Let the adjacency metric generatorQa′=vi,vj,vk,1≤i,j,k≤9, taking vertices in Qa′ with 0-size gap (consecutive vetices). Then, we have the same representations in vi,vj,vk­vi′,vj′; it means that Qa′ have the same representations with the vertices which are not adjacent to any of the vertex of Qa′.Case 2.
LetQa′=vi,vi+2,vi+3,1≤i≤6, taking vertices in Qa′ with 1- and 0-size gap, respectively. Then, we have the same representations in vi~vi′,vj′; it means that Qa′ have the same representations with the vertices which are adjacent to vi only.Case 3.
LetQa′=vi,vi+1,vi+3, 1≤i≤6, taking vertices again in Qa′ with 0- and 1-size gap, respectively. Then, we have the same representations in vi+3~vi′,vj′; it means that Qa′ have the same representations with the vertices which are adjacent to vi+3 only.Case 4.
LetQa′=vi,vi+2,vi+4,1≤i≤5, taking vertices in Qa′ with 1-size gap. Then, we have the same representations in vi+4~vi′,vj′; it means that Qa′ have the same representations with the vertices which are adjacent to vi+4 only.Case 5.
LetQa′=vi,vi+1,vi+4,1≤i≤5, with 0- and 2-size gap, respectively. Then, we have the same representations in vi+4~vi′,vj′, which simplifies that Qa′ have the same representations with the vertices which are adjacent to vi+4 only.Case 6.
LetQa′=vi,vi+2,vi+5,1≤i≤4, taking vertices in Qa′ with 1- and 2-size gap, respectively. Then, we have the same representations in vi+5~vi′,vj′, which means that Qa′ have the same representations with the vertices which are adjacent to vi+5 only.
Due to the nature of the adjacency metric generator with three cardinalities,Qa′ have the following gap size possibilities:
(i)
The first gap is even, and second is odd(ii)
The first gap is odd and the next is even(iii)
Both gaps are even(iv)
Both gaps are oddCase 7.
LetQa′=vi,vj,vk,1≤i,j,k≤9, taking vertices in above any sizes of gap possibilities. Then, we have the same representations in either vi,vj,vk­vi′,vj′ or only single vertex of Qa′ adjacent to both vertices, which have the same representations. From all above cases, dimaC9≠3. Hence, our base step is true:
(8)dimaC9=4.
Now, assume that it is also true forn=m, and we have to show that it is also true for n=m+1 which implies that
(9)dimaCm+1=2m+46.
Assume the assertion that(10)dimaCm+1=dimaCm+dimaC9−4.
Putting equations (8) and (9) in equation (10), we have
(11)dimaCm+1=2n+36+4−4=2n+46,where n+3/6=n+4/6.
Part C. Remaining cases whenn≡1,2mod6,n≥13.
Again, the method of induction can be used, and this implies that the base step becomes true forn=13 and as well dimaC13=5; for this purpose, let Qa=v1,v2,v5,v7,v11 be a resolving set for adjacency metric dimension; all the vertices have the following representations:
(12)rvk∣Q=a,b,c,d,e,k=1,2,⋯,n.where a,b,c,d=0 when k=1,2,5,7,11, respectively, and a=1 when k=2,3,12,13, b=1 when k=1,3,4,13, c=1 when k=3,4,6,7, d=1 when k=5,6,8,9, and e=1 when k=9,10,12,13; otherwise, all values of a,b,c,d are 2.(13)dimaC13≤5.
On the contrary, assume thatdimaC13=4. Let Qa′ be the adjacency metric generator with cardinality 4 having the following gap size possibilities.
(i)
All the gap sizes are even(ii)
All the gap sizes are odd(iii)
One gap size is odd, and others are even(iv)
One gap size is even, and others are oddCase 1.
LetQa′=vi,vj,vk,vl, 1≤i,j,k,l≤13, with any sizes of gap possibilities above defined. Then, we have the same representations in either vi,vj,vk,vl­vi′,vj′ or only single vertex of Qa′ adjacent to both vertices, which have the same representations. From all above cases, dimaC13≠4. Hence,
(14)dimaC13=5.
Now, assume that it is also true forn=m, and we have to show that it is also true for n=m+1, which leads to the assertion that
(15)dimaCm+1=2m+46+1.
Assuming that(16)dimaCm+1=dimaCm+dimaC13−4.
Putting equations (14) and (15) in equation (16), we have
(17)dimaCm+1=2n+36+5−4=2n+46+1,where n+3/6=n+4/6. This completes the proof of the theorem with all possible cases on order of the Cn graph.Theorem 4.
LetMLm be a Möbius ladder graph. Then,
(18)dimaMLm=3,ifm=4;.1cm,4,ifm=3,5,m−2,ifm≥6.Proof.
We divide the proof of the theorem into three parts.
Part A. LetQa=v1,v2,v5 be an adjacency metric generator, and those shown in Table 1 are the representations of all vertices for dimaML4≤3.
All the vertices have different representations, and it proves thatdimaML4≤3. On the contrary, suppose that dimaML4=2. By using Proposition 1, it is not possible, concluding that
(19)dimaML4=3.
Part B. Whenm=3,5, this adjacency metric generator is Qa=v1,v2,v4,v4+m/2 which claims that dimaMLm≤4. All vertices have the following representations:
(20)rvk∣Q=a,b,c,d,k=1,2,⋯,2m,where a,b,c,d=0 when k=1,2,4,4+m/2, respectively, and a=1 when k=2,m+1,2m, b=1 when k=1,3,m+2, c=1 when k=m−2,n,2m−1, and d=1 when m−1,m+1,2m; otherwise, all a,b,c,d are 2. It proves the claim that dimaMLm≤4; on the other hand, suppose that dimaMLm=3, when m=3,5.Case 1.
LetQa′=vi,vj,vk, 1≤i,j,k≤2m, taking vertices in Qa′ with 0-size gap. Then, we have the same representations in rvl∣Qa′=rvl′∣Qa′,1≤l≤m+1 and m+2≤l′≤2m.Case 2.
LetQa′=vi,vj,vk,1≤i,j,k≤2m, with the vertices in Qa′ with any size of gap discussed in Theorem 3, part 6 Then, we have the same representations in rvl∣Qa′=rvl′∣Qa′,1≤l≤m+1 and m+2≤l′≤2m. It means that when choosing the resolving set for adjacency metric dimension Qa′ with cardinality three and vertices with any gap size, there must exist two vertices with the same representations which have one belonging to l-domain and the second from l′-domain. From all above cases, dimaMLm≠3 for the values of m=3,5. Hence,
(21)dimaMLm=4.
Part C. Here, we will use the induction method. For the base step, we choosem=6; the dimaML6=4 having the adjacency metric generator Qa=v1,v3,v5,v7, and the following are the representations of all vertices:
(22)rvk∣Qa=a,b,c,d,k=1,2,⋯,2m,where a,b,c,d=0 when k=1,3,5,7, respectively, and a=1 when k=2,7,12, b=1 when k=2,4,9, c=1 when k=4,6,11, and d=1 when k=1,6,8; otherwise, all values of a,b,c,d are 2. It concludes that
(23)dimaML6≤4.
The contradiction side gives usdimaML6=3. For this contradiction, possible cases are discussed in the converse of part b of the theorem. One can evaluate from the discussion that Qa with cardinality three is not possible which implies that
(24)dimaML6=4.
Now, assume that it is also true form=l, and we have to show that m=l+1 which leads to the inductive step:
(25)dimaMLl+1=l−1.
Assume that(26)dimaMLl+1=dimaMLl+dimaML6−3.
Using equations (24) and (25) in equation (26), we have
(27)dimaMLl+1=m−2+4−3=m−1.
It completes the proof of the theorem with all possible cases onm-cycles of the Möbius ladder graph.Theorem 5.
LetHMLm be a hexagonal Möbius ladder graph. Then,
(28)dimaHMLm=3,ifm=2,4,ifm=3,6,ifm=4,m+3,ifm≥5.Proof.
We break the proof of the theorem into four parts according to the adjacency metric dimension.
Part A. In this part, we claim thatdimaHML2=3. For the case dimaHML2≤3, let the adjacency metric generator be Qa=v1,v2,v6, and those shown in Table 2 are the representations of all vertices of HML2 with respect to Qa.
In Table2, the given representations are different, and it proves that dimaHML2≤3; on the reverse, for inequality which is dimaHML2=2, using Proposition 1 is not true, concluding that
(29)dimaHML2=3.
Part B. This part contains the adjacency metric dimension of the hexagonal Möbius ladder graph withm=3; for this, let the adjacency metric generator be Qa=v1,v3,v5,v7, and those shown in Table 3 are the representations of all vertices according to Qa, which are again different, and it proves that dimaHML3≤4; on the reverse, inequality which is dimaHML3=3 is not true, and the following are some discussions to this side.Case 1.
LetQa′=vi,vj,vk,1≤i,j,k≤4m, taking vertices in Qa′ with any size of gap discussed in Theorem 3, part 6 Then, we have the same representations in either rv1∣Qa′=rvl′∣Qa′ or rvl∣Qa′=rvl′∣Qa′,1≤l≤2m+1 and 2m+2≤l′≤4m. It means that when choosing the resolving set of adjacency metric dimension Qa′ with cardinality three and vertices with any gap size, there must exist two vertices with the same representations which have one belonging to l-domain and the second from l′-domain. It is also possible that the same representations are in two vertices, and v1 is one of them, and the second vertex belongs to l′-domain. From all above cases, dimaML3≠3. Hence,
(30)dimaG=4.
Part C. FordimaHML4≤6, let the adjacency metric generator be Qa=v1,v2,v5,v7,v9,v12, and representations are shown in Table 4.Table 1
Representations of vertices with respect toQa=v1,v2,v5.
vkrvk∣v1rvk∣v2rvk∣v5vkrvk∣v1rvk∣v2rvk∣v510125121210162103212722142228122Table 2
Representations of vertices with respect toQa=v1,v2,v6.
vkrvk∣v1rvk∣v2rvk∣v6vkrvk∣v1rvk∣v2rvk∣v610125121210262103212722142228122Table 3
Representations of vertices with respect toQa=v1,v3,v5,v7.
vkrvk∣v1rvk∣v3rvk∣v5rvk∣v7vkrvk∣v1rvk∣v3rvk∣v5rvk∣v7102217122021122822213202292122421121022225220211221262211121222Table 4
Representationsrvk∣Qa of vertices with respect to Qa=v1,v2,v5,v7,v9,v12.
vkv1v2v5v7v9v12vkv1v2v5v7v9v1210122129122202210222210222212321222211222221422122212222220522022213221221622112214222222722202215222122822211216122222The representations given in Table4 prove that dimaHML4≤6. On contrary, suppose that dimaHML4=5; the following are some discussions to the side of this contradiction.Case 1.
LetQa′=vi,vj,vk,vl,vm,1≤i,j,k,l,m≤4m, taking vertices in Qa′ with any size of gap already discussed above in the theorem. Then, we have the same representations in either rv1∣Qa′=rvl′∣Qa′ or rvl∣Qa′=rvl′∣Qa′,1≤l≤2m+1 and 2m+2≤l′≤4m. It means that when choosing the resolving set for adjacency metric dimension Qa′ with cardinality five and vertices with any gap size, there must exist two vertices with the same representations which have one belonging to l-domain and the second from l′-domain. It is also possible that the same representations are in two vertices and v1 is one of them, and the second vertex belongs to l′-domain. From all above cases, dimaML4≠5. Hence,
(31)dimaG=6.
Part D. In this part for the proof ofdimaHMLm=m+3 where m≥5, we will apply the induction method and the base case for m=5, which implies that dimaHML5=8, to prove that dimaHML5≤8; the following are the representations with respect to the adjacency metric generator Qa=v1,v2,v4,v7,v9,v11,v13,v16:
(32)rvk∣Qa=a,b,c,d,e,f,g,h,k=1,2,⋯,4m.where a,b,c,d,e,f,g,h=0 when k=1,2,4,7,9,11,13,16, and a=1 when k=2,11,20, b=1 when k=1,3, c=1 when k=3,5, d=1 when k=6,8,17, e=1 when k=8,10,19, f=1 when k=1,10,12, g=1 when k=3,12,14, and h=1 when k=15,17; otherwise, all values of a,b,c,d,e,f,g,h are 2. All the representations show that there are no two vertices with the same representation; hence,
(33)dimaHML5≤8.
On the contrary, suppose thatdimaHML5=7; the following are some discussions to the side of contradiction.Case 1.
LetQa′=vi1,vi2,vi3,vi4,vi5,vi6,vi7,1≤ij≤4m and 1≤j≤7, taking vertices in Qa′ with any size of gap discussed in Theorem 3, part 6 Then, we have the same representations in either rv1∣Qa′=rv2∣Qa′ or rv1∣Qa′=rvl′∣Qa′ or rvl∣Qa′=rvl′∣Qa′,1≤l≤2m+1 and 2m+2≤l′≤4m. It means that when choosing the resolving set of adjacency metric dimension Qa′ with cardinality seven and vertices with any gap size, there must exist two vertices with the same representations which have one belonging to l-domain and the second from l′-domain. It is also possible that the same representations are in two vertices and v1 is one of them, and the second vertex belongs to l′-domain. From all above cases, dimaHML5≠7. Hence,
(34)dimaHML5=8.
Now, assume that the assertion is true form=l:
(35)dimaHMLm=l+3.
We have to show that it is also true form=l+1. Suppose
(36)dimaHMLm=dimaHMLm+1+dimaHML5−7.
Plugging the values of equations (34) and (35) in equation (36), we have
(37)dimaHMLl+1=l+3+8−7=l+4.
As a result, the result holds for all positive integersm≥5. It also completes the all possible cases that we assume on the very start of the proof.Theorem 6.
LetLn be a ladder graph with n≥3. Then,
(38)dimaLn=n−n+14.Proof.
We prove thatdimaLn=n−n+1/4 with the induction method and the base step is n=3 which implies that dimaL3=2. If we assume on the contrary it is not possible that dimaL3=1, for dimaL3≤2, all vertices have the following representations with respect to Qa=v1,v5:
(39)rvk∣Qa=a,b,k=1,2,⋯,4n.where a,b=0 when k=1,5, respectively, and a=1 when k=2,3, b=1 when k=3,6; otherwise, all values of a,b are 2. All the representations show that there are no two vertices with the same representation; hence,
(40)dimaL3=2.
Now, assume that the assertion is true forn=k:
(41)dimaLk=k−k+14.
We have to show that it is also true forn=k+1. Suppose
(42)dimaLm=dimaLm+1+dimaL3−1.
Using equations (40) and (41) in equation (42), we have
(43)dimaLk+1=k−k+14+2−1,=k+1−k+14,=k+1−k+24,where k+1/4=k+2/4. As a consequence, the result holds for all positive integers for n≥3, which completes the proof.


## 4. Conclusion

In this article, we studied the adjacency metric dimension of circulant, ladder, Möbius ladder, and hexagonal Möbius ladder graphs. It is known that adjacency metric dimension is a useful parameter in localization, networking, and some robot navigation ideas. Therefore, it is interesting to find adjacency metric generators for generalized classes of graphs. We demonstrated that in adjacency metric generators, all graphs have inconstant numbers of members and that each graph follows the modification of parameters or order.



---

*Source: 6906316-2022-06-25.xml*