# Double Metric Resolvability in Convex Polytopes

Authors: Muhammad Ahmad; Dalal Alrowaili; Rifaqat Ali; Zohaib Zahid; Imran Siddique
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Nowadays, the study of source localization in complex networks is a critical issue. Localization of the source has been investigated using a variety of feasible models. To identify the source of a network’s diffusion, it is necessary to find a vertex from which the observed diffusion spreads. Detecting the source of a virus in a network is equivalent to finding the minimal doubly resolving set (MDRS) in a network. This paper calculates the doubly resolving sets (DRSs) for certain convex polytope structures to calculate their double metric dimension (DMD). It is concluded that the cardinality of MDRSs for these convex polytopes is finite and constant.


---

## Body

## 1. Introduction and Preliminaries

Consider a connected and undirected graphΓ=VΓ,EΓ, where VΓ denotes the set of vertices, while EΓ represents the collection of edges. The distance db,c between two vertices b,c∈VΓ is calculated by counting the length of the shortest path between the two vertices. dc,f1≠dc,f2≠⋯≠dc,fn implies that the vertex set f1,f2,…,fn is resolved by the vertex c∈VΓ. Let MΓ⊆VΓ be a set of order l. The vector of metric coordinates of a vertex u with respect to MΓ, represented by ru|MΓ, is the l-vector ru|MΓ=du,m:m∈MΓ. If distinct vertices of Γ have unique metric coordinate vectors with respect to MΓ, the set MΓ is said to be resolving. A minimum-order resolving set is referred to as the basis of graph Γ and its order is called the metric dimension (MD) of Γ, denoted as dimΓ.Blumenthal [1] first proposed the notion of the MD of general metric space in 1953. Slater [2] introduced MD in 1975, and Harary and Melter [3] developed it as a resolving set of graphs in 1976. It was originally intended that the resolving sets have been used to locate an intruder in a network, but Chartrand and Zang [4] have since presented numerous uses of resolving sets in robotics, chemistry, and biology. The concept of trilateration can be generalized from a two-dimensional real plane in terms of the MD of graphs. The Global Positioning System (GPS) uses distance measurements to detect the exact location of various objects on our planet. For studying the MD theoretically, there are several applications in navigation of robots [5] and molecular chemistry [6]. The MD of Hamming graphs has been investigated in a variety of applications, ranging from coin-weighing difficulties [7, 8] to efficient Mastermind game strategies [9]. Studies on combinatorial optimization [10] and the difficulty of locating facilities, as well as the Coast Guard’s loran and sonar systems [2], have all made use of the MD approach. Moreover, different fields including robotics [5], discovery and verification in networks [11], and routing protocols geographically [12] have examined this notion extensively.Determining the exact MD value of any given graph is a computationally challenging task [5, 13]. Several helpful bounds for different types of graphs were investigated; for instance, see [14]. Both Buczkowski et al. [15] and Ali et al. [16] explored the minimal order resolving sets of wheel graphs and Mobius ladders, respectively. Chartrand and others performed a classification of all graphs using MD 1, n−2, and n−1 (see [6]). In [17, 18], Imran et al. find the MD for different convex polytope structures. Tomescu et al. in [19] and Ahmad et al. [20] calculated the MD for Jahangir graphs, chorded cycles and kayak paddle graphs, respectively. Baca et al. provides the results for the MD of regular bipartite graphs [21]. The MD of necklace graphs was studied in [22], and certain plane graphs for MD were considered in [23].As a research tool for studying minimal resolving sets of cartesian product graphs, Caceres et al. [24] established the concept of DRSs. Consider a graph Γ, where Γ≥2. Two vertices h′ and k′∈VΓ doubly resolve a pair of vertices h,k of Γ if dh,h′−dh,k′≠dk,h′−dk,k′. A subset DΓ is a DRS of Γ if some two vertices of DΓ doubly resolve any pair of vertices in Γ. The MDRS is a DRS that is the smallest possible. The DMD of Γ is the cardinality of an MDRS and is represented by ψΓ. For all graphs Γ, any DRS is obviously a resolving set, with dimΓ≤ψΓ.Kratica et al. [25] studied the computational complexity of the DRSs of a graph Γ. An investigation of the Harary graph family (resp. circulant graph family) for MD and MDRSs was conducted by Ahmad et al. [26, 27]. Chen et al. [28] provided the first explicitly approximated lower and upper limits for the MDRSs problem. Ahmad et al. studied the line graphs of n-Sunlet, prism [29], and kayak paddle graphs [30] for the MD and MDRSs, respectively. To find the smallest possible DRS, a variety of graph families have been examined, such as those involving prisms [31], convex polytopes [32], and Hamming graphs [33]. The MDRSs of different convex polytope structures were examined by Pan et al. [34] and Ahmad et al. [35]. Minimal order resolving sets and MDRSs of cocktail and jellyfish graphs were calculated by Liu and others [36]. For the layer-sun graphs and their related line graphs, the MDRS problem was also studied in [37]. In [38], the minimal resolving sets and DMD of the line graph of chorded cycles were examined. Authors demonstrated that the DMD of LCnt is exactly one greater than its MD.Thus, DRSs are essential for examining the MD of cartesian products. We were inspired by the idea of achieving upper bounds in the cartesian product of graphs to examine the DRSs of other graph classes. In addition, this parameter can be helpful in a wide range of domains, including rumor spreading on online social networks and the origin of a disease outbreak.It is feasible to determine the diffusion source in complex networks using MDRSs. Finding the source of wide-area network propagation might be challenging. As an example, in the case of an unknown virus source, all that is required to locate it is the contamination time of a subset of the sensor nodes. These sensor nodes may record their infection time. How many sensors are required to locate the viral source? A property called DMD provides the answer to this problem (for details see [39, 40]). It would be simple to determine the origins of the pandemic if we were able to see it from beginning to end. Data for source localization is sometimes scarce due to the cost and complexity of collecting and storing information. Even if the initial virus propagation period is unknown, a doubly resolving sensor set may detect infection sources reliably.In a star-like network, identifying the viral origin is much more complicated than in a path-like network. The DMD isn−1 for a star network of n nodes, but the DMD is 2 for a path network. As a result, this demonstrates that the DMD is always dependent on the network’s topology [39].It has been challenging to solve convex polytopes for the DMD in the previous few years. Here, Imran et al. [18, 41] calculate DMD for Tn and Sn convex polytopes. In the following theorems, the MD of the convex polytopes Tn and Sn is shown.Theorem 1.
IfTn is the graph of convex polytope, dimTn is 3, and ∀n≥6.Theorem 2.
IfSn is the graph of convex polytope, dimSn is 3, and ∀n≥6.The following sections elaborate on the rest of the article:(i)
In Section2, we define the graph of Tn and computed the MDRSs of the convex polytope Tn for n≥6.(ii)
In Section3, we define the graph of Sn and calculated the DMD for the convex polytope structure Sn, for n≥6.(iii)
Section4 concludes that the DMD for the convex polytopes Tn and Sn is finite and constant.


## 2. Double Metric Dimension for the Convex PolytopeTn

The results of the DMD computation for the convex polytopeTn are presented here in this section.There are 3-sided, 5-sided, andn-sided faces on the convex polytope Tn as shown in Figure 1.Figure 1
Convex polytopeTn.There are three types of vertex labels used here: {rω: ∀0≤ω≤n−1} represents the inner cycle vertex, {sω: 0≤ω≤n−1} represents the central cycle vertex, and {tω: ∀0≤ω≤n−1} represents the outer cycle vertex as shown in Figure 1.As a result of applying Theorem1, ψTn≥3 for n≥6 is obtained. Also, ψTn=3 for n≥6 will be proved in this section. Vertex distances of the graph Tn can be computed using the following procedure:Assume that the setSωs0=s∈VTn:ds0,s=ω is a vertex set in VTn at a distance of ω from s0. The Table 1 is simply constructed for Sωs0, and it will be used to figure out how far two vertices in VTn are from each other.Table 1
Sωs0 for Tn.
nωSωs01{r0, r1, t0}2≤ω≤⌊n/2⌋{rω, rn−ω+1, sω−1, sn−ω+1, tω−1, tn−ω+1,}evenn+2/2{sn/2, tn/2}oddn+1/2{rn+1/2, sn−1/2, sn+1/2, tn−1/2, tn+1/2}Because of the symmetry ofTn for n≥6, it can be demonstrated that(1)drω,rν=ds0,rω−ν−1,ifω−ν=0,ds0,rω−ν,if1≤ω−ν≤n2,ds0,rω−ν−1,ifn+22≤ω−ν≤n−1,dsω,tν=ds0,tω−ν,if0≤ω−ν≤n−1,dtω,tν=ds0,gω−ν−1,if0≤ω−ν≤n−1,dsω,sν=ds0,sω−ν,if0≤ω−ν≤n−1.Ifn is odd(2)drω,tν=ds0,tω−ν,if1≤ω−ν≤n2forω>ν,ds0,tω−ν+1,ifn+22≤ω−ν≤n−1forω>ν,ds0,tω−ν+1,if0≤ω−ν≤n2forν≥ω,ds0,tω−ν,ifn+22≤ω−ν≤n−1forν>ω,drω,sν=ds0,rω−ν+1,if1≤ω−ν≤n2forν>ω,ds0,rω−ν−1,ifn+22≤ω−ν≤n−1forν>ω,ds0,rω−ν,if0≤ω−ν≤n−1forω≥ν.Ifn is even(3)drω,tν=ds0,tω−ν,if1≤ω−ν≤n2forω>ν,ds0,tω−ν+1,ifn+22≤ω−ν≤n−1forω>ν,ds0,tω−ν+1,if0≤ω−ν≤n−22forν≥ω,ds0,tω−ν,ifn2≤ω−ν≤n−1forν>ω,drω,sν=ds0,rω−ν+1,if1≤ω−ν≤n−22forν>ω,ds0,rω−ν,ifω−ν=n2forν>ω,ds0,rω−ν−1,ifn+22≤ω−ν≤n−1forν>ω,ds0,rω−ν,if0≤ω−ν≤n−1forω≥ν.Due to the fact that, in order to calculate the distance between any pair of vertices inVTn, we must know the distance ds0,s for each s∈VTn.Lemma 1.
For the odd positive integern≥6, ψTn=3.Proof.
To demonstrate thatψTn=3 for the odd positive integer, finding a DRS with cardinality 3 is enough. Using the sets Sωs0 listed in Table 1, the Table 2 shows the metric coordinate vectors for all vertices of Tn with respect to DTn=r0,sn−1/2,t0.
Table2 shows that the representation rg1,DTn−rg2,DTn≠0 for any two vertices g1,g2∈Sωs0, where ω∈1,2,…,n+1/2. Consequently, for any ω,ν∈1,2,…,n+1/2 such as ω≠ν if the vertices g1∈Sωs0 and g2∈Sνs0, then the representation rg1,DTn−rg2,DTn≠ω−ν. So the collection DTn=r0,sn−1/2,t0 represents the MDRS of Tn. As a result, Lemma 1 holds.Table 2
Metric coordinate vectors ofTn for odd n≥6.
ωSωf0DTn=r0,sn−1/2,t00s01,n+1/2,11r00,n+1/2,2r11,n−1/2,2t02,n+1/2,02≤ω≤n−1/2rωω,n−2ω+1/2,ω+1rn−ω+1ω−1,n−2ω+3/2,ω+1sω−1ω,n−2ω+3/2,ωsn−ω+1ω−1,n−2ω+5/2,ωtω−1ω+1,n−2ω+3/2,ω−1tn−ω+1ω,n−2ω+5/2,ω−1n+1/2rn+1/2n−1/2,1,n+3/2sn−1/2n+1/2,0,n+1/2sn+1/2n−1/2,2,n+1/2tn−1/2n+3/2,1,n−1/2tn+1/2n+1/2,2,n−1/2Lemma 2.
For the even positive integern≥6, ψTn=3.Proof.
To demonstrate thatψTn=3 for the even positive integer n≥6, finding a DRS with cardinality 3 is enough. Using the sets Sωs0 listed in Table 1, the Table 3 shows the metric coordinate vectors for all vertices of Tn with respect to DTn=r0,rn/2,t0.
Table3 shows that the representation rg1,DTn−rg2,DTn≠0 for any two vertices g1,g2∈Sωs0, where ω∈1,2,…,n+2/2. Consequently, for any ω,ν∈1,2,…,n+2/2 such as ω≠ν if the vertices g1∈Sωs0 and g2∈Sνs0, then the representation rg1,DTn−rg2,DTn≠ω−ν. So the collection DTn=r0,rn/2,t0 represents the MDRS of Tn. As a result, Lemma 2 holds.
The entire technique clearly demonstrates thatψTn=3, for n≥6. The main theorem is stated below using Lemmas 1 and 2:Table 3
Metric coordinate vectors ofTn for even n≥6.
ωSωs0DTn=r0,rn/2,t00s01,n/2,11s00,n/2,2s11,n−2/2,2t02,n+2/2,02≤ω≤n/2rωω,n−2ω/2,ω+1rn−ω+1ω−1,n−2ω+2/2,ω+1sω−1ω,n−2ω+2/2,ωsn−ω+1ω−1,n−2ω+4/2,ωtω−1ω+1,n−2ω+4/2,ω−1tn−ω+1ω,n−2ω+6/2,ω−1n+2/2sn/2n/2,1,n+2/2tn/2n+2/2,2,n/2Theorem 3.
LetTn be a convex polytope, then ψTn=3 for n≥6.


## 3. Double Metric Dimension for the Convex PolytopeSn

This section contains the results of the DMD computation for the convex polytopeSn.There are 3-sided, 4-sided, andn-sided faces on the convex polytope Sn as shown in Figure 2.Figure 2
Convex polytopeSn.There are three types of vertex labels used here: {pω: ∀0≤ω≤n−1} represents the inner cycle vertex, {qω: ∀0≤ω≤n−1} represents the interior cycle vertex, {rω: ∀0≤ω≤n−1} represents the exterior cycle vertex, and {tω: ∀0≤ω≤n−1} represents the outer cycle vertex as shown in Figure 2.As a result of applying Theorem2, ψSn≥3 for n≥6 is obtained. Also, ψSn=3 for n≥6 will be proved in this section. Vertex distances of the graph Sn can be computed using the following procedure:Assume that the setSωq0=q∈VSn:dq0,q=ω is a vertex set in VSn at a distance of ω from q0. Table 4 is simply constructed for Sωq0, and it will be used to figure out how far two vertices in VSn are from each other.Table 4
Sωq0 for Sn.
nωSωq01{p0, pn−1, q1, qn−1, r0}2{p1, pn−2, q2, qn−2, r1, rn−1, t0}3≤ω≤⌊n/2⌋−1{pω−1, pn−ω, qω, qn−ω, rω−1, rn−ω+1, tω−2, tn−ω+2}evenn/2{pn−2/2, pn/2, qn/2, rn−2/2, rn+2/2, tn−4/2, tn+4/2}n+2/2{rn/2, tn−2/2, tn+2/2}n+4/2tn/2oddn−1/2{pn−3/2, pn+1/2, qn−1/2, qn+1/2, rn−3/2, rn+3/2, tn−5/2, tn+5/2}n+1/2{pn−1/2, rn−1/2, rn+1/2, tn−3/2, tn+3/2}n+3/2{tn−1/2, tn+1/2}Because of the symmetry ofSn for n≥6, it can be demonstrated that(4)dqω,tν=dq0,tω−ν,if0≤ω−ν≤n−1,dqω,rν=dq0,rω−ν,if0≤ω−ν≤n−1,drω,tν=dq0,tω−ν−1,if0≤ω−ν≤n−1,drω,rν=dtω,tν=dq0,rω−ν−1,if0≤ω−ν≤n−1,dqω,qν=dq0,qω−ν,if0≤ω−ν≤n−1.Ifn is odd(5)dpω,pν=dq0,pω−ν−1,if0≤ω−ν≤n−12,dq0,pω−ν,ifn+12≤ω−ν≤n−1,dqω,pν=dq0,pω−ν−1,if1≤ω−ν≤n−12forω>ν,dq0,pω−ν+1,ifn+12≤ω−ν≤n−1forω>ν,dq0,pω−ν,if0≤ω−ν≤n−1forν≥ω,dpω,rν=dq0,rω−ν+1,if0≤ω−ν≤n−12forω≥ν,dq0,rω−ν,ifn+12≤ω−ν≤n−1forω>ν,dq0,rω−ν,if1≤ω−ν≤n−12forν>ω,dq0,rω−ν+1,ifn+12≤ω−ν≤n−1forν>ω,dpω,tν=dq0,hω−ν+1,if0≤ω−ν≤n−12forω≥ν,dq0,hω−ν,ifn+12≤ω−ν≤n−1forω>ν,dq0,hω−ν,if1≤ω−ν≤n−12forν>ω,dq0,hω−ν+1,ifn+12≤ω−ν≤n−1forν>ω.Ifn is even(6)dpω,pν=dq0,pω−ν−1,if0≤ω−ν≤n−22,dq0,pqω−ν,ifn2≤ω−ν≤n−1,dpω,rν=dq0,rω−ν+1,if0≤ω−ν≤n−22forω≥ν,dq0,rω−ν,ifn2≤ω−ν≤n−1forω>ν,dq0,rω−ν,if1≤ω−ν≤n2forν>ω,dq0,rω−ν+1,ifn+22≤ω−ν≤n−1forν>ω,dqω,pν=dq0,pω−ν−1,if1≤ω−ν≤n−22forω>ν,dq0,pω−ν,ifω−ν=n2forω>ν,dq0,pω−ν+1,ifn+22≤ω−ν≤n−1forω>ν,dq0,pω−ν,if0≤ω−ν≤n−1forν≥ω,dpω,tν=dq0,tω−ν+1,if0≤ω−ν≤n−22forω≥ν,dq0,tω−ν,ifn2≤ω−ν≤n−1forω>ν,dq0,tω−ν,if1≤ω−ν≤n2forν>ω,dq0,tω−ν+1,ifn+22≤ω−ν≤n−1forν>ω.Due to the fact that, in order to calculate the distance between any pair of vertices inVSn, we need to know dq0,q for each q∈VSn.Lemma 3.
For any odd positive integern≥6, ψSn=3.Proof.
The MDRSs forS7, S9, and S11 are(7)DSn=p0,p3,t2,ifn=7,p0,p4,t7,ifn=9,p0,p5,t3,ifn=11,
to demonstrate thatψSn=3 for any odd positive integer n≥13, finding a DRS with cardinality 3 is enough. Using the sets Sωq0 listed in Table 4, the Table 5 shows the metric coordinate vectors for all vertices of Sn in relation to the set DSn=p0,pn−1/2,tn+7/2.
Table5 shows that the representation rh1,DSn−rh2,DSn≠0 for any two vertices h1,h2∈Sωq0, where ω∈1,2,…,n+3/2. Consequently, for any ω,ν∈1,2,…,n+3/2 such as ω≠ν if the vertices h1∈Sωq0 and h2∈Sνq0, then the representation rh1,DSn−rh2,DSn≠ω−ν. So the collection DSn=p0,pn−1/2,tn+7/2 represents the MDRS of Tn. As a result, Lemma 3 holds.Table 5
Metric coordinate vectors ofSn for odd n≥13.
ωSωf0DSn=p0,pn−1/2,tn+7/20q01,n+1/2,n−3/21p00,n−1/2,n−1/2pn−11,n−1/2,n−3/2q11,n−1/2,n−1/2qn−12,n−1/2,n−5/2r02,n+3/2,n−5/22p11,n−3/2,n+1/2pn−22,n−3/2,n−5/2q22,n−3/2,n+1/2qn−23,n−3/2,n−7/2r12,n+1/2,n−3/2rn−13,n+1/2,n−7/2t03,n+5/2,n−7/23≤ω≤n−3/2pω−1=2,n−5/2,n+3/2,ifω=2,ω−1,n−2ω+1/2,n−2ω+13/2,ifω≠2.pn−ω=ω,n−2ω+1/2,n−2ω−1/2,ifω≤n−7/2ω,n−2ω+1/2,2ω−n+11/2,ifω>n−7/2qω=3,n−5/2,n+3/2,ifω=3ω,n−2ω+1/2,n−2ω+11/2,ifω≠3qn−ω=ω+1,n−2ω+1/2,n−2ω−3/2ifω≤n−7/2ω+1,n−2ω+1/2,2ω−n+11/2,ifω>n−7/2rω−1=ω,n−2ω+5/2,n+2ω−7/2,ifω≤4ω,n−2ω+5/2,n−2ω+11/2ifω>4rn−ω+1=ω+1,n−2ω+5/2,n−2ω−3/2,ifω≠n−3/2n−1/2,4,2,ifω=n−3/2tω−2=ω,n−2ω+9/2,n+2ω−13/2,ifω≤5ω,n−2ω+9/2,n−2ω+11/2,ifω>5tn−ω+2ω+1,n−2ω+9/2,n−2ω−3/2n−1/2pn−3/2n−3/2,1,7pn+1/2n−1/2,1,5qn−1/2n−1/2,1,6qn+1/2n+1/2,1,5rn−3/2n−1/2,3,6rn+3/2n+1/2,3,3tn−5/2n−1/2,5,6tn+5/2n+1/2,5,1n+1/2pn−1/2n−1/2,0,6rn−1/2n+1/2,2,5rn+1/2n+3/2,2,4tn−3/2n+1/2,4,5tn+3/2n+3/2,4,2n+3/2tn−1/2n+3/2,3,4tn+1/2n+5/2,3,3Lemma 4.
For any even positive integern≥6, ψSn=3.Proof.
To demonstrate thatψSn=3 for any even positive integer n≥6, finding a DRS with cardinality 3 is enough. Using the sets Sωq0 listed in Table 4, the Table 6 shows the metric coordinate vectors for all vertices of Sn in relation to the set DSn=p0,pn−2/2,t1.
Table6 shows that the representation rh1,DSn−rh2,DSn≠0 for any two vertices h1,h2∈Sωq0, where ω∈1,2,…,n+4/2. Consequently, for any ω,ν∈1,2,…,n+4/2 such as ω≠ν if the vertices h1∈Sωq0 and h2∈Sνq0, then the representation rh1,DSn−rh2,DSn≠ω−ν. So the collection DSn=p0,pn−2/2,t1 represents the MDRS of Tn. As a result, Lemma 4 holds.
The entire technique clearly demonstrates thatψSn=3, for n≥6. The main theorem is stated below using Lemmas 3 and 4:Table 6
Metric coordinate vectors ofSn for even n≥6.
ωSωq0DSn=p0,pn−2/2,t10q01,n/2,21p00,n−2/2,2pn−11,n/2,3q11,n−2/2,1qn−12,n/2,3r02,n+2/2,12p11,n−4/2,3pn−22,n−2/2,5q22,n−4/2,3qn−23,n−2/2,5r12,n/2,1rn−13,n+2/2,3t03,n+4/2,13≤ω≤n−2/2pω−1ω−1,n−2ω/2,ω+1pn−ωω,n−2ω+2/2,ω+3qωω,n−2ω/2,ω+1qn−ωω+1,n−2ω+2/2,ω+3rω−1ω,n−2ω+4/2,ω−1rn−ω+1ω+1,n−2ω+6/2,ω+1tω−2ω,n−2ω+8/2,ω−3tn−ω+2ω+1,n−2ω+10/2,ω−1n/2pn−2/2n−2/2,0,n+2/2pn/2n/2,1,n+4/2qn/2n/2,1,n+4/2rn−2/2n/2,2,n−2/2rn+2/2n+2/2,3,n+2/2tn−4/2n/2,4,n−6/2tn+4/2n+2/2,5,n−2/2n+2/2rn/2n+2/2,2,n/2tn−2/2n+2/2,3,n−4/2tn+2/2n+4/2,4,n/2n+4/2tn/2n+6/2,3,n−2/2Theorem 4.
LetSn be the convex plytope for n≥6. Then ψSn=3.


## 4. Conclusion

In this paper, we investigate the idea of calculating MDRSs of graphs using an integer linear programming formulation previously presented in the literature. We calculate the DMD for the convex polytopesTn and Sn, which is the minimum cardinality over all the DRSs of Tn and Sn. It is interesting to consider these families of the convex polytopes because their DMD is finite and independent of the parity of n. Finally, we get ψTn=ψSn=3 for n≥6.



---

*Source: 5884924-2022-07-31.xml*