# On the Geodesic Identification of Vertices in Convex Plane Graphs

Authors: Fawaz E. Alsaadi; Muhammad Salman; Masood Ur Rehman; Abdul Rauf Khan; Jinde Cao; Madini Obad Alassafi
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

A shortest path between two verticesu and v in a connected graph G is a u−v geodesic. A vertex w of G performs the geodesic identification for the vertices in a pair u,v if either v belongs to a u−w geodesic or u belongs to a v−w geodesic. The minimum number of vertices performing the geodesic identification for each pair of vertices in G is called the strong metric dimension of G. In this paper, we solve the strong metric dimension problem for three convex plane graphs by performing the geodesic identification of their vertices.


---

## Body

## 1. Introduction

The identification of vertices of a graph using various graph parameters is a fascinating problem for researchers. In the literature, almost over 1000 articles are contributed to explore the identification of vertices in a remarkable way by using various graph theory concepts including graph coloring, labeling of vertices, domination in graphs, vertex covering, graph automorphisms with symmetry breaking technique, independence of vertices, and by defining the metric on graphs, to name a few.By defining the metric on a graph, the problem of identification of vertices attracted many researchers due to its significant applications in several extents including verification, security, and discovery of networks [1], the chemistry of pharmaceutics for drug designing [2], mastermind game strategies [3], navigation of robots [4], connected joins in graphs [5], and solution of coin weighing problems [6]. Because of these practical significances of this problem, from the last two decades, numerous researchers identified vertices of a graph by considering the metric-related well-known concept of the metric dimension [2, 7, 8]. Later on, many researchers extended the study of this concept by defining its several variations including the fractional metric dimension [9], the resolving domination [10], the doubly metric dimension [11], the independent metric dimension [12], the weighted metric dimension [13], the k-metric dimension [14], the solid metric dimension [15], the mixed metric dimension [16], the local metric dimension [17], the simultaneous metric dimension [18], the strong metric dimension [5], and the connected metric dimension [19].This paper is aimed to identify the vertices of three convex plane graphs by using geodesics between them, which provides the strong metric dimension of these graphs.


## 2. Geodesic Identification: The Strong Metric Dimension

LetG be a simple connected graph. A shortest path between two vertices x and y in G is known as a x−y geodesic. The geodesic identification of vertices is equivalently the strong resolvability of vertices, which is defined as follows: a vertex w of G performs the geodesic identification for the vertices in a pair x,y (i.e., w strongly resolves the vertices in a pair x,y) if either x belongs to (lies on) a y−w geodesic or y belongs to (lies on) a x−w geodesic. A set S of vertices in G is said to be a strong metric generator for G if for every pair of vertices of G, there is always a vertex in S which performs the geodesic identification for the vertices in the pair. The cardinality of such a smallest set S is called the strong metric dimension of G, denoted by sdimG [5].Sebö and Tannier initiated the study of geodesic identification of vertices by defining the concepts of strong metric generator and strong metric dimension in 2004 [5]. Later on, this study was extended by many researchers, and they contributed to the literature with a variety of remarkable research work. To develop the readers interest, we shortly survey the strong metric dimension problem as follows:(i)
The strong metric dimension problem has been solved for Sierpiński graph in [20], for hamming graphs in [21], for some convex polytopes in [22, 23], for wheel related graphs (including n-fold wheel, sunflower, helm, and friendship graphs) in [24], for path, cycle, complete, complete bipartite, and tree graphs in [25], for Cayley graphs in [26], for Cartesian sum graphs in [27], for the power graph of a finite group in [28], for distance-hereditary graphs in [29], for generalized butterfly and starbarbell graphs in [30], for antiprism and king graphs in [31], for sun, windmill, and Möbius ladder graphs in [32], and for crossed prism in [33].(ii)
The strong metric dimension of various products of graphs including Cartesian product, direct product, strong product, lexicographic product, rooted product, and corona product has been supplied through the articles in [26, 27, 30, 31, 33–39].(iii)
The fractional version of the strong metric dimension problem has been introduced in [40] and further studied for various graphs and graph products in [41, 42].(iv)
The technique of the computation of strong metric dimension with the concept of the vertex cover number has been provided in [38] by proposing the construction of strong resolving graph of a connected graph. Furthermore, the article in [25] supplied some fundamental realizations and characterizations of the strong metric dimension problem in connection with the strong resolving graph.(v)
To solve the strong metric dimension problem, the genetic algorithmic approach is used in [43], and the variable neighborhood search method is used in [44].(vi)
The article in [45] supplied the Nordhaus–Gaddum type results whenever the strong metric dimension problem was solved for graphs and their compliments.(vii)
To compute the strong metric dimension of graphs using optimization techniques, the integer linear programming model for the strong metric dimension problem was formulated in [22].(viii)
The complexity and the optimal approximability in the computation of the strong metric dimension problem of graphs have been discussed in [38, 46].(ix)
Furthermore, we refer a survey in [47] and the Ph.D. thesis in [48] to the readers having interest in the computation of the strong metric dimension of graphs.With this paper, we extend the study of the identification of vertices using the concept of strong metric dimension. We consider three convex plane graphs and investigate their strong metric dimension by performing the geodesic identification of vertices in the graphs.


## 3. Basic Works

LetG be a simple and connected graph with vertex set VG and edge set EG. We denote the adjacent vertices u and v by u∼v and nonadjacent vertices by u≁v in G. The neighborhood of a vertex v in G is Nv=u∈VG:u∼vinG. The number of vertices adjacent with a vertex v is called its degree and is denoted by dv. The metric on G is a mapping d:VG×VG⟶ℤ+∪0 defined by dx,y=l, where l is the length of (the number of edges in) a x−y geodesic. Accordingly, a vertex w of G performs the geodesic identification for the vertices in a pair x,y if and only if either dx,w=dx,y+dy,wordy,w=dy,x+dx,w.Kratica et al. in [22] supplied the following two results, which are useful tools for the geodesic identification of vertices.Lemma 1.
(see [22]). Let u,v be a pair of distinct vertices in a connected graph G such that(1)du,v≥dw,v,∀w∈Nu,du,v≥dw,u,∀w∈Nv.Then, there is no vertex inVG−u,v which performs the geodesic identification for the pair u,v.Proposition 1.
(see [22]). If S is a strong metric generator for a connected graphs G, then for every pair u,v of distinct vertices in G satisfying both the conditions in (1), either u∈S or v∈S.
For a connected graphG, the number diamG=maxeccv=maxu∈VGdv,u;v∈VG is called the diameter of G, where eccv is the eccentricity of a vertex v. The following result, provided by Kratica et al. in [22], is also a useful tool for the geodesic identification of vertices.Proposition 2.
(see [22]). If S is a strong metric generator for a connected graphs G, then for every pair u,v of distinct vertices in G such that du,v=diamG, either u∈S or v∈S.
A vertexv of G for which dv=1 is known as a leaf. The following result describes the geodesic identification of leaves in a connected graph.Lemma 2.
IfS is a strong metric generator for a connected graphs G and u,v is a pair of distinct leaves in G, then either u∈S or v∈S.Proof.
Sinceu and v are leaves, du=1=dv. Without loss of generality, let Nu=x and Nv=y. Now, if x=y, then(2)du,v=2>dx,v,du,v=2>dx,u.
Ifx≠y, then(3)du,v=du,x+dx,y+dy,v=dx,y+2,(4)dx,v=dx,y+dy,v=dx,y+1<du,v,(5)dy,u=dy,x+dx,u=dx,y+1<du,v.
The identities (2)–(5) provide that the pair u,v satisfies both the conditions in (1), and hence, Proposition 1 yields the required result.
Lemma2 supplies the following straightforward proposition.Proposition 3.
IfS is a strong metric generator for a connected graph G and L is the set of m leaves in G, then S must contain at least m−1 leaves from L.


## 4. Convex Plane Graphs

A graphG is convex if a straight line joining any two vertices of G entirely lies within the region occupied by G. A graph G is a plane graph if it is free from crossing of edges. Throughout this section, it should be helpful to keep in mind the following points:(i)
The right arrow⟶ in the supper script of the notation of geodesics will indicate forward nature of geodesics (see Figure 1).(ii)
The left arrow← in the supper script of the notation of geodesics will indicate backward nature of geodesics (see Figure 1).(iii)
The indices greater thann or less than 1 will be taken modulo n.Figure 1
Illustrating forward and backward natures ofai−ai+k and ai−ai+k−1 geodesics.In the next sections, we investigate the strong metric dimension of three convex plane graphs.


### 4.1. Convex Plane GraphSnp

The graph of a convex polytopeSn is defined in [49] for n≥3. The vertex set of Sn is VSn=ai,bi,ci,di;1≤i≤n, and its edge set is(6)ESn=ai∼ai+1,ai∼bi,bi∼bi+1,bi∼ai+1;1≤i≤n∪bi∼ci,ci∼ci+1,ci∼di,di∼di+1;1≤i≤n.The convex plane graphSnp (p for pendant) can be obtained from the graph of a convex polytope Sn by attaching one pendant vertex (leaf) ei to the vertex di of Sn for each 1≤i≤n (see Figure 2) [50]. Thus, the vertex and edge sets of Snp are(7)VSnp=VSn∪ei;1≤i≤n,ESnp=ESn∪di∼ei;1≤i≤n.Figure 2
The general half view of the convex plane graphSnp.We investigate the strong matrix dimension ofSnp by supplying the following main result.Theorem 1.
Forn≥3, let Snp be a convex plane graph. Then,(8)sdimSnp=n,whennis odd,3n2,whennis even.The next four lemmas will lead the proof of Theorem1.Lemma 3.
For odd values ofn≥3, if S is a strong metric generator for Snp, then S≥n.Proof.
Letn=2k+1 with k≥1, and consider Table 1 for 1≤i≤n.
InSnp, note the following points:P1:L=ei;1≤i≤n is the set of leaves.P2: for each1≤i≤n, dai,ei+k=k+4. It follows, according to Table 1, that the pair ai,ei+k satisfies both the conditions in (1).P3:diamSnp=k+4=dai,ei+k for each 1≤i≤n.
From P1, without loss of generality, we suppose thate2,e3,…,en∈S by Proposition 3. Then, since the pair ak+1,e1 satisfies P2 and P3, we have either ak+1∈S or e1∈S, by Propositions 1 and 2. Hence, S≥n−1+1=n.Table 1
Vertices willing to perform the geodesic identification inSnp.
VertexvNvdw,⋅ for all w∈Nvaiai+1,ai−1,bi−1,bidw,ei+k=k+3ei+kdi+kdw,ai=k+3Lemma 4.
For even values ofn≥4, if S is a strong metric generator for Snp, then S≥3n/2.Proof.
Letn=2k with k≥2, and consider Table 2 for 1≤i≤n.
InSnp, the following points hold:P1:L=ei;1≤i≤n is the set of leaves.P2: for each1≤i≤n, dai,ei+k−1=dai,ei+k=dbi,ei+k=k+3. Therefore, Table 2 yields that the pairs ai,ei+k−1,ai,ei+k and bi,ei+k satisfy both the conditions in (1) for each 1≤i≤n. Table 2 further implies that the pair aj,aj+k satisfies both the conditions in (1) because daj,aj+k=k for each 1≤j≤k.P3:diamSnp=k+3=dai,ei+k−1=dai,ei+k=dbi,ei+k for each 1≤i≤n.
Due to P1, without loss of generality, we lete2,e3,…,en∈S, by Proposition 3. Then, as the pairs ak+2,e1,ak+1,e1 and bk+1,e1 satisfy P2 and P3, we must have either ak+2∈S or ak+1∈S or bk+1∈S or e1∈S, by Propositions 1 and 2. For the geodesic identification of these three pairs, it is enough to consider e1 in S. Furthermore, for each 1≤j≤k, either aj∈S or aj+k∈S, due to P2 and Proposition 1. Hence, S≥n−1+1+k=3n/2.Table 2
Vertices willing to perform the geodesic identification inSnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bi−1,bidw,ai+k∈k−1,kdw,ei+k−1∈k+2,k+3dw,ei+k∈k+2,k+3ai+kai+k−1,ai+k+1,bi+k−1,bi+kdw,ai∈k−1,kbiai,ai+1,bi−1,bi+1,cidw,ei+k∈k+2,k+3ei+k−1di+k−1dw,ai=k+2ei+kdi+kdw,ai=k+2dw,bi=k+2Lemma 5.
Ifn=2k+1 with k≥1, then the set S=e1,e2,…,en⊂VSnp is a strong metric generator for Snp.Proof.
For anys∈S and any u∈VSnp−s, since the vertex s performs the geodesic identification for the pair s,u, we have to perform the geodesic identification for every pair x,y of distinct vertices with x,y∈VSnp−S. For each 1≤i≤n, consider the following ai−ei+k geodesics of length k+4:(9)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k∼bi+k∼ci+k∼di+k∼ei+k,(10)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k∼ci+k∼di+k∼ei+k,(11)P3i⟶:ai∼bi∼ci∼ci+1∼ci+2∼⋯∼ci+k∼di+k∼ei+k,(12)P4i⟶:ai∼bi∼ci∼di∼di+1∼di+2∼⋯∼di+k∼ei+k,(13)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k=ai+k+1∼bi+k∼ci+k∼di+k∼ei+k,(14)P2i←:ai∼bi−1∼bi−2∼⋯∼bi−k=bi+k+1∼bi+k∼ci+k∼di+k∼ei+k,(15)P3i←:ai∼bi−1∼ci−1∼ci−2∼⋯∼ci−k=ci+k+1∼ci+k∼di+k∼ei+k,(16)P4i←:ai∼bi−1∼ci−1∼di−1∼di−2∼⋯∼di−k=di+k+1∼di+k∼ei+k.
Each geodesic, listed from (9) to (16), provides that the vertex ei+k∈S performs the geodesic identification for every pair x,y with x,y∈VSnp−S. It follows that S is a strong metric generator for Snp.Lemma 6.
Ifn=2k with k≥2, then the set S=a1,a2,…,ak,e1,e2,…,en⊂VSnp is a strong metric generator for Snp.Proof.
We have to perform the geodesic identification each pairu,v of distinct vertices for u,v∈VSnp−S because for any s∈S and any v∈VSnp−s, the pair s,v possesses the geodesic identification by the vertex s. For each 1≤i≤n, consider the following ai−ei+k−1 geodesics and ai−ei+k geodesics of length k+3:(17)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k−1∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(18)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(19)P3i⟶:ai∼bi∼ci∼ci+1∼ci+2∼⋯∼ci+k−1∼di+k−1∼ei+k−1,(20)P4i⟶:ai∼bi∼ci∼di∼di+1∼di+2∼⋯∼di+k−1∼ei+k−1,(21)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k−1=ai+k+1∼bi+k∼ci+k∼di+k∼ei+k,(22)P2i←:ai∼bi−1∼bi−2∼⋯∼bi−k−1=bi+k+1∼bi+k∼ci+k∼di+k∼ei+k,(23)P3i←:ai∼bi−1∼ci−1∼ci−2∼⋯∼ci−k−1=ci+k+1∼ci+k∼di+k∼ei+k,(24)P4i←:ai∼bi−1∼ci−1∼di−1∼di−2∼⋯∼di−k−1=di+k+1∼di+k∼ei+k.
Except the pairsai,aj for k≤i≤n−1 and i+1≤j≤n, all the pairs of vertices owned the geodesic identification by the vertices ei+k and ei+k−1 due to the geodesics listed from (17) to (24). By considering the following ak−an geodesic(25)P⟶:ak∼ak+1∼ak+2∼⋯∼an−1∼an,we get that the vertex ak performs the geodesic identification for all the remaining pairs ai,aj. Hence, S is a strong metric generator for Snp.Proof.
(Theorem1). The lower bound for the strong metric dimension of Snp is provided by Lemmas 3 and 4, whereas the upper bound is due to Lemmas 5 and 6.


### 4.2. Convex Plane GraphTnp

The graph of a convex polytopeTn is defined in [49] for n≥3. The vertex set of Tn is VTn=ai,bi,ci,di;1≤i≤n, and its edge set is(26)ETn=ai∼ai+1,ai∼bi,bi∼bi+1,bi∼ai+1,bi∼ci;1≤i≤n∪ci∼ci+1,ci∼di,ci∼di−1,di∼di+1;1≤i≤n.The convex plane graphTnp (p for pendant) can be obtained from the graph of a convex polytope Tn by attaching one pendant vertex (leaf) ei to the vertex di of Tn for each 1≤i≤n (see Figure 3) [50]. Accordingly, the vertex and edge sets of Tnp are(27)VTnp=VTn∪ei;1≤i≤n,ETnp=ETn∪di∼ei;1≤i≤n.Figure 3
The general half view of the convex plane graphTnp.Mainly, we have the following result for the strong metric dimension ofTnp.Theorem 2.
Forn≥3, let Tnp be a convex plane graph. Then,(28)sdimTnp=2n,whennis odd,5n2,whennis even.The proof of Theorem2 will be followed after the next four lemmas.Lemma 7.
For odd values ofn≥3, if S is a strong metric generator for Tnp, then S≥2n.Proof.
Letn=2k+1 with k≥1, and consider Table 3 for 1≤i≤n.
Note the following three points inTnp:P1:L=ei;1≤i≤n is the set of leaves.P2:dai,ei+k−1=dai,ei+k=dbi,ei+k=k+3 and dai,ci+k=k+2 for each 1≤i≤n. Hence, Table 3 ensures that pairs of vertices in Tnp satisfying both the conditions in (1) are ai,ei+k−1,ai,ei+k,bi,ei+k, and ai,ci+k for each 1≤i≤n.P3:diamTnp=k+3=dai,ei+k−1=dai,ei+k=dbi,ei+k for each 1≤i≤n.
By Proposition3, let us take e2,e3,…,en∈S without loss of generality due to P1. Then, from the remaining pairs ak+3,e1,ak+2,e1, and bk+2,e1, we must have either ak+3∈S or ak+2∈S or bk+2∈S or e1∈S, by Propositions 1 and 2, because these pairs are satisfying P2 and P3. Here, it can be seen, by letting e1∈S only, that all these pairs possess the geodesic identification by the vertex e1. Furthermore, for each 1≤i≤n, from the pair ai,ci+k satisfying P2, either ai∈S or ci+k∈S, by Proposition 1. Hence, S≥n−1+1+n=2n.Table 3
Vertices willing to perform the geodesic identification inTnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bi−1,bidw,ci+k=k+1dw,ei+k−1∈k+2,k+3dw,ei+k∈k+2,k+3biai,ai+1,bi−1,bi+1,cidw,ei+k∈k+2,k+3ci+kbi+k,ci+k−1,ci+k+1,di+k−1,di+kdw,ai∈k+1,k+2ei+k−1di+k−1dw,ai=k+2ei+kdi+kdw,ai=k+2dw,bi=k+2Lemma 8.
For even values ofn≥4, if S is a strong metric generator for Tnp, then S≥5n/2.Proof.
Letn=2k with k≥2, and consider Table 4 for 1≤i≤n.
The following points are considerable inTnp:P1:L=ei;1≤i≤n is the set of leaves.P2:dai,ei−1=4,dai,ei+k−1=k+3 and dbi,ci+k=k+1, which implies according to Table 4, that the pairs ai,ei−1,ai,ei+k−1 and bi,ci+k satisfy both the conditions in (1) for each 1≤i≤n. Moreover, for each 1≤j≤k, daj,aj+k=k, and so Table 4 concludes that the pair aj,aj+k also satisfies both the conditions in (1).P3:diamTnp=k+3=dai,ei+k−1 for all 1≤i≤n.
Now, without loss of generality, let us takee2,e3,…,en in S, by Proposition 3 and due to P1. Then, from the remaining pairs ak+2,e1 and a2,e1 satisfying P2 and P3, respectively, we must have either ak+2∈S or e1∈S by Proposition 2, and either a2∈S or e1∈S by Proposition 1. If we take e1 in S, then this vertex performs the geodesic identification for both the remaining pairs. Also, Proposition 1 yields that either bi∈S or ci+k∈S for each 1≤i≤n and either aj∈S or aj+k∈S for each 1≤j≤k because of the point P2. Therefore, S≥n−1+1+n+k=5n/2.Table 4
Vertices willing to perform the geodesic identification inTnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bi−1,bidw,ai+k∈k−1,kdw,ei+k−1=k+2dw,ei−1∈3,4ai+kai+k−1,ai+k+1,bi+k−1,bi+kdw,ai∈k−1,kbiai,ai+1,bi−1,bi+1,cidw,ci+k∈k,k+1ci+kbi+k,ci+k−1,ci+k+1,di+k−1,di+kdw,bi∈k,k+1ei−1di−1dw,ai=3ei+k−1di+k−1dw,ai=k+2Lemma 9.
Forn=2k+1 with k≥1, the set S=a1,a2,…,an,e1,e2,…,en⊂VTnp is a strong metric generator for Tnp.Proof.
Note that every pairv,s with s∈S and v∈VTnp−s possesses the geodesic identification by the vertex s. It follows that we should perform the geodesic identification for every pair u,v of distinct vertices by the vertices in S whenever u,v∈VTnp−S. For each 1≤i≤n, except the pairs of vertices,(29)v,bi−k,v,bi+k,v,ci−k,v,ci+k,v,di−k,v,di+k,forv∈bi,ci,di,
All other pairs of vertices possess the geodesic identification by the verticesei+k−1 and ei+k using ai−ei+k−1 geodesics and ai−ei+k geodesics of length k+3, listed from the following equations:(30)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k−1∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(31)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(32)P3i⟶:ai∼bi∼ci∼ci+1∼ci+2∼⋯∼ci+k−1∼di+k−1∼ei+k−1,(33)P4i⟶:ai∼bi∼ci∼di∼di+1∼di+2∼⋯∼di+k−1∼ei+k−1,(34)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k−1∼bi−k∼ci−k=ci+k+1∼di+k∼ei+k,(35)P2i←:ai∼bi−1∼bi−2∼⋯∼bi−k−1∼bi−k∼ci−k=ci+k+1∼di+k∼ei+k,(36)P3i←:ai∼bi−1∼ci−1∼ci−2∼⋯∼ci−k−1∼ci−k=ci+k+1∼di+k∼ei+k,(37)P4i←:ai∼bi−1∼ci−1∼di−2∼di−3∼⋯∼di−k−1∼di−k=di+k+1∼di+k∼ei+k.
Now, for each1≤i≤n, by considering bi−ei+k geodesics, listed from (38) to (43), the vertex ei+k performs the geodesic identification for all the pairs of vertices listed in (29):(38)Q1i⟶:bi∼bi+1∼bi+2∼⋯∼bi+k∼ci+k∼di+k∼ei+k,(39)Q2i⟶:bi∼ci∼ci+1∼ci+2∼⋯∼ci+k∼di+k∼ei+k,(40)Q3i⟶:bi∼ci∼di∼di+1∼di+2∼⋯∼di+k∼ei+k,(41)Q1i←:bi∼bi−1∼bi−2∼⋯∼bi−k∼ci−k=ci+k+1∼di+k∼ei+k,(42)Q2i←:bi∼ci∼ci−1∼ci−2∼⋯∼ci−k=ci+k+1∼di+k∼ei+k,(43)Q3i←:bi∼ci∼di−1∼di−2∼⋯∼di−k=di+k+1∼di+k∼ei+k.
It concludes thatS is a strong metric generator for Tnp.Lemma 10.
Ifn=2k with k≥2, then the set(44)S=a1,a2,…,ak,b1,b2,…,bn,e1,e2,…,en⊂VTnp,is a strong metric generator for Tnp.Proof.
Since the vertexs∈S performs the geodesic identification for every pair of vertices including s, it implies that we have to perform the geodesic identification by the vertices in S for all the pairs of vertices from VTnp−S. For this, consider the following ai−ei+k−1 geodesics of length k+3:(45)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k−1∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(46)P2i⟶:ai∼bi∼ci∼ci+1∼ci+2∼⋯∼ci+k−1∼di+k−1∼ei+k−1,(47)P3i⟶:ai∼bi∼ci∼di∼di+1∼di+2∼⋯∼di+k−1∼ei+k−1,(48)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k−1=ai+k+1∼bi+k∼ci+k∼di+k−1∼ei+k−1,(49)P2i←:ai∼bi−1∼ci−1∼ci−2∼⋯∼ci−k−1=ci+k+1∼ci+k∼di+k−1∼ei+k−1,(50)P3i←:ai∼bi−1∼ci−1∼di−2∼di−3∼⋯∼di−k−1=di+k+1∼di+k∼di+k−1∼ei+k−1.
Due to geodesics, listed from (45) to (50), the vertex ei+k−1 performs the geodesic identification for all the pairs of vertices except the pairs ci,ci+k,di,ci+k,di,di+k for all 1≤i≤n and the pair aj,dj−1 for each k+1≤j≤n. These pairs are identified as follows:(i)
For each1≤i≤n, the vertex bi performs the geodesic identification for the pair ci,ci+k due to the geodesic Qi⟶:bi∼ci∼ci+1∼ci+2∼⋯∼ci+k−1∼ci+k.(ii)
For each1≤i≤n, the vertex bi+k performs the geodesic identification for the pair di,ci+k due to the geodesic Ri⟶:di∼di+1∼di+2∼⋯∼di+k−1∼ci+k∼bi+k.(iii)
For each1≤i≤n, the vertex ei+k performs the geodesic identification for the pair di,di+k due to the geodesic Si⟶:di∼di+1∼di+2∼⋯∼di+k−1∼di+k∼ei+k.(iv)
For eachk+1≤j≤n, the vertex ej−1 performs the geodesic identification for the pair aj,dj−1 due to the geodesic Ti←:aj∼bj−1∼dj−1∼ej−1.
Hence, we conclude thatS is a strong metric generator for Tnp.Proof.
(Theorem2). The lower bound for the strong metric dimension of Tnp is provided by Lemmas 7 and 8, whereas the upper bound is due to Lemmas 9 and 10.


### 4.3. Convex Plane GraphUnp

The graph of a convex polytopeUn is defined in [49] for n≥3. The vertex set of Un is VUn=ai,bi,ci,di,ei;1≤i≤n, and its edge set is(51)EUn=ai∼ai+1,ai∼bi,bi∼bi+1,bi∼ci;1≤i≤n∪ci∼di,ci∼di−1,di∼ei,ei∼ei+1;1≤i≤n.The convex plane graphUnp (p for pendant) is obtained from the graph of a convex polytope Un by attaching one pendant vertex (leaf) fi to the vertex ei of Un for each 1≤i≤n (see Figure 4) [50]. Thus, we have the followings vertex and edge sets for Unp:(52)VUnp=VUn∪fi;1≤i≤n,EUnp=EUn∪ei∼fi;1≤i≤n.Figure 4
The general half view of the convex plane graphUnp.The following main result provides the strong metric dimension ofUnp.Theorem 3.
Forn≥3, let Unp be a convex plane graph. Then,(53)sdimUnp=2n,whennis odd,5n2,whennis even.The proof of Theorem3 will be followed after the next four lemmas.Lemma 11.
For odd values ofn≥3, if S is a strong metric generator for Unp, then S≥2n.Proof.
Letn=2k+1 with k≥1, and consider Table 5 for 1≤i≤n.
Note the following points inUnp:P1:L=fi;1≤i≤n is the set of leaves.P2: for each1≤i≤n, the pairs of vertices ai,fi+k and ci,di+k satisfy both the conditions in (1) because of Table 5 and since dai,fi+k=k+5, dci,di+k=k+3.P3:diamUnp=k+5=dai,fi+k for each 1≤i≤n.
Due to P1 and by Proposition3, we let f2,f3,…,fn∈S without loss of generality. Then, the remaining pair ak+2,f1 satisfies both P2 and P3. So, we must have either ak+2∈S or f1∈S, by Propositions 1 and 2. Furthermore, Proposition 1 yields that, from the pair ci,di+k, either ci∈S or di+k∈S for all 1≤i≤n due to P2. Hence, S≥n−1+1+n=2n.Table 5
Vertices willing to perform the geodesic identification inUnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bidw,fi+k=k+4cibi,di−1,didw,di+k=k+2di+kci+k,ci+k+1,ei+kdw,ci=k+2fi+kei+kdw,ai=k+4Lemma 12.
For even values ofn≥4, if S is a strong metric generator for Unp, then S≥5n/2.Proof.
Letn=2k with k≥2, and consider Table 6 for 1≤i≤n.
The following points hold inUnp:P1:L=fi;1≤i≤n is the set of leaves.P2: for each1≤i≤n, dai,fi+k−1=k+4=dai,fi+k and dai,ci+k=dci,di+k=ddi,fi+k=k+2. It follows, by Table 6, that the pairs of vertices ai,fi+k−1, ai,fi+k, ai,ci+k, ci,di+k, and di,fi+k satisfy both the conditions in (1) for all 1≤i≤n. Moreover, for each 1≤j≤k, dcj,cj+k=k+2=ddj,dj+k. Therefore, Table 6 again yields that the pairs of vertices cj,cj+k and dj,dj+k satisfy both the conditions in (1) for all 1≤j≤k.P3:diamUnp=k+4=dai,fi+k−1=dai,fi+k for all 1≤i≤n.
Without loss of generality, takingf2,f3,…,fn in S, by Proposition 3 and due to P1, we get three pairs of vertices ak+2,f1,ak+1,f1, and dk+1,f1, which are still satisfying P2 and P3. For these pairs, Propositions 1 and 2 allow us to take either ak+2∈S or ak+1∈S or f1∈S. It can be seen that the best suitable choice, to perform the geodesic identification for these three pairs, is to take f1 in S. For otherwise, we will get S≥3n. Furthermore, the point P3 together with Proposition 2 yields that, from the pairs of vertices ai,ci+k and ci,di+k, either ai∈S or ci+k∈S and ci∈S or di+k∈S for all 1≤i≤n. Accordingly, we discuss the following four cases:(i)
Ifai∈S and ci∈S for all 1≤i≤n, then we must have either dj∈S or dj+k∈S for all 1≤j≤k, by the point P2 and Proposition 1. For otherwise, we get the pair of vertices dj,dj+k, for all 1≤j≤k, which is left unidentified by the elements of S, but we have S≥n−1+1+n+n+k=7n/2.(ii)
Ifai∈S and di+k∈S for all 1≤i≤n, then we must have either cj∈S or cj+k∈S for all 1≤j≤k, by the point P2 and Proposition 1. Otherwise, we get the pair of vertices cj,cj+k, for all 1≤j≤k, which is left unidentified by the elements of S, but we have S≥n−1+1+n+n+k=7n/2.(iii)
Ifci+k∈S, then of course ci∈S for all 1≤i≤n. Moreover, we must have either dj∈S or dj+k∈S for all 1≤j≤k, by the point P2 and Proposition 1. For otherwise, we get the pair of vertices dj,dj+k, for all 1≤j≤k, which is left unidentified by the elements of S. Then, we have S≥n−1+1+n+k=5n/2.(iv)
Ifci+k∈S and di+k∈S for all 1≤i≤n, then we have S≥n−1+1+n+n=3n.
It can be concluded from these four cases that the most suitable choice to construct a strong metric generatorS with minimum cardinality is found in the Case 3, which yields that S≥5n/2.Table 6
Vertices willing to perform the geodesic identification inUnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bidw,ci+k=k+1dw,fi+k−1∈k+3,k+4dw,fi+k∈k+3,k+4cibi,di−1,didw,ci+k∈k+1,k+2dw,di+k∈k+1,k+2ci+kbi+k,di+k−1,di+kdw,ai∈k+1,k+2dw,ci∈k+1,k+2dici,ci+1,eidw,di+k∈k+1,k+2dw,fi+k∈k+1,k+2di+kci+k,ci+k+1,ei+kdw,ci∈k+1,k+2dw,di∈k+1,k+2fi+kei+kdw,ai=k+3dw,di=k+1fi+k−1ei+k−1dw,ai=k+3Lemma 13.
Ifn=2k+1 with k≥1, then the set S=c1,c2,…,cn,f1,f2,…,fn⊂VUnp is a strong metric generator for Unp.Proof.
It is enough to perform the geodesic identification for those pairs of vertices ofUnp having no element from the set S because every pair of vertices having one element s from S possesses the geodesic identification by the element s. Let us consider the following ai−fi+k geodesics of length k+5, for each 1≤i≤n:(54)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k∼bi+k∼ci+k∼di+k∼ei+k∼fi+k,(55)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k∼ci+k∼di+k∼ei+k∼fi+k,(56)P3i⟶:ai∼bi∼ci∼di∼ei∼ei+1∼ei+2∼⋯∼ei+k∼fi+k,(57)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k=ai+k+1∼bi+k+1∼ci+k+1∼di+k∼ei+k∼fi+k,(58)P2i←:ai∼bi∼bi−1∼bi−2∼⋯∼bi−k=bi+k+1∼ci+k+1∼di+k∼ei+k∼fi+k,(59)P3i←:ai∼bi∼ci∼di−1∼ei−1∼ei−2∼⋯∼ei−k=ei+k+1∼ei+k∼fi+k.
The vertexfi+k performs the geodesic identification for all the pairs of vertices due to geodesics listed from (54) to (59), except the following pairs of vertices:(60)di,di+1,di,di−1,for1≤i≤n,(61)di,di+j,di,di−j,for1≤i≤n,2≤j≤k.
For1≤i≤n, 2≤j≤k, the following geodesics ensure the geodesic identification of the pairs, given in (60) and (61), by some vertices of S as described in Table 7:(62)Qi⟶:ci∼di∼ci+1∼di+1,(63)Qi←:ci+1∼di∼ci∼di−1,(64)Rji⟶:ci∼di∼ei∼ei+1∼ei+2∼⋯∼ei+j−1∼ei+j∼di+j,(65)Rji←:ci+1∼di∼ei∼ei−1∼ei−2∼⋯∼ei−j−1∼ei−j∼di−j.
Hence, we conclude thatS is a strong metric generator for Unp.Table 7
Geodesic identification for the pairs given in (60) and (61).
PairsVertex performing the geodesic identificationDue to the geodesic indi,di+11≤i≤nci(62)di,di−11≤i≤nci+1(63)2≤j≤kdi,di+j1≤i≤nci(64)2≤j≤kdi,di−j1≤i≤nci+1(65)Lemma 14.
Ifn=2k with k≥2, then the set(66)S=c1,c2,…,cn,d1,d2,…,dk,f1,f2,…,fn⊂VUnpis a strong metric generator for Unp.Proof.
Fors∈S, a pair of vertices v,s with v∈VUnp−s possesses the geodesic identification by the vertex s. Therefore, we should perform the geodesic identification for each pair x,y of vertices of Unp by the vertices in S for both x,y∈S. For each 1≤i≤n, the following ai−fi+k−1 and ai−fi+k geodesics of length k+4 are useful for our purpose:(67)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k−1∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1∼fi+k−1,(68)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1∼fi+k−1,(69)P3i⟶:ai∼bi∼ci∼di∼ei∼ei+1∼ei+2∼⋯∼ei+k−1∼fi+k−1,(70)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k−1∼bi−k−1∼ci−k−1∼di−k=di+k∼ei+k∼fi+k,(71)P2i←:ai∼bi∼bi−1∼bi−2∼⋯∼bi−k−1∼ci−k−1∼di−k=di+k∼ei+k∼fi+k,(72)P3i←:ai∼bi∼ci∼di−1∼ei−1∼ei−2∼⋯∼ei−k−1∼ei−k=ei+k∼fi+k.
It can be seen that, for some pairs of vertices, the vertexfi+k−1 performs the geodesic identification due to geodesics in (67)–(69), and for some pairs of vertices, the vertex fi+k performs the geodesic identification due to geodesics in (70)–(72). The pairs of vertices, which are left unidentified, are as follows:(73)ai,ai+k,ai,bi+k,bi,bi+k,for1≤i≤k,(74)ej,dj+k,ej,ej+k,for1≤j≤k,(75)dr,dr+1,fork+1≤r≤n−1,(76)dl,dl+m,fork+1≤l≤n−2,2≤m≤k−1.
All these pairs of vertices possess the geodesic identification, as described in Table8, with the help of the following geodesics, for 1≤i≤k, 1≤j≤k, k+1≤r≤n−1, k+1≤l≤n−2, and 2≤m≤k−1:(77)Q1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k∼bi+k∼ci+k,(78)Q2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k∼ci+k,(79)Rj⟶:dj∼ej∼ej+1∼ej+2∼⋯∼ej+k−1∼ej+k∼dj+k,(80)Sj⟶:cr∼dr∼cr+1∼dr+1,(81)Tml⟶:cl∼dl∼el∼el+1∼el+2∼⋯∼el+m−1∼el+m∼dl+m.
Thus,S is a strong metric generator for Unp.Table 8
Geodesic identification for the pairs given in (73)–(76).
PairsVertex performing the geodesic identificationDue to the geodesic inai,ai+k,ai,bi+k1≤i≤kci+k(77)bi,bi+k1≤i≤kci+k(78)ej,dj+k,ej,ej+k1≤j≤kdj(79)dr,dr+1k+1≤r≤n−1cr(80)2≤m≤k−1dl,dl+mk+1≤l≤n−2cl(81)Proof.
(Theorem3). The lower bound for the strong metric dimension of Unp is provided by Lemmas 11 and 12, whereas the upper bound is due to Lemmas 13 and 14.


## 4.1. Convex Plane GraphSnp

The graph of a convex polytopeSn is defined in [49] for n≥3. The vertex set of Sn is VSn=ai,bi,ci,di;1≤i≤n, and its edge set is(6)ESn=ai∼ai+1,ai∼bi,bi∼bi+1,bi∼ai+1;1≤i≤n∪bi∼ci,ci∼ci+1,ci∼di,di∼di+1;1≤i≤n.The convex plane graphSnp (p for pendant) can be obtained from the graph of a convex polytope Sn by attaching one pendant vertex (leaf) ei to the vertex di of Sn for each 1≤i≤n (see Figure 2) [50]. Thus, the vertex and edge sets of Snp are(7)VSnp=VSn∪ei;1≤i≤n,ESnp=ESn∪di∼ei;1≤i≤n.Figure 2
The general half view of the convex plane graphSnp.We investigate the strong matrix dimension ofSnp by supplying the following main result.Theorem 1.
Forn≥3, let Snp be a convex plane graph. Then,(8)sdimSnp=n,whennis odd,3n2,whennis even.The next four lemmas will lead the proof of Theorem1.Lemma 3.
For odd values ofn≥3, if S is a strong metric generator for Snp, then S≥n.Proof.
Letn=2k+1 with k≥1, and consider Table 1 for 1≤i≤n.
InSnp, note the following points:P1:L=ei;1≤i≤n is the set of leaves.P2: for each1≤i≤n, dai,ei+k=k+4. It follows, according to Table 1, that the pair ai,ei+k satisfies both the conditions in (1).P3:diamSnp=k+4=dai,ei+k for each 1≤i≤n.
From P1, without loss of generality, we suppose thate2,e3,…,en∈S by Proposition 3. Then, since the pair ak+1,e1 satisfies P2 and P3, we have either ak+1∈S or e1∈S, by Propositions 1 and 2. Hence, S≥n−1+1=n.Table 1
Vertices willing to perform the geodesic identification inSnp.
VertexvNvdw,⋅ for all w∈Nvaiai+1,ai−1,bi−1,bidw,ei+k=k+3ei+kdi+kdw,ai=k+3Lemma 4.
For even values ofn≥4, if S is a strong metric generator for Snp, then S≥3n/2.Proof.
Letn=2k with k≥2, and consider Table 2 for 1≤i≤n.
InSnp, the following points hold:P1:L=ei;1≤i≤n is the set of leaves.P2: for each1≤i≤n, dai,ei+k−1=dai,ei+k=dbi,ei+k=k+3. Therefore, Table 2 yields that the pairs ai,ei+k−1,ai,ei+k and bi,ei+k satisfy both the conditions in (1) for each 1≤i≤n. Table 2 further implies that the pair aj,aj+k satisfies both the conditions in (1) because daj,aj+k=k for each 1≤j≤k.P3:diamSnp=k+3=dai,ei+k−1=dai,ei+k=dbi,ei+k for each 1≤i≤n.
Due to P1, without loss of generality, we lete2,e3,…,en∈S, by Proposition 3. Then, as the pairs ak+2,e1,ak+1,e1 and bk+1,e1 satisfy P2 and P3, we must have either ak+2∈S or ak+1∈S or bk+1∈S or e1∈S, by Propositions 1 and 2. For the geodesic identification of these three pairs, it is enough to consider e1 in S. Furthermore, for each 1≤j≤k, either aj∈S or aj+k∈S, due to P2 and Proposition 1. Hence, S≥n−1+1+k=3n/2.Table 2
Vertices willing to perform the geodesic identification inSnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bi−1,bidw,ai+k∈k−1,kdw,ei+k−1∈k+2,k+3dw,ei+k∈k+2,k+3ai+kai+k−1,ai+k+1,bi+k−1,bi+kdw,ai∈k−1,kbiai,ai+1,bi−1,bi+1,cidw,ei+k∈k+2,k+3ei+k−1di+k−1dw,ai=k+2ei+kdi+kdw,ai=k+2dw,bi=k+2Lemma 5.
Ifn=2k+1 with k≥1, then the set S=e1,e2,…,en⊂VSnp is a strong metric generator for Snp.Proof.
For anys∈S and any u∈VSnp−s, since the vertex s performs the geodesic identification for the pair s,u, we have to perform the geodesic identification for every pair x,y of distinct vertices with x,y∈VSnp−S. For each 1≤i≤n, consider the following ai−ei+k geodesics of length k+4:(9)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k∼bi+k∼ci+k∼di+k∼ei+k,(10)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k∼ci+k∼di+k∼ei+k,(11)P3i⟶:ai∼bi∼ci∼ci+1∼ci+2∼⋯∼ci+k∼di+k∼ei+k,(12)P4i⟶:ai∼bi∼ci∼di∼di+1∼di+2∼⋯∼di+k∼ei+k,(13)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k=ai+k+1∼bi+k∼ci+k∼di+k∼ei+k,(14)P2i←:ai∼bi−1∼bi−2∼⋯∼bi−k=bi+k+1∼bi+k∼ci+k∼di+k∼ei+k,(15)P3i←:ai∼bi−1∼ci−1∼ci−2∼⋯∼ci−k=ci+k+1∼ci+k∼di+k∼ei+k,(16)P4i←:ai∼bi−1∼ci−1∼di−1∼di−2∼⋯∼di−k=di+k+1∼di+k∼ei+k.
Each geodesic, listed from (9) to (16), provides that the vertex ei+k∈S performs the geodesic identification for every pair x,y with x,y∈VSnp−S. It follows that S is a strong metric generator for Snp.Lemma 6.
Ifn=2k with k≥2, then the set S=a1,a2,…,ak,e1,e2,…,en⊂VSnp is a strong metric generator for Snp.Proof.
We have to perform the geodesic identification each pairu,v of distinct vertices for u,v∈VSnp−S because for any s∈S and any v∈VSnp−s, the pair s,v possesses the geodesic identification by the vertex s. For each 1≤i≤n, consider the following ai−ei+k−1 geodesics and ai−ei+k geodesics of length k+3:(17)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k−1∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(18)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(19)P3i⟶:ai∼bi∼ci∼ci+1∼ci+2∼⋯∼ci+k−1∼di+k−1∼ei+k−1,(20)P4i⟶:ai∼bi∼ci∼di∼di+1∼di+2∼⋯∼di+k−1∼ei+k−1,(21)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k−1=ai+k+1∼bi+k∼ci+k∼di+k∼ei+k,(22)P2i←:ai∼bi−1∼bi−2∼⋯∼bi−k−1=bi+k+1∼bi+k∼ci+k∼di+k∼ei+k,(23)P3i←:ai∼bi−1∼ci−1∼ci−2∼⋯∼ci−k−1=ci+k+1∼ci+k∼di+k∼ei+k,(24)P4i←:ai∼bi−1∼ci−1∼di−1∼di−2∼⋯∼di−k−1=di+k+1∼di+k∼ei+k.
Except the pairsai,aj for k≤i≤n−1 and i+1≤j≤n, all the pairs of vertices owned the geodesic identification by the vertices ei+k and ei+k−1 due to the geodesics listed from (17) to (24). By considering the following ak−an geodesic(25)P⟶:ak∼ak+1∼ak+2∼⋯∼an−1∼an,we get that the vertex ak performs the geodesic identification for all the remaining pairs ai,aj. Hence, S is a strong metric generator for Snp.Proof.
(Theorem1). The lower bound for the strong metric dimension of Snp is provided by Lemmas 3 and 4, whereas the upper bound is due to Lemmas 5 and 6.


## 4.2. Convex Plane GraphTnp

The graph of a convex polytopeTn is defined in [49] for n≥3. The vertex set of Tn is VTn=ai,bi,ci,di;1≤i≤n, and its edge set is(26)ETn=ai∼ai+1,ai∼bi,bi∼bi+1,bi∼ai+1,bi∼ci;1≤i≤n∪ci∼ci+1,ci∼di,ci∼di−1,di∼di+1;1≤i≤n.The convex plane graphTnp (p for pendant) can be obtained from the graph of a convex polytope Tn by attaching one pendant vertex (leaf) ei to the vertex di of Tn for each 1≤i≤n (see Figure 3) [50]. Accordingly, the vertex and edge sets of Tnp are(27)VTnp=VTn∪ei;1≤i≤n,ETnp=ETn∪di∼ei;1≤i≤n.Figure 3
The general half view of the convex plane graphTnp.Mainly, we have the following result for the strong metric dimension ofTnp.Theorem 2.
Forn≥3, let Tnp be a convex plane graph. Then,(28)sdimTnp=2n,whennis odd,5n2,whennis even.The proof of Theorem2 will be followed after the next four lemmas.Lemma 7.
For odd values ofn≥3, if S is a strong metric generator for Tnp, then S≥2n.Proof.
Letn=2k+1 with k≥1, and consider Table 3 for 1≤i≤n.
Note the following three points inTnp:P1:L=ei;1≤i≤n is the set of leaves.P2:dai,ei+k−1=dai,ei+k=dbi,ei+k=k+3 and dai,ci+k=k+2 for each 1≤i≤n. Hence, Table 3 ensures that pairs of vertices in Tnp satisfying both the conditions in (1) are ai,ei+k−1,ai,ei+k,bi,ei+k, and ai,ci+k for each 1≤i≤n.P3:diamTnp=k+3=dai,ei+k−1=dai,ei+k=dbi,ei+k for each 1≤i≤n.
By Proposition3, let us take e2,e3,…,en∈S without loss of generality due to P1. Then, from the remaining pairs ak+3,e1,ak+2,e1, and bk+2,e1, we must have either ak+3∈S or ak+2∈S or bk+2∈S or e1∈S, by Propositions 1 and 2, because these pairs are satisfying P2 and P3. Here, it can be seen, by letting e1∈S only, that all these pairs possess the geodesic identification by the vertex e1. Furthermore, for each 1≤i≤n, from the pair ai,ci+k satisfying P2, either ai∈S or ci+k∈S, by Proposition 1. Hence, S≥n−1+1+n=2n.Table 3
Vertices willing to perform the geodesic identification inTnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bi−1,bidw,ci+k=k+1dw,ei+k−1∈k+2,k+3dw,ei+k∈k+2,k+3biai,ai+1,bi−1,bi+1,cidw,ei+k∈k+2,k+3ci+kbi+k,ci+k−1,ci+k+1,di+k−1,di+kdw,ai∈k+1,k+2ei+k−1di+k−1dw,ai=k+2ei+kdi+kdw,ai=k+2dw,bi=k+2Lemma 8.
For even values ofn≥4, if S is a strong metric generator for Tnp, then S≥5n/2.Proof.
Letn=2k with k≥2, and consider Table 4 for 1≤i≤n.
The following points are considerable inTnp:P1:L=ei;1≤i≤n is the set of leaves.P2:dai,ei−1=4,dai,ei+k−1=k+3 and dbi,ci+k=k+1, which implies according to Table 4, that the pairs ai,ei−1,ai,ei+k−1 and bi,ci+k satisfy both the conditions in (1) for each 1≤i≤n. Moreover, for each 1≤j≤k, daj,aj+k=k, and so Table 4 concludes that the pair aj,aj+k also satisfies both the conditions in (1).P3:diamTnp=k+3=dai,ei+k−1 for all 1≤i≤n.
Now, without loss of generality, let us takee2,e3,…,en in S, by Proposition 3 and due to P1. Then, from the remaining pairs ak+2,e1 and a2,e1 satisfying P2 and P3, respectively, we must have either ak+2∈S or e1∈S by Proposition 2, and either a2∈S or e1∈S by Proposition 1. If we take e1 in S, then this vertex performs the geodesic identification for both the remaining pairs. Also, Proposition 1 yields that either bi∈S or ci+k∈S for each 1≤i≤n and either aj∈S or aj+k∈S for each 1≤j≤k because of the point P2. Therefore, S≥n−1+1+n+k=5n/2.Table 4
Vertices willing to perform the geodesic identification inTnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bi−1,bidw,ai+k∈k−1,kdw,ei+k−1=k+2dw,ei−1∈3,4ai+kai+k−1,ai+k+1,bi+k−1,bi+kdw,ai∈k−1,kbiai,ai+1,bi−1,bi+1,cidw,ci+k∈k,k+1ci+kbi+k,ci+k−1,ci+k+1,di+k−1,di+kdw,bi∈k,k+1ei−1di−1dw,ai=3ei+k−1di+k−1dw,ai=k+2Lemma 9.
Forn=2k+1 with k≥1, the set S=a1,a2,…,an,e1,e2,…,en⊂VTnp is a strong metric generator for Tnp.Proof.
Note that every pairv,s with s∈S and v∈VTnp−s possesses the geodesic identification by the vertex s. It follows that we should perform the geodesic identification for every pair u,v of distinct vertices by the vertices in S whenever u,v∈VTnp−S. For each 1≤i≤n, except the pairs of vertices,(29)v,bi−k,v,bi+k,v,ci−k,v,ci+k,v,di−k,v,di+k,forv∈bi,ci,di,
All other pairs of vertices possess the geodesic identification by the verticesei+k−1 and ei+k using ai−ei+k−1 geodesics and ai−ei+k geodesics of length k+3, listed from the following equations:(30)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k−1∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(31)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(32)P3i⟶:ai∼bi∼ci∼ci+1∼ci+2∼⋯∼ci+k−1∼di+k−1∼ei+k−1,(33)P4i⟶:ai∼bi∼ci∼di∼di+1∼di+2∼⋯∼di+k−1∼ei+k−1,(34)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k−1∼bi−k∼ci−k=ci+k+1∼di+k∼ei+k,(35)P2i←:ai∼bi−1∼bi−2∼⋯∼bi−k−1∼bi−k∼ci−k=ci+k+1∼di+k∼ei+k,(36)P3i←:ai∼bi−1∼ci−1∼ci−2∼⋯∼ci−k−1∼ci−k=ci+k+1∼di+k∼ei+k,(37)P4i←:ai∼bi−1∼ci−1∼di−2∼di−3∼⋯∼di−k−1∼di−k=di+k+1∼di+k∼ei+k.
Now, for each1≤i≤n, by considering bi−ei+k geodesics, listed from (38) to (43), the vertex ei+k performs the geodesic identification for all the pairs of vertices listed in (29):(38)Q1i⟶:bi∼bi+1∼bi+2∼⋯∼bi+k∼ci+k∼di+k∼ei+k,(39)Q2i⟶:bi∼ci∼ci+1∼ci+2∼⋯∼ci+k∼di+k∼ei+k,(40)Q3i⟶:bi∼ci∼di∼di+1∼di+2∼⋯∼di+k∼ei+k,(41)Q1i←:bi∼bi−1∼bi−2∼⋯∼bi−k∼ci−k=ci+k+1∼di+k∼ei+k,(42)Q2i←:bi∼ci∼ci−1∼ci−2∼⋯∼ci−k=ci+k+1∼di+k∼ei+k,(43)Q3i←:bi∼ci∼di−1∼di−2∼⋯∼di−k=di+k+1∼di+k∼ei+k.
It concludes thatS is a strong metric generator for Tnp.Lemma 10.
Ifn=2k with k≥2, then the set(44)S=a1,a2,…,ak,b1,b2,…,bn,e1,e2,…,en⊂VTnp,is a strong metric generator for Tnp.Proof.
Since the vertexs∈S performs the geodesic identification for every pair of vertices including s, it implies that we have to perform the geodesic identification by the vertices in S for all the pairs of vertices from VTnp−S. For this, consider the following ai−ei+k−1 geodesics of length k+3:(45)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k−1∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1,(46)P2i⟶:ai∼bi∼ci∼ci+1∼ci+2∼⋯∼ci+k−1∼di+k−1∼ei+k−1,(47)P3i⟶:ai∼bi∼ci∼di∼di+1∼di+2∼⋯∼di+k−1∼ei+k−1,(48)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k−1=ai+k+1∼bi+k∼ci+k∼di+k−1∼ei+k−1,(49)P2i←:ai∼bi−1∼ci−1∼ci−2∼⋯∼ci−k−1=ci+k+1∼ci+k∼di+k−1∼ei+k−1,(50)P3i←:ai∼bi−1∼ci−1∼di−2∼di−3∼⋯∼di−k−1=di+k+1∼di+k∼di+k−1∼ei+k−1.
Due to geodesics, listed from (45) to (50), the vertex ei+k−1 performs the geodesic identification for all the pairs of vertices except the pairs ci,ci+k,di,ci+k,di,di+k for all 1≤i≤n and the pair aj,dj−1 for each k+1≤j≤n. These pairs are identified as follows:(i)
For each1≤i≤n, the vertex bi performs the geodesic identification for the pair ci,ci+k due to the geodesic Qi⟶:bi∼ci∼ci+1∼ci+2∼⋯∼ci+k−1∼ci+k.(ii)
For each1≤i≤n, the vertex bi+k performs the geodesic identification for the pair di,ci+k due to the geodesic Ri⟶:di∼di+1∼di+2∼⋯∼di+k−1∼ci+k∼bi+k.(iii)
For each1≤i≤n, the vertex ei+k performs the geodesic identification for the pair di,di+k due to the geodesic Si⟶:di∼di+1∼di+2∼⋯∼di+k−1∼di+k∼ei+k.(iv)
For eachk+1≤j≤n, the vertex ej−1 performs the geodesic identification for the pair aj,dj−1 due to the geodesic Ti←:aj∼bj−1∼dj−1∼ej−1.
Hence, we conclude thatS is a strong metric generator for Tnp.Proof.
(Theorem2). The lower bound for the strong metric dimension of Tnp is provided by Lemmas 7 and 8, whereas the upper bound is due to Lemmas 9 and 10.


## 4.3. Convex Plane GraphUnp

The graph of a convex polytopeUn is defined in [49] for n≥3. The vertex set of Un is VUn=ai,bi,ci,di,ei;1≤i≤n, and its edge set is(51)EUn=ai∼ai+1,ai∼bi,bi∼bi+1,bi∼ci;1≤i≤n∪ci∼di,ci∼di−1,di∼ei,ei∼ei+1;1≤i≤n.The convex plane graphUnp (p for pendant) is obtained from the graph of a convex polytope Un by attaching one pendant vertex (leaf) fi to the vertex ei of Un for each 1≤i≤n (see Figure 4) [50]. Thus, we have the followings vertex and edge sets for Unp:(52)VUnp=VUn∪fi;1≤i≤n,EUnp=EUn∪ei∼fi;1≤i≤n.Figure 4
The general half view of the convex plane graphUnp.The following main result provides the strong metric dimension ofUnp.Theorem 3.
Forn≥3, let Unp be a convex plane graph. Then,(53)sdimUnp=2n,whennis odd,5n2,whennis even.The proof of Theorem3 will be followed after the next four lemmas.Lemma 11.
For odd values ofn≥3, if S is a strong metric generator for Unp, then S≥2n.Proof.
Letn=2k+1 with k≥1, and consider Table 5 for 1≤i≤n.
Note the following points inUnp:P1:L=fi;1≤i≤n is the set of leaves.P2: for each1≤i≤n, the pairs of vertices ai,fi+k and ci,di+k satisfy both the conditions in (1) because of Table 5 and since dai,fi+k=k+5, dci,di+k=k+3.P3:diamUnp=k+5=dai,fi+k for each 1≤i≤n.
Due to P1 and by Proposition3, we let f2,f3,…,fn∈S without loss of generality. Then, the remaining pair ak+2,f1 satisfies both P2 and P3. So, we must have either ak+2∈S or f1∈S, by Propositions 1 and 2. Furthermore, Proposition 1 yields that, from the pair ci,di+k, either ci∈S or di+k∈S for all 1≤i≤n due to P2. Hence, S≥n−1+1+n=2n.Table 5
Vertices willing to perform the geodesic identification inUnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bidw,fi+k=k+4cibi,di−1,didw,di+k=k+2di+kci+k,ci+k+1,ei+kdw,ci=k+2fi+kei+kdw,ai=k+4Lemma 12.
For even values ofn≥4, if S is a strong metric generator for Unp, then S≥5n/2.Proof.
Letn=2k with k≥2, and consider Table 6 for 1≤i≤n.
The following points hold inUnp:P1:L=fi;1≤i≤n is the set of leaves.P2: for each1≤i≤n, dai,fi+k−1=k+4=dai,fi+k and dai,ci+k=dci,di+k=ddi,fi+k=k+2. It follows, by Table 6, that the pairs of vertices ai,fi+k−1, ai,fi+k, ai,ci+k, ci,di+k, and di,fi+k satisfy both the conditions in (1) for all 1≤i≤n. Moreover, for each 1≤j≤k, dcj,cj+k=k+2=ddj,dj+k. Therefore, Table 6 again yields that the pairs of vertices cj,cj+k and dj,dj+k satisfy both the conditions in (1) for all 1≤j≤k.P3:diamUnp=k+4=dai,fi+k−1=dai,fi+k for all 1≤i≤n.
Without loss of generality, takingf2,f3,…,fn in S, by Proposition 3 and due to P1, we get three pairs of vertices ak+2,f1,ak+1,f1, and dk+1,f1, which are still satisfying P2 and P3. For these pairs, Propositions 1 and 2 allow us to take either ak+2∈S or ak+1∈S or f1∈S. It can be seen that the best suitable choice, to perform the geodesic identification for these three pairs, is to take f1 in S. For otherwise, we will get S≥3n. Furthermore, the point P3 together with Proposition 2 yields that, from the pairs of vertices ai,ci+k and ci,di+k, either ai∈S or ci+k∈S and ci∈S or di+k∈S for all 1≤i≤n. Accordingly, we discuss the following four cases:(i)
Ifai∈S and ci∈S for all 1≤i≤n, then we must have either dj∈S or dj+k∈S for all 1≤j≤k, by the point P2 and Proposition 1. For otherwise, we get the pair of vertices dj,dj+k, for all 1≤j≤k, which is left unidentified by the elements of S, but we have S≥n−1+1+n+n+k=7n/2.(ii)
Ifai∈S and di+k∈S for all 1≤i≤n, then we must have either cj∈S or cj+k∈S for all 1≤j≤k, by the point P2 and Proposition 1. Otherwise, we get the pair of vertices cj,cj+k, for all 1≤j≤k, which is left unidentified by the elements of S, but we have S≥n−1+1+n+n+k=7n/2.(iii)
Ifci+k∈S, then of course ci∈S for all 1≤i≤n. Moreover, we must have either dj∈S or dj+k∈S for all 1≤j≤k, by the point P2 and Proposition 1. For otherwise, we get the pair of vertices dj,dj+k, for all 1≤j≤k, which is left unidentified by the elements of S. Then, we have S≥n−1+1+n+k=5n/2.(iv)
Ifci+k∈S and di+k∈S for all 1≤i≤n, then we have S≥n−1+1+n+n=3n.
It can be concluded from these four cases that the most suitable choice to construct a strong metric generatorS with minimum cardinality is found in the Case 3, which yields that S≥5n/2.Table 6
Vertices willing to perform the geodesic identification inUnp.
VertexvNvdw,⋅ for all w∈Nvaiai−1,ai+1,bidw,ci+k=k+1dw,fi+k−1∈k+3,k+4dw,fi+k∈k+3,k+4cibi,di−1,didw,ci+k∈k+1,k+2dw,di+k∈k+1,k+2ci+kbi+k,di+k−1,di+kdw,ai∈k+1,k+2dw,ci∈k+1,k+2dici,ci+1,eidw,di+k∈k+1,k+2dw,fi+k∈k+1,k+2di+kci+k,ci+k+1,ei+kdw,ci∈k+1,k+2dw,di∈k+1,k+2fi+kei+kdw,ai=k+3dw,di=k+1fi+k−1ei+k−1dw,ai=k+3Lemma 13.
Ifn=2k+1 with k≥1, then the set S=c1,c2,…,cn,f1,f2,…,fn⊂VUnp is a strong metric generator for Unp.Proof.
It is enough to perform the geodesic identification for those pairs of vertices ofUnp having no element from the set S because every pair of vertices having one element s from S possesses the geodesic identification by the element s. Let us consider the following ai−fi+k geodesics of length k+5, for each 1≤i≤n:(54)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k∼bi+k∼ci+k∼di+k∼ei+k∼fi+k,(55)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k∼ci+k∼di+k∼ei+k∼fi+k,(56)P3i⟶:ai∼bi∼ci∼di∼ei∼ei+1∼ei+2∼⋯∼ei+k∼fi+k,(57)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k=ai+k+1∼bi+k+1∼ci+k+1∼di+k∼ei+k∼fi+k,(58)P2i←:ai∼bi∼bi−1∼bi−2∼⋯∼bi−k=bi+k+1∼ci+k+1∼di+k∼ei+k∼fi+k,(59)P3i←:ai∼bi∼ci∼di−1∼ei−1∼ei−2∼⋯∼ei−k=ei+k+1∼ei+k∼fi+k.
The vertexfi+k performs the geodesic identification for all the pairs of vertices due to geodesics listed from (54) to (59), except the following pairs of vertices:(60)di,di+1,di,di−1,for1≤i≤n,(61)di,di+j,di,di−j,for1≤i≤n,2≤j≤k.
For1≤i≤n, 2≤j≤k, the following geodesics ensure the geodesic identification of the pairs, given in (60) and (61), by some vertices of S as described in Table 7:(62)Qi⟶:ci∼di∼ci+1∼di+1,(63)Qi←:ci+1∼di∼ci∼di−1,(64)Rji⟶:ci∼di∼ei∼ei+1∼ei+2∼⋯∼ei+j−1∼ei+j∼di+j,(65)Rji←:ci+1∼di∼ei∼ei−1∼ei−2∼⋯∼ei−j−1∼ei−j∼di−j.
Hence, we conclude thatS is a strong metric generator for Unp.Table 7
Geodesic identification for the pairs given in (60) and (61).
PairsVertex performing the geodesic identificationDue to the geodesic indi,di+11≤i≤nci(62)di,di−11≤i≤nci+1(63)2≤j≤kdi,di+j1≤i≤nci(64)2≤j≤kdi,di−j1≤i≤nci+1(65)Lemma 14.
Ifn=2k with k≥2, then the set(66)S=c1,c2,…,cn,d1,d2,…,dk,f1,f2,…,fn⊂VUnpis a strong metric generator for Unp.Proof.
Fors∈S, a pair of vertices v,s with v∈VUnp−s possesses the geodesic identification by the vertex s. Therefore, we should perform the geodesic identification for each pair x,y of vertices of Unp by the vertices in S for both x,y∈S. For each 1≤i≤n, the following ai−fi+k−1 and ai−fi+k geodesics of length k+4 are useful for our purpose:(67)P1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k−1∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1∼fi+k−1,(68)P2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k−1∼ci+k−1∼di+k−1∼ei+k−1∼fi+k−1,(69)P3i⟶:ai∼bi∼ci∼di∼ei∼ei+1∼ei+2∼⋯∼ei+k−1∼fi+k−1,(70)P1i←:ai∼ai−1∼ai−2∼⋯∼ai−k−1∼bi−k−1∼ci−k−1∼di−k=di+k∼ei+k∼fi+k,(71)P2i←:ai∼bi∼bi−1∼bi−2∼⋯∼bi−k−1∼ci−k−1∼di−k=di+k∼ei+k∼fi+k,(72)P3i←:ai∼bi∼ci∼di−1∼ei−1∼ei−2∼⋯∼ei−k−1∼ei−k=ei+k∼fi+k.
It can be seen that, for some pairs of vertices, the vertexfi+k−1 performs the geodesic identification due to geodesics in (67)–(69), and for some pairs of vertices, the vertex fi+k performs the geodesic identification due to geodesics in (70)–(72). The pairs of vertices, which are left unidentified, are as follows:(73)ai,ai+k,ai,bi+k,bi,bi+k,for1≤i≤k,(74)ej,dj+k,ej,ej+k,for1≤j≤k,(75)dr,dr+1,fork+1≤r≤n−1,(76)dl,dl+m,fork+1≤l≤n−2,2≤m≤k−1.
All these pairs of vertices possess the geodesic identification, as described in Table8, with the help of the following geodesics, for 1≤i≤k, 1≤j≤k, k+1≤r≤n−1, k+1≤l≤n−2, and 2≤m≤k−1:(77)Q1i⟶:ai∼ai+1∼ai+2∼⋯∼ai+k∼bi+k∼ci+k,(78)Q2i⟶:ai∼bi∼bi+1∼bi+2∼⋯∼bi+k∼ci+k,(79)Rj⟶:dj∼ej∼ej+1∼ej+2∼⋯∼ej+k−1∼ej+k∼dj+k,(80)Sj⟶:cr∼dr∼cr+1∼dr+1,(81)Tml⟶:cl∼dl∼el∼el+1∼el+2∼⋯∼el+m−1∼el+m∼dl+m.
Thus,S is a strong metric generator for Unp.Table 8
Geodesic identification for the pairs given in (73)–(76).
PairsVertex performing the geodesic identificationDue to the geodesic inai,ai+k,ai,bi+k1≤i≤kci+k(77)bi,bi+k1≤i≤kci+k(78)ej,dj+k,ej,ej+k1≤j≤kdj(79)dr,dr+1k+1≤r≤n−1cr(80)2≤m≤k−1dl,dl+mk+1≤l≤n−2cl(81)Proof.
(Theorem3). The lower bound for the strong metric dimension of Unp is provided by Lemmas 11 and 12, whereas the upper bound is due to Lemmas 13 and 14.


## 5. Concluding Remarks

The geodesic identification (strong resolvability) for each pair of vertices has been performed in three familiesSnp, Tnp, and Unp of convex plane graphs for all n≥3. In fact, we extended the study of the identification of vertices by solving the strong metric dimension problem for three more families of graphs. The problem is solved with the following investigations:(i)
InSnp,total 5n2 pairs of vertices are identified with n vertices by using 8n geodesics when n is odd and with 3n/2 vertices by using 8n+1 geodesics when n is even.(ii)
InTnp, total 5n2 pairs of vertices are identified with 2n vertices by using 14n geodesics when n is odd and with 5n/2 vertices by using 19n/2 geodesics when n is even.(iii)
InUnp, total 6n2 pairs of vertices are identified with 2n vertices by using nn+3 geodesics when n is odd and with 5n/2 vertices by using n2/4+6n+3 geodesics when n is even.



---

*Source: 7483291-2020-12-28.xml*