# On Constant Metric Dimension of Some Generalized Convex Polytopes

Authors: Xuewu Zuo; Abid Ali; Gohar Ali; Muhammad Kamran Siddiqui; Muhammad Tariq Rahim; Anton Asare-Tuah
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Metric dimension is the extraction of the affine dimension (obtained from Euclidean spaceEd) to the arbitrary metric space. A family ℱ=Gn of connected graphs with n≥3 is a family of constant metric dimension if dimG=k (some constant) for all graphs in the family. Family ℱ has bounded metric dimension if dimGn≤M, for all graphs in ℱ. Metric dimension is used to locate the position in the Global Positioning System (GPS), optimization, network theory, and image processing. It is also used for the location of hospitals and other places in big cities to trace these places. In this paper, we analyzed the features and metric dimension of generalized convex polytopes and showed that this family belongs to the family of bounded metric dimension.


---

## Body

## 1. Introduction

LetG∈ℱ be a finite, simple, and undirected connected graph with vertex set V=VG=v1,v2,…,vn and edge set E=EG. The distance between two vertices is denoted by dvs,vj=dsj where dsj is the length of the shortest path between these vertices in G. Moreover, the distance dsj=djs because all graphs are undirected. An ordered subset W=w1,w2,…,wk of V is called a resolving set or locating set for G if for any two distinct vertices vs and vj, their codes are distinct with respect to Z, where codevs=dvs,z1,dvs,z2,…,dvs,zk∈Wk is a vector [1]. min:W:Wis a resolving set ofG=dimG=βG is called the metric dimension or locating number of G, and such a resolving set Z is called a basis set for G. To investigate Z is a basis set for G, it suffices to show that, for all different vertices x,y∈V∖W, their codes are also different because for any wj∈W,1≤j≤k, the jth component of the code is zero, while all other components are nonzero. For more details about βG and resolving sets, one can read [1–4].Lemma 1 (see [3]).
For a connected graphG with resolving set W, if dxs,w=dxj,w for all w∈V∖xs,xj, then W∩xs,xj≠∅.The join of two graphsG and H represented as G+H is a graph with VG+H=VG∪VH and EG+H=EG∪EH∪gh:g∈VGandh∈VH. Wn=Cn+K1 is a wheel graph of order n+1 for n≥3. fn=Pn+K1 is a fan graph obtained from the amalgamation of the path on n vertices with a single vertex graph Kn. Jahangir or gear graph J2n is obtained from the wheel graph W2n by deleting n-cycle edges alternatively; see in [4]. The following results appear in [5–7] for the graphs defined above.Theorem 1.
For wheel graphWn, fan graph fn, and Jahangir graph J2n, we have the following:(i)
βWn=⌊2n+2/5⌋, for every n≥7(ii)
βfn=2n+2/5, for every n≥7(iii)
βJ2n=⌊2n/3⌋, for every n≥4All the above three families of graphs are planar, and their metric dimension depends on the number of vertices in the graph, which shows that the metric dimension of these graphs is unbounded [8, 9]. Khuller et al. [10] clarified the properties of those graphs whose metric dimension is two.Theorem 2 (see [10]).
LetβG=2=W, where W=x,y⊂VG; then, the following holds:(i)
There is a unique shortest pathP between x and y(ii)
degx≤3 or degy≤3(iii)
For every other vertexz except x and y on P, degz≤5Definition 1 (see [11]).
A setK⊂ℝd is said to be convex if the line segment xy¯:λx+1−λy,0≤λ≤1, lies inside K for all distinct pairs of point x,y∈K.Definition 2 (see [11]).
The smallest convex set containingK (the intersection of the family of all convex sets that contain K) is called the convex hull of K, denoted by ConvK=∩K⊂SsSs, where Ss is a convex set.Definition 3 (see [11]).
A convex polytope is a bounded convex linear combination of convex sets.There are some families of graphs with constant metric dimension (see [2]); these families are generated by convex polytopes. The problem of finding βG is NP-complete (see [2]).Theorem 3 (see [12]).
LetSnp be a convex polytope with p-pendent vertices; then, dimSnp=3 for all n≥6.Theorem 4 (see [12]).
The metric dimension of convex polytopeTnp with p-pendent edges is 3 for every n≥6.Theorem 5 (see [12]).
βUnp=3 for n≥6, where Unp is a convex polytope graph with p-pendents.For more details about the metric dimension of certain families of graphs, see [13, 14]. Here, we will investigate generalized convex polytopes with pendent edges for their metric dimensions.


## 2. Main Results

This section is devoted to the main results which we proved for the newly introduced generalized convex polytopes. The convex polytopesSn, Tn, and Un were examined by Muhammad et al. for their metric dimensions in [2] and proved that these families belong to the family of constant metric dimension.Generalized convex polytopeSn,m is the generalization of Sn, with one n-sided and infinite face each, 3-sided faces being 2n, and 4-sided faces being nm−2, so the total number of faces is nm+2. The convex polytope Sn,mp is obtained from the generalized convex polytope graph by attached p-pendent vertices at the outer cycle of Sn,m, shown in Figure 1. The generalized convex polytope Sn.mp with p-pendents is a graph consisting of m cycles, with vertex and edge sets(1)VSn,mp=Xsj:1≤s≤n,1≤j≤m,ESn,mp=XsjXs+1j:1≤s≤n,1≤j≤m∪XsjXsj+1:1≤s≤n,1≤j≤m∪Xs+11Xs2:1≤s≤n.Figure 1
The generalized convex polytope graphSn,mp.In the set of edges, indices are taken as modulon and m.In [2], it was shown that βSn=3, for n≥6. In the result below, we proved that the metric dimension for the generalized convex polytope of Sn is still 3, which implies that Sn, Snp, and Sn,mp belong to the same family of constant metric dimension.Theorem 6.
LetG=Sn,mp be the generalized convex polytope graph defined above; then, βG=3 for n≥6 and m≥5.Proof.
Validating the mentioned theorem with the help of double inequalities, two cases are present:Case (i): forn is even.Letn=2α′ where α′≥3 is an integer. As N2x≥6 for all x∈Sn,m, it is guaranteed by [15] that βG≥3.ConsiderZ=X11,X21,Xl+11 to be an ordered subset of VSn,mp; to show that Z is a basis set for G, codes of the elements of VSn,mp∖Z with respect to Z are given in the following scheme:(2)rXs1|Z=s−1,s−2,α′−s+1,α′≥s≥3,2α′−s+1,2α′−s+2,s−α′−1,2α′≥s≥α′+2,rXs2|Z=1,1,α′,s=1,s,s−α′,α′−s+1,α′≥s≥2,α′,α′,1,s=α′+1,2α′−s+1,2α′−s+2,s−l,2α′≥s≥α′+2.Codes for the verticesXsm for 1≤s≤n and m≥3 are given in the following:(3)rXsm|Z=m−2,m−2,m−2+rXs2|Z.It proves thatβG≤3 implies that the metric dimension of G=Sn,mp is 3.Case (ii): forn is an odd integer.Letn=2α′+1, where α′≥3, and by [15], βG≥3; for reaching the conclusion, it remains to show that βG≤3.LetZ=X11,X21,Xl+11 be an ordered subset of Sn,mp; the formulation for the representation of nodes for VSn,mp∖Z with respect to Z is given in the following:(4)rXs1|Z=s−1,s−2,α′−s+1,α′≥s≥3,α′,α′,1,s=α′+2,2α′−s+2,2α′−s+3,s−α′−1,2α′+1≥s≥α′+3,rXs2|Z=1,1,α′,s=1,s,s−α′,α′−s,l−s+1,α′≥s≥2,α′+1,α′,1,s=α′+1,2α′−s+2,2α′−s+3,s−α′,n≥s≥α′+2.
The representation of the verticesXsm,1≤s≤n and m≥3, is as follows:(5)rXsm|Z=m−2,m−2,m−2+rXs2|Z.
It shows that, for any two distinct verticesx,y∈Sn,mp for odd n≥7, rx|Z≠ry|Z implying that βG≤3; this completes the proof.


## 3. Generalized Convex Polytope GraphTn,mp

In [16], Imran et al. proved the metric dimension of convex polytope Tn. The general form of Tn is denoted by Tn,m known as the generalized convex polytope (for short, GCP); this graph consists of one each n-sided and infinite face, respectively, and the number of 3-sided faces is 4n and 4-sided faces is nm−3. The GCP graph Tn,mp is a graph with p-pendent edges. Vertex and edge sets for G=Tn,mp are given in the following:(6)VTn,mp=Xsj:1≤s≤n,1≤j≤m,ETn,mp=XsjXs+1j:1≤s≤n,1≤j≤m∪XsjXsj+1:1≤s≤n,1≤j≤m−3∪Xs+1m−2Xsm−1:1≤s≤n∪Xsm−1Xsm:1≤s≤n.In the set of edges, indices are taken as modulon and m. In Figure 2, the graph G=Tn,mp is shown.Figure 2
GCP graphTn,mp.The result given below shows thatTn,mp belongs to the family of constant metric dimension.Theorem 7.
LetTn,mp be a GCP graph with p-pendents for all n≥6; then, βTn,mp=3.Proof.
AsN2v≥6 for all nonpendent vertices of Tn,mp, βTn,mp≥3 for all n≥6 by [15]. To complete the proof, it suffices to show that any ordered subset of the vertices of this graph is a resolving set.Case (i): forn is an even integer.Letn=2α′ with α′≥3; consider an ordered subset Z=X11,X21,Xl+11 of vertices of Tn,mp. The representation of vertices of VTn,mp∖Z with respect to Z is formulated as follows:(7)rXs1|Z=s−1,s−2,α′−s+1,α′≥s≥3,2α′−s+α′,2α′−s+2,s−α′−1,2α′≥s≥α′+2,rXs2|Z=1,1,α′,s=1,s,s−α′,α′−s+1,α′≥s≥2,α′,α′,1,s=α′+1,2α′−s+1,2α′−s+2,s−α′,2≥s≥α′+2.For3≤j≤m−2,(8)rXsj|Z=j−2,j−2,j−2+sXs2|Z.(9)rXsm−1|Z=2+1,2+1,α′+1,s=1,s+2,s+1,α′−s+2,α′−1≥s≥2,α′+2,α′+1,3,s=α′,α′+1,α′+2,3,s=α′+1,2α′−s+2,2α′−s+3,s−α′+2,α′+2≤s≤n−1,3,3,α′+2,s=n.Codes of the pendent vertices are given as follows:(10)rXsm|Z=1,1,1+rXsm−1|Z.From the above formulation, it is obvious that no two distinct vertices of the GCP with pendentsp have the same code with respect to Z, which implies that βTn,mp=3.Case (ii): forn is an odd integer.Letn=2α′+1 for α′≥3; suppose an ordered subset Z=x11,X21,Xl+11 of vertices VTn,mp; to show that Z is a basis set for Tn,mp, the formulation codes are given as follows:(11)rXs1|Z=s−1,s−2,α′−s+1,α′≥s≥3,α′,α′,1,s=α′+2,2α′−s+2,2α′−s+3,s−α′−1,n≥s≥α′+3,rXs2|Z=1,1,α′,s=1,s,s−1,α′−s+1,α′≥s≥2,α′+1,α′,1,s=α′+1,2α′−s+2,2α′−3,s−α′−1,n≥s≥α′+2.
Codes given to the vertices of other interior cycles are(12)rXsj|Z=j−2,j−2,j−2+rXs2|Z,for1≤j≤m−2.
Representation given to the second last cycleXsm−1 is(13)rXsm−1|Z=2+1,2+1,α′+1,s=1,s+2,s+1,α′−s+2,α′−1≥s≥2,α′+2,α′+1,3,s=α′,α′+2,α′+2,3,s=α′+1,2α′−s+3,2α′−s+4,s−α′+2,n−1≥s≥α′+2,3,3,α′+2,s=n.
The same representation is given to the pendent vertices:(14)rXsm|Z=1,1,1+rXsm−1|Z.
It shows thatZ is a resolving set for Tn,mp for n-odd and p-pendents, βTn,mp=3, and this completes the proof.


## 4. Generalized Convex Polytope GraphUn,mp

In [2], the graph Un is given, and a generalized graph Un,mp of Un is shown in Figure 3. The vertex and edge sets for this graph are given as follows:(15)VUn,mp=Xsj:1≤s≤n,s≤j≤m,EUn,mp=XsjXs+1j:1≤s≤n,1≤j≤m−1∪XsjXsj+1:1≤s≤n,1≤j≤m−4∪Xsm−3Xsm−2:1≤s≤n∪Xsm−2Xs+1m−3:1≤s≤n∪Xsm−2Xsm−1:1≤s≤n∪Xsm−1Xsm:1≤s≤n.Figure 3
The generalized convex polytope graphUn,mp.We will show that GCP graphUn,mp with n≥6 along with p-pendent vertices belongs to the family of constant metric dimension and its locating number is 3.Theorem 8.
LetUn,mp be a GCP graph for n≥6; then, dimUn,mp=3.Proof.
According to [15], dimG≥3 if and only if N2x≥6 or N3x≥8 for all x∈VG as N2x≥6 for every nonpendent vertex x of Un,mp implying that dimUn,mp≥3. To reach the conclusion, it remains to show that there exists a resolving set for Un,mp with exactly three elements. For this, consider the following two cases:
Case (i): for an integern is even. Let n=2α′, where α′≥3; take Z=X11,X21,Xl+11 to be an ordered subset of VUn,mp; to show that Z resolves vertices of the GCP, the representation of vertices of the GCP is shown as follows:(16)rXs1|Z=s−1,s−2,s−α′+1,α′≥s≥3,2α′−s+1,2α′−s+2,s−α′−1,2α′≥s≥α′+2.
For2≤j≤m−3,(17)rXsj|Z=j−1,j−1,j−1+rXs1|Z.Representation given to theXim−2 cycle is(18)rXsm−2|Z=3,3,α′+2,s=1s+2,s+1,α′−s+3,α′≥s≥2,α′+2,α′+2,3,s=α′+1,2α′−s+3,2α′−s+4,s−α′+2,2α′≥s≥α′+2.Representation of the vertices of the outer cycle is(19)rXsm−1|Z=1,1,1+rXsm−2|Z,1≤s≤n.Representation of pendent vertices is(20)rXsm|Z=2,2,2+rXsm−2|Z,1≤s≤n.It shows thatZ is a resolving set for GCP Un,mp implying that dimUn,mp=3.Case (ii): whenn is an odd integer. Let n=2α′+1 for α′≥3; let Z=X11,X21,Xl+11 be an ordered subset of the vertices of the GCP. To show that Z is a locating set for Un,mp, consider the codes’ formulation of the vertices of the GCP with respect to Z as(21)rX11|Z=s−1,s−2,α′−s+1,α′≥s≥3,α′,α′,1,s=α′+2,2α′−s+2,2α′−s+3,s−α′−1,2α′+1≥s≥α′+3.For2≤j≤m−2,(22)rXsj|Z=j−1,j−1,j−1+rXs1.Representation given to the vertices of the interior cycle is(23)rXsm−2|Z=3,3,α′+2,s=1,s+2,s+1,α′−s+3,α′≥s≥2,α′+3,α′+2,3,s=α′+1,α′+2,α′+1,4,s=α′+2,α′+1,α′,5,s=α′+3,2α′−s+4,2α′−s+5,s−α′+2,2α′+1≥s≥α′+3.Representation given to the nodes of the outer cycle is(24)rXsm−1|Z=1,1,1+rXsm−2|Z,1≤s≤n.Also, representation given to the nodes hanging is(25)Xsm|Z=2,2,2+rXsm−2|Z,1≤s≤n.It gives us thatZ is a resolving set for GCP Un,mp, implying that the metric dimension of GCP Un,mp is 3. □


## 5. Concluding Remarks

In this paper, we focus to study those graphs obtained from convex polytopes and examine that generalized convex polytopes (GCPs) also belong to the family of constant metric dimension such as their parent graphsSn, Tn, and Un.



---

*Source: 6919858-2021-08-10.xml*