# Studies of Chordal Ring Networks via Double Metric Dimensions

Authors: M. Ahmad; Z. Zahid; M. Javaid; E. Bonyah
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Locating the sources of information spreading in networks including tracking down the origins of epidemics, rumors in social networks, and online computer viruses, has a wide range of applications. In many situations, identifying where an epidemic started, or which node in a network served as the source, is crucial. But it can be difficult to determine the root of an outbreak, especially when data are scarce and noisy. The goal is to find the source of the infection by analysing data provided by only a limited number of observers, such as nodes that can indicate when and where they are infected. Our goal is to investigate where the least number of observers should be placed, which is similar to how to figure out the minimal doubly resolving sets in the network. In this paper, we calculate the double metric dimension of chordal ring networksCRn1,3,5 by describing their minimal doubly resolving sets.


---

## Body

## 1. Introduction and Preliminaries

Suppose thatΓ is a connected, finite, and undirected graph. Its vertex set is VΓ and its edge set is EΓ. The distance df,g between two vertices f,g∈VΓ in a connected graph is the shortest path connecting those two vertices. If e∈VΓ is a vertex such as de,f≠de,g, then we say e resolves the vertices f and g. The representation rh,JΓ of a vertex h with respect to an ordered set JΓ  =  jυ|1≤υ≤ρ⊆VΓ is defined as a ρ-vector dh,j1,…,dh,jρ, also called the distance vector. If each vertex of the graph Γ has a unique distance vector with respect to the set JΓ, then JΓ is called the resolving set (or sometimes called locating set) for graph Γ. The minimum possible cardinality of a resolving set in Γ is called the metric dimension (MD), represented as dimΓ. A resolving set of cardinality dimΓ is said to be the metric basis of Γ.The notion of MD was first proposed by Slater in [1] and investigated independently by Harary and Melter in [2] because of the problem of locating an intruder in a network. Later, Chartrend and Zang [3] demonstrated various applications in biology, robotics, and chemistry. From a two-dimensional real plane, the MD of graphs can extend the concept of trilateration. For instance, distances are used by the Global Positioning System (GPS) to identify an object’s location on Earth. In the context of MD, Hamming graphs are closely related to the difficulties in weighing of coins discussed in [4, 5], and the comprehensive study of the Mastermind game given in [6].Resolvability of graphs has become a significant parameter in graph theory as a result of its widespread applicabilities in different areas of mathematics, including facility location problems, network discovery and verification [7], applications in molecular chemistry [8], the positioning of robots in a network [9], routing protocols geographically [10], the problems of sonar or LORAN stations [1], and the optimization problem in combinatorics [11]. After that, we will have a look at some research work on the mathematical significance of this distance-based parameter.The MD has been used to study a variety of mathematically interesting graph families. We will highlight some of the significant work in this section: Similar to many other graph-theoretic parameters, finding the MD of arbitrary graphs is a computationally tough task [9, 12]. For example, the bounds for the MD of the Petersen graph family was studied by Shao et al. [13]. On various distance-regular graphs (such as kayak paddle graphs and chorded cycles), Ahmad et al. investigated the MD [14]. Bailey et al. [15] investigated the MD of Kneser graphs. For wheel graphs, Buczkowski et al. in [16] investigated the MD, whereas Baca et al. in [17] examined the MD of regular bipartite graphs. Chartrand et al. [8] categorized n-vertex graphs with MD 1, n−2 and n−1. From the perspective of MD, graphs of relevance in group theory, such as Cayley digraphs [18] and Cayley graphs formed by certain finite groups [19], have also been investigated. [20] provides a response to the question of whether the MD is a finite number or an infinite quantity. The minimum ordered resolving sets of Jahangir graphs (resp. necklace graphs) were investigated by Tomescu et al. in [21] (resp. in [22]). Investigations have also been carried out into the MD and the resolving sets of product graphs, such as the categorical product of graphs [23] and the cartesian products [24].MD has also been generalised and extended by offering more mathematically rigorous general ideas, such as the double metric dimension (DMD). Caceres et al. [24] proposed and defined the notion of doubly resolving sets (DRSs) of graph Γ as follows: a pair of vertices g and h of graph Γ is said to double resolve vertices g′ and h′ if the following equation holds: dg′,g−dg′,h≠dh′,g−dh′,h. A DRS of Γ is a subset NΓ=k1,k2,…,kn of VΓ, where every two different vertices of Γ are resolved by some two vertices of NΓ. The minimal doubly resolving set (MDRS) problem is to find a DRS of Γ with the smallest cardinality, which is called the DMD of Γ indicated by ψΓ. If the vertices g′ and h′ can be doubly resolved by the vertices g and h then either dg′,g−dh′,g≠0 or dg′,h−dh′,h≠0 which follows that either g or h resolve the vertices g′ and h′.Because a DRS is also a resolving set, we haveψΓ≥dimΓ, so we can use the MDRSs to get an upper bound on the MD of the graph under discussion. The idea of establishing upper boundaries in the cartesian product encouraged us to explore on DRSs of different graph classes. In general graphs, the MDRS problem has been shown to be NP-hard [25]. Many families of graphs, such as cocktail graphs, prisms, and jellyfish graphs, have been studied for the problem of finding the MDRSs (for details see: [26, 27]). The MDRSs for convex polytope structures and Hamming graphs have been derived and may be found in [28], and [29], respectively. The DMD and minimal order resolving sets of Harary and circulant graphs were studied in [30, 31]. It was Chen et al. that provided the first approximated upper bounds for the MDRS problem [32]. The authors in [33, 34] demonstrated that the DMD of some convex polytope structures is finite and constant. The line graphs of chorded cycles [35], kayak paddle graphs [36], n-Sunlet, and prism graphs [37] were discovered to have the MD and DRSs. In [38], layersun graphs and associated line graphs were studied for the MDRSs. Liu et al. gave the results for the minimum order resolving sets and DMD of the line graph of the Necklace graph in [39].Using resolving sets is a natural way to find the origins of a network spread. For example, determining where a disease originated as it spreads through a population might be helpful in a variety of scenarios. A direct solution can be found if the time at which the spread began and the internode distances are reliable and known. Resolvability, however, needs to be expanded to account for things like an unknown start time and irregular transmission delays among nodes. The former problem can be solved by employing DRSs. The variation involved with arbitrary internode distances is critical in successfully determining the source of a spread [40].Detecting virus sources in starlike networks are more complicated than in pathlike networks. While the DMD isn−1 for a star-type structure with n nodes, and for a path-type structure with the same number of nodes it is 2 (see [40]). In addition, this demonstrates that the DMD is always reliant on the topology of the network being used.The purpose of this research is to find the MDRSs and DMD for a class of chordal ring networks, which are helpful in the designing of local area networks. The following result regarding the MD of chordal ring networksCRn1,3,5 is helpful in determining its DMD:Theorem 1.
[41] Let CRn1,3,5 be the chordal ring network. Then, for any even integer n≥6, we have dimCRn1,3,5=3,ifn≡0mod44,ifn≡2mod4
The rest of the article is arranged in this following way:(i)
In Section2, we discussed the construction of chordal ring networks and investigated the MDRSs of CRn1,3,5(ii)
Finally, in Section3, we summarize the findings of the article


## 2. Double Metric Dimension of Chordal Ring NetworksCRn1,3,5

In this section, we calculated the MDRSs and DMD for chordal ring networkCRn1,3,5.If every closed path of length 4 or more in an undirected network contains a chord, it is referred to as chordal. Arden and Lee [42] first proposed chordal ring networks of degree 3. An undirected cycle of even order can be used to form a chordal ring network, in which all newly added chords connect an even labelled node to an oddly labelled node.Letα,β,γ∈1,2,…,n−1 be three distinct odd integers and n≥3 be an even natural number. A chordal ring network having order n with chords α,β, and γ represented by CRnα,β,γ, has the nodes set Zn, and links are given by δ∼δ+α,δ∼δ+β and δ∼δ+γ for every even node δ∈Zn. By definition, every chordal ring network CRnα,β,γ is bipartite and 3-regular. Further, every odd node θ∈Zn forms a link with θ−α,θ−β,θ−γ in CRnα,β,γ. There are no specific rules for selecting three different odd integers α,β, and γ from the set 1,2,…,n−1. Actually, we can choose any three different odd integers and, as a result, we obtain different chordal ring networks each time, with the possibility that few of them are isomorphic. To make a CRnα,β,γ, select 3 different even integers from the set 1,2,…,n−1 and connect odd numbered nodes to them, as explained earlier. In addition, α,β, and γ are stated to be chords because they help to connect nodes in the CRnα,β,γ, and each obtained link represents a chord for at least one path in CRnα,β,γ as demonstrated in Figure 1.Figure 1
Chordal ring networkCR121,3,5.Here, the DMD.ψCRn1,3,5≥3,ifn≡0mod44,ifn≡2mod4for any even integer n≥6 by applying Theorem 1. Also, we are going to prove the DMD ψCRn1,3,5=4, for any even integer n≥6.DefineSυh0=h∈VCRn1,3,5:dh0,h=υ be a vertex set in VCRn1,3,5 at distance υ from h0. Table 1 is simply constructed for Sυh0 and employed to compute the distance between any pair of vertices in VCRn1,3,5.Table 1
Sυh0 for CRn1,3,5.
nυSυh01{h1, hn−3, hn−1}4l,l≥22≤υ≤l=h2υ−2,h2υ,hn−2υ,hn−2υ+2,ifυis evenh2υ−3,h2υ−1,hn−2υ−1,hn−2υ+1,ifυis oddl+1=h2υ−2,ifυis evenh2υ−3,ifυis odd4l+2,l≥12≤υ≤l+1=h2υ−2,h2υ,hn−2υ,hn−2υ+2,ifυis evenh2υ−3,h2υ−1,hn−2υ−1,hn−2υ+1,ifυis oddThe symmetry ofCRn1,3,5 for any even integer n≥6, shows the following fact that: dhυ,hτ=dh0,hτ−υ if 0≤τ−υ≤n−1.As a conclusion, by knowing the distancedh0,h for all h∈VCRn1,3,5, we can reconstruct the distances between every two vertices in VCRn1,3,5.Lemma 1.
Forn≥8 and n≡0mod4, we have ψCRn1,3,5>3.Proof.
We know thatψCRn1,3,5≥3. Therefore, we need to explain that every set DCRn1,3,5⊆VCRn1,3,5 of order 2 is not a DRS for CRn1,3,5. There are some different types of set DCRn1,3,5, as well as their nondoubly resolved pair of vertices from VCRn1,3,5, listed in Table 2. Let us show that the vertices h0,hn−3 are not doubly resolved by any two vertices of the set h0,hυ,hτ;1≤υ≤2l−2andτ=n−1. Now, for 1≤υ≤2l−2 and τ=n−1:(1)dh0,h0=0,(2)dh0,hn−3=1,(3)dh0,hυ=υ,(4)dhυ,hn−3=dh0,hn−3−υ=υ+1,(5)dh0,hτ=1,(6)dhτ,hn−3=dh0,hn−3−τ=2.
From equations (1) to (6), we have dh0,h0−dh0,hn−3=dh0,hυ−dhυ,hn−3=dh0,hτ−dhτ,hn−3=−1, that is, the set h0,hυ,hτ;1≤υ≤2l−2andτ=n−1 is not a DRS of CRn1,3,5. All other forms of the set DCRn1,3,5 in Table 2 can be examined and confirmed to have nondoubly resolved vertices, as well.Table 2
Nondoubly resolved pairs of vertices forCRn1,3,5, for n≥8 and n≡0mod4
DCRn1,3,5Nondoubly resolved pairsh0,hυ,hτ, υ=1,n−4≤τ≤n−3h0,hn−1h0,hυ,hτ, 2≤υ≤3,n−4≤l≤n−3h1,hn−1h0,hυ,hτ, 4≤υ≤5,n−4≤l≤n−3h0,hn−1h0,hυ,hτ, 1≤υ<τ≤2l−2h0,hn−3h0,hυ,hτ, 2l+1≤υ<τ≤n−1h0,h1h0,hυ,hτ, 1≤υ≤2l−2,τ=n−1h0,hn−3h0,hυ,hτ, 2l−1≤υ≤2l,τ=n−1h1,hn−3Lemma 2.
Letn≡0mod4 for n≥8, we have ψCRn1,3,5=4.Proof.
Consider the case wheren≡0mod4 for n≥8. To demonstrate that ψCRn1,3,5=4, a DRS of order 4 is all that is required. Now, by using the sets Sυh0 from Table 1, Tables 3 and 4 demonstrate the metric coordinate vectors for each vertex of CRn1,3,5 in relation to the set DCRn1,3,5=h0,h1,h2,h2l−1, where n=4l and l≥2 be an integer.
Using Tables3 and 4, it is possible to verify directly that, for any given integer υ∈1,2,…,l+1 if two vertices a1,a2∈Sυh0, then the difference between their first coordinates is zero, but the difference between their overall coordinates is not zero that is the representation ra1,DCRn1,3,5−ra2,DCRn1,3,5≠0. In the same way, for the vertices a1∈Sυh0 and a2∈Sτh0 for any υ≠τ∈1,2,…,l+1, the difference between their first coordinates is υ−τ but the difference between all coordinates is not υ−τ at the same time, that is the representation ra1,DCRn1,3,5−ra2,DCRn1,3,5≠υ−τ. Therefore, the set DCRn1,3,5=h0,h1,h2,h2l−1 is the MDRSs. Thus, Lemma 2 holds.Table 3
Metric coordinate vectors forCRn1,3,5, where n=4l, l≥2 is even.
υSυh0DCRn1,3,5=h0,h1,h2,h2l−10h00,1,2,l+11h11,0,1,lhn−31,2,3,lhn−11,2,1,l2≤υ≤l,whenυis evenh2υ−2υ,υ−1,υ−2,l−υ+1h2υυ,υ−1,υ,l−υ+1hn−2υ=υ,υ+1,υ+2,l−υ+1,ifυ<lυ,υ−1,υ,1,ifυ=lhn−2υ+2υ,υ+1,υ,l−υ+1whenυis oddh2υ−3υ,υ−1,υ−2,l−υ+1h2υ−1υ,υ−1,υ,l−υ+1hn−2υ−1υ,υ+1,υ+2,l−υ+1hn−2υ+1υ,υ+1,υ,l−υ+1υ=l+1,whenυis oddh2υ−3υ,υ−1,υ−2,0Table 4
Metric coordinate vectors forCRn1,3,5, where n=4l, l≥2 is odd.
υSυh0DCRn1,3,5=h0,h1,h2,h2l−10h00,1,2,l1h11,0,1,l−1hn−31,2,3,l−1hn−11,2,1,l+12≤υ≤l,whenυis evenh2υ−2v,υ−1,υ−2,l−υ+2h2υυ,υ−1,υ,l−υhn−2υ=υ,υ+1,υ+2,l−υ,ifυ<l−1υ,υ+1,υ+2,1,ifυ=l−1hn−2υ+2υ,υ+1,υ,l−υ+2whenυis oddh2υ−3υ,υ−1,υ−2,l−υ+2h2υ−1υ,υ−1,υ,l−υhn−2υ−1=υ,υ+1,υ+2,l−υ,ifυ<lυ,υ−1,υ,0,ifυ=lhn−2υ+1υ,υ+1,υ,l−υ+2υ=l+1,whenυis evenh2υ−2υ,υ−1,υ−2,1Lemma 3.
Letn≡2mod4 for n≥6, we have ψCRn1,3,5=4.Proof.
Consider the case wheren≡2mod4 for n≥6. To demonstrate that ψCRn1,3,5=4, a DRS of order 4 is all that is required. Now, by using the sets Sυh0 from Table 1, Tables 5 and 6 demonstrate the metric coordinate vectors for each vertex of CRn1,3,5 in relation to the sets DCRn1,3,5=h0,h1,h2,h2l+1 and DCRn1,3,5=h0,h1,h2,h2l+2 respectively, where n=4l+2 and l≥1 be an integer.
Using Tables5 and 6, it is possible to verify directly that, for any given integer υ∈1,2,…,l+1 if two vertices b1,b2∈Sυh0, then the difference between their first coordinates is zero, but the difference between their overall coordinates is not zero, that is the representation rb1,DCRn1,3,5−rb2,DCRn1,3,5≠0. In the same way, for the vertices b1∈Sυh0 and b2∈Sτh0 for any υ≠τ∈1,2,…,l+1, the difference between their first coordinates is υ−τ but the difference between all coordinates is not υ−τ at the same time, that is the representation rb1,DCRn1,3,5−rb2,DCRn1,3,5≠υ−τ. Therefore, the sets DCRn1,3,5=h0,h1,h2,h2l+1 and DCRn1,3,5=h0,h1,h2,h2l+2 are the MDRSs. Thus, Lemma 3 holds.
Using Lemmas2 and 3, the main theorem is stated below:Table 5
Metric coordinate vectors forCRn1,3,5, where n=4l+2, l≥1 is odd.
υSυh0DCRn1,3,5=h0,h1,h2,h2l+10h00,1,2,l1h11,0,1,l+1hn−3=1,2,1,0,ifn=61,2,3,l−1,ifn≠6hn−11,2,1,l+12≤υ≤l+1,whenυis evenh2υ−2υ,υ−1,υ−2,l−υ+2h2υυ,υ−1,υ,l−υ+2hn−2υ=υ,υ+1,υ+2,l−υ,ifυ<l+1υ,υ−1,υ−2,1,ifυ=l+1hn−2υ+2=υ,υ+1,υ,l−υ+2,ifυ<l+1υ,υ−1,υ,1,ifυ=l+1whenυis oddh2υ−3υ,υ−1,υ−2,l−υ+2h2υ−1υ,υ−1,υ,l−υ+2hn−2υ−1=υ,υ+1,υ+2,l−υ,ifυ<lυ,υ+1,υ,0,ifυ=lhn−2υ+1υ,υ+1,υ,l−υ+2Table 6
Metric coordinate vectors forCRn1,3,5, where n=4l+2, l≥1 is even.
υSυh0DCRn1,3,5=h0,h1,h2,h2l+20h00,1,2,l1h11,0,1,l+1hn−31,2,3,l−1hn−11,2,1,l+12≤υ≤l+1,whenυis evenh2υ−2υ,υ−1,υ−2,l−υ+2h2υυ,υ−1,υ,l−υ+2hn−2υ=υ,υ+1,υ+2,l−υ,ifυ<lυ,υ+1,υ,0,ifυ=lhn−2υ+2υ,υ+1,υ,l−υ+2whenυis oddh2υ−3υ,υ−1,υ−2,l−υ+2h2υ−1υ,υ−1,υ,l−υ+2hn−2υ−1=υ,υ+1,υ+2,l−υ,ifυ<l+1υ,υ−1,υ−2,1,ifυ=l+1hn−2υ+1=υ,υ+1,υ,l−υ+2,ifυ<l+1υ,υ−1,υ,1,ifυ=l+1Theorem 2.
LetCRn1,3,5 be the chordal ring network. Then for any even integer n≥6, ψCRn1,3,5=4.


## 3. Conclusion

This study is concerned with the concept of calculating MDRSs of graphs that has been proposed earlier in the literature. The DMD of chordal ring networksCRn1,3,5 is computed by describing their MDRSs. In this study, we found that the number of vertices in the chordal ring networks does not affect its DMD.



---

*Source: 8303242-2022-08-31.xml*