Quadrature-free polytopic discontinuous Galerkin methods for transport problems

1.   Introduction and preliminaries

Combinatorics is the study of how items are arranged by predetermined principles. Combinatorial approaches are required to count, enumerate, or describe potential solutions. Many difficult real-world situations require finding an optimal solution in a finite solution space. The literature contains a large number of issues that could be solved in polynomial time, even though some practical problems, such as determining the shortest or cheapest roundtrips, internet data packet routing, planning, scheduling, and timetabling, appear to be NP-complete. Several combinatorial strategies can be used to achieve this, including metric dimension (MD), fault-tolerant MD, and DMD. The networks considered in this study are simple (no multiple loops permitted), finite (both edge and vertex sets are finite), linked (a path exists between any two pairs of vertices), and undirected (the edges are not oriented). Consider a network $G$ of order $n$ with the edge set $E_{G}$ and vertex set $V_{G}$. For a vertex $\nu\in V_{G}$, the representation (l-tuple) $r(\nu) = (d_\tau| 1\leq \tau\leq l)$, where $d_\tau = d_\tau(\nu, \nu_\tau)$, is said to be the distance vector of the vertex $\nu$. The distance vector between two vertices $\nu\neq u$ could be the same. In this case, the question of determining which vertices have unique distance vectors arises. This difficulty led to the definition of the resolving sets, introduced by Slater ^[1] in 1975 and Harary and Melter ^[2] in 1976.

Definition 1.1. 1) The vertex $x\in V_{G}$ determines (resolves) the vertices $v, w \in V_{G}$ if $d(v, x)\neq d(w, x)$.

2) Let $W_{G}\subseteq V_{G}$, where $W_{G} = \{y_{\tau}| 1\leq \tau\leq l\}; (l\leq n)$ is an ordered set and $z\in V_{G}$, then the notation $r(z| W_{G})$ is the distance vector of the vertex $z$ in association with $W_{G}$ is the $l$-tuple $\Big(d(z, y_{\tau})\Big)^l_{\tau = 1}$, also called the vector of metric coordinates.

3) The set $W_{G}$ is said to be a resolving set for network $G$, if the $l$-tuple $\Big(d(z, y_{\tau})\Big)^l_{\tau = 1}$ is unique with respect to $z$.

4) A metric basis of network $G$ is a resolving set with minimal number of entries. The number of entries in a metric basis is denoted by $\dim(G)$ and is called the MD of $G$.

The MD has a wide range of potential applications in science, sociology, and engineering. In this context, we will explore the diverse applications of the MD within different scientific fields. Several disciplines, such as telecommunications ^[3], establishing routing protocols geographically ^[4], combinatorial optimization ^[5], and robotics ^[6] have benefited from the rise and diversity of MD applications. Another area where the MD has significant implications is network discovery and verification ^[3]. Many applications in chemistry are derived from the vertex-edge relation in networks and its equivalence to the atom and bond relation ^[7]. Many strategies for the Mastermind ^[8] games are built using the resolving sets, and the MD of hamming networks is linked to various coin-weighing difficulties explained in ^[9,10]. It is natural to investigate the mathematical features of this parameter due to its significance in other scientific fields. And after that, we look at some studies on the mathematical importance of this graph-theoretic parameter.

Several network families of mathematical importance have been studied from the perspective of MD. The field of MD has seen significant advancements, which we will discuss below. The chorded cycle, kayak paddle networks ^[11], and Mobius ladders ^[12] are examples of families for which MD has been estimated. Bailey and others have examined the MD of specific families of distance-regular networks, such as Grassmann networks ^[13], Kneser networks, and Johnson networks ^[14].

Cayley networks and Cayley digraphs, which are examples of networks generated by finite groups with group-theoretic importance, have been studied from the MD perspective ^[15,16]. There has also been research into the MD and resolving sets of product networks, such as the categorical product of networks ^[17] and the cartesian product of graphs ^[18]. Kratica et al. ^[19] (and, respectively, Imran et al. ^[20]) investigated the MD of rotationally symmetric convex polytopes (and, respectively, convex polytopes created by wheel-related networks). Siddiqui et al. ^[21] investigated certain infinite families derived from wheel networks for the MD problem.

Burdett et al. ^[22] determined various domination numbers for flower snarks, including independent domination, 2-domination, total domination, connected domination, upper domination, secure domination, and weak Roman domination numbers. In ^[23], the exact results of the mixed MD on two special classes of networks, namely flower snarks and wheel-related networks, were presented. Another study by Girisha et al. ^[24] characterized the MD and distance matrix of flower snark and sunflower networks. Additionally, due to computational complexity in finding exact values, Liu et al. provided bounds for the partition dimension of certain convex polytope structures in their work ^[25]. Lastly, Nawaz et al. ^[26] discussed the edge MD of various structures of benzodiazepines, which are types of drugs used for the treatment of depression.

Caceres et al. ^[27] responded to the question of whether the MD is a finite number. They demonstrated this by constructing infinite families of networks having infinite MDs. The computational difficulty of the MD problem was addressed by Garey and Johnson ^[28], just like many other graph-theoretic characteristics. The bounds of the MD have been examined for generalized Petersen networks by Shao et al. (refer to ^[29]). All connected networks possessing MDs $n-1$, $n-2$, and 1 were determined by Chartrand et al. ^[7]. Raza et al. ^[30] examined the fault-tolerant MD of infinite sets of regular networks, categorizing them accordingly. Baca et al. ^[31] and Tomescu et al. ^[32] studied the concept of resolving sets for the regular bipartite networks and the family of necklace networks, respectively. For more details, see ^[33,34].

MD and its associated parameters are widely used among researchers today because of the relevance of MD in the identification of nodes in networks. The concept of the DRS and DMD of the network, which is a generalization of the MD of the network, is a distinctive and significant parameter. The term "DRS" was defined by Caceres et al. ^[18] as follows:

Definition 1.2. 1) The vertices $e_{1}, e_{2} \in G$ (where $|G|\geq 2$) are said to doubly resolve the vertices $f_{1}, f_{2}$ of network $G$ if $d(e_{1}, f_{1})-d(e_{1}, f_{2})\neq d(e_{2}, f_{1})-d(e_{2}, f_{2})$.

2) An ordered set $D_{G} = \{e_\tau| 1\leq \tau\leq l\}$ of $G$ is a DRS of $G$ if there does not exist a pair of vertices in $G$ that has the same difference in their associated metric coordinates with respect to $D_{G}$.

3) In other words, all coordinates of the vector $r(f_{1}|D_{G})-r(f_{2}|D_{G})$ cannot be the same for any pair of distinct vertices $f_{1}, f_{2} \in V_{G}$. i.e. $r(f_{1}|D_{G})-r(f_{2}|D_{G})\neq \gamma I$, where $I$ is the unit vector $(1, 1, \ldots, 1)$ and $\gamma$ is an integer.

A DRS having a minimal cardinal number is called a MDRS. The cardinal number of an MDRS is the DMD of $G$, denoted by $\psi(G)$. Moreover, a DRS is a resolving set as well, and $\psi(G)\leq \dim(G)$. It was shown in ^[35] (and, respectively, in ^[6]) that finding $\psi(G)$ (and, respectively, $\dim(G)$) is an NP-hard task. The task of identifying MDRSs for necklace networks and certain convex polytopes was first addressed in ^[36] and ^[19]. Furthermore, authors in ^[37,38] demonstrated that the DMD remains constant for certain convex polytope structures. For various families of Harary networks, Ahmad et al. calculated the MDRSs (see ^[39] for more information).

In ^[40], it was shown that the $\dim(G)$ and $\psi(G)$ of some families of circulant networks were the same in all cases. The problem of determining the MDRS is discussed for many network families; for example, the MDRSs of prisms and Hamming networks were investigated in ^[41] and ^[42], respectively. Chen and Wang ^[43] conducted a study to identify the MDRSs for trees, cycles, wheels, and $k$-edge-augmented trees. In another study ^[44], Chen et al. were the first to present explicit approximations of upper and lower bounds for the MDRS problem.

An investigation into the MDRSs and MD of certain network families was conducted by Liu et al. ^[45]. In a recent study, Ahmad et al. ^[46] investigated the MDRSs for the chordal ring networks. Moreover, in ^[47], the MDRSs of layer-sun networks and their line networks have been explored in detail. The DMD and MDRSs for certain classes of convex polytopes were found by Pan et al. ^[48]. Jannesari ^[49] characterized all networks $G$ having the DMD 2 by using 2-connected subgraphs of network $G$. Recently, the generalized solutions for the DRS problem of several families of networks were found by Ahmad et al. ^[50].

The reason for studying doubly resolving sets (DRSs) is their potential to improve the accuracy and efficiency of source detection in different network scenarios. Our study aimed to explore the theoretical principles of certain network properties using the flower snark network as a model due to its distinct and well-defined structural characteristics. The results of the study are significant as they present calculated double metric dimensions (DMDs) for complex network models such as flower snarks and quasi-flower snarks. These findings not only demonstrate the real-world application of DRSs in intricate networks but also provide valuable insights into their structural traits. This comprehension can guide future work in the theory of networks and its practical implementations, leading to more effective source detection techniques in various real-world networks.

MDRSs play a crucial role in identifying diffusion sources in intricate networks. Locating the origins of an outbreak in such networks is an exciting yet challenging task. For instance, consider the scenario where the only available information about the epidemic is from a subset of nodes referred to as sensors. These sensors can indicate if and when they have been infected with the virus. The question then arises: What is the minimum number of sensors required to identify the source of the outbreak accurately? Fortunately, a well-known network feature called DMD offers a solution to this problem (for details, see ^[51,52]).

Let us look at a few real-world instances. The DMD in an $n$-node star network is $n-1$. DRSs cannot be formed from sets that do not include all of the external nodes. On the other hand, the DMD for a path network is 2. The two nodes, one at each end of the path, are sensors always sufficient to identify the source. Using these instances, it is clear that the DMD and the difficulty in finding the source largely depend on the network topology. A path-like network makes it far easier to find the source of an outbreak than a star-like network ^[52].

The results on minimal resolving sets for the flower snark $J_m$ and quasi-flower snarks $G_m$ were determined by Imran et al. ^[53] and Naeem et al. ^[54] and are given in the following theorems:

Theorem 1.3. ^[53] Let $J_{m}$ be the flower snark. Then, for every odd positive integer $m\geq 5$, we have $\dim(J_{m}) = 3$.

Theorem 1.4. ^[54] Let $G_{m}$ be the quasi-flower snark. Then, for every positive integer $m\geq 4$, we have dim$(G_{m}) = \left\{ \begin{array}{ll} 3, & {\rm{if}}\ m\ {is\ odd}\; \\ \leq 4, & {{otherwise}}. \end{array} \right.$

The results presented above determine the lower bound on the DMD of flower snarks $J_m$ and quasi-flower snarks $G_m$. Following is how the main contribution of the article is structured:

● We compute the DMD for flower snarks $J_{m}$ and quasi-flower snarks $G_{m}$ in Sections 2 and 3.

● The utilization of the research in the context of the source of diffusion in a complex network is presented in Section 4.

● Finally, in Section 5, we demonstrate that the DMD for flower snarks depends on the order of the network, and the DMD for quasi-flower snarks is independent of the order of the network.

2.   Double metric dimension for the flower snarks $J_{m}$

In this section, we will concentrate on determining the DMD of flower snarks $J_{m}$.

The flower snark $J_{m}$, depicted in Figure 1, is a cubic network comprising $4m$ vertices and $6m$ edges. The vertex set for the flower snarks $J_{m}$ is $V_{J_{m}}$ = $\{c_{\tau}, f_{\tau}, g_{\tau}, h_{\tau}$: $\forall$ $0\leq \tau\leq m-1\}$, and the edge set is $E_{J_{m}}$ = $\{c_{\tau}c_{\tau+1}, c_{\tau}f_{\tau}, f_{\tau}g_{\tau}, f_{\tau}h_{\tau}, g_{\tau}g_{\tau+1}, h_{\tau}h_{\tau+1}$: $\forall$ $0\leq \tau \leq m-2 \} \bigcup$ $\{c_{m-1}c_{0}, c_{m-1}f_{m-1}, f_{m-1}g_{m-1}, f_{m-1}h_{m-1}, g_{m-1}g_{0}, h_{m-1}h_{0}, g_{0}h_{m-1}, g_{m-1}h_{0}\}$.

As shown in Figure 1, the inner cycle vertices are labeled as $\{c_\tau$ : $\forall$ $0\leq \tau\leq m-1\}$, the set of central vertices are labeled as $\{f_\tau$ : $\forall$ $0\leq \tau \leq m-1\}$, and the outer cycle vertices are labeled as $\{g_\tau$ : $\forall$ $0\leq \tau\leq m-1\}$ $\bigcup$ $\{h_\tau$ : $\forall$ $0\leq \tau\leq m-1\}$.

MDRSs for $J_{m}$ are to be found in this section. It follows from Theorem 1.3 that $\psi(J_{m})\geq 3$, for all $m\geq 6$. We shall also show, for all $m\geq 6$:

Define the vertex subset $S_{\tau}(f_{0}) = \{g\in V_{J_{m}}: d(f_{0}, g) = \tau\} \subseteq V_{J_{m}}$ having distance $\tau$ from $f_{0}$. The Table 1 is a simple formulation for $S_{\tau}(f_{0})$ and will be used to compute the distances between each pair of vertices in $V_{J_{m}}$.

The following facts can be demonstrated as a result of the symmetry of $J_{m}$, where $m\geq 6$:

$d(f_{\tau}, f_{\upsilon}) = d(f_{0}, f_{|\tau-\upsilon|})$ if $0 \leq |\tau-\upsilon|\leq m-1;$ $d(c_{\tau}, c_{\upsilon}) = d(f_{0}, c_{|\tau-\upsilon|})-1$ if $0 \leq |\tau-\upsilon|\leq m-1;$

$d(c_{\tau}, f_{\upsilon}) = d(f_{0}, c_{|\tau-\upsilon|})$ if $0 \leq |\tau-\upsilon|\leq m-1;$

$d(c_{\tau}, g_{\upsilon}) = d(c_{\tau}, h_{\upsilon}) = d(f_{0}, c_{|\tau-\upsilon|})+1$ if $0 \leq |\tau-\upsilon|\leq m-1;$

$d(f_{\tau}, g_{\upsilon}) = d(f_{\tau}, h_{\upsilon}) = d(f_{0}, g_{|\tau-\upsilon|})$ if $0 \leq |\tau-\upsilon|\leq m-1.$

If $m$ is an odd integer, then

If $m$ is an even integer, then

Therefore, we can recalculate the distances between each pair of vertices in $V_{J_{m}}$ if $d(f_{0}, g)$ is known for each $g\in V_{J_{m}}$.

Lemma 2.1. For any even positive integer $m\geq 6$, $\psi\big(J_{m}\big) > 4$.

Proof. To prove the DMD $\psi\big(J_{m}\big) > 4$, we must show that every subset $D_{J_{m}}\subseteq V_{J_{m}}$ of cardinality 4 is not a DRS for $J_{m}$. Table 2 demonstrates the non-doubly resolved pairs of vertices from the set $V_{J_{m}}$ as well as all possible forms of subset $D_{J_{m}}$. Let us compute that any two vertices of the set $\{c_{\tau}, c_{\upsilon}, c_{\omega}, f_{0}; 0\leq \tau < \upsilon < \omega\leq m-1\}$ do not doubly resolve the vertices $f_{0}, g_{0}$. For example, it is clear that $d(f_{0}, f_{0}) = 0, d(f_{0}, g_{0}) = 1$. Now, for $0\leq \tau\leq \frac{m-2}{2}, 1\leq \upsilon\leq \frac{m-2}{2}, 2\leq \omega\leq \frac{m-2}{2}$, we have

● $d(c_{\tau}, f_{0}) = d(f_{0}, c_{\tau}) = \tau+1,$

● $d(c_{\tau}, g_{0}) = d(f_{0}, c_{\tau})+1 = \tau+2,$

● $d(c_{\upsilon}, f_{0}) = d(f_{0}, c_{\upsilon}) = \upsilon+1,$

● $d(c_{\upsilon}, g_{0}) = d(f_{0}, c_{\upsilon})+1 = \upsilon+2,$

● $d(c_{\omega}, f_{0}) = d(f_{0}, c_{\omega}) = \omega+1,$

● $d(c_{\omega}, g_{0}) = d(f_{0}, c_{\omega})+1 = \omega+2.$

Also, for $\frac{m}{2}\leq \tau\leq m-3, \frac{m}{2}\leq \upsilon\leq m-2, \frac{m}{2}\leq \omega\leq m-1$, we have

● $d(c_{\tau}, f_{0}) = d(f_{0}, c_{\tau}) = m-\tau+1,$

● $d(c_{\tau}, g_{0}) = d(f_{0}, c_{\tau})+1 = m-\tau+2,$

● $d(c_{\upsilon}, f_{0}) = d(f_{0}, c_{\upsilon}) = m-\upsilon+1,$

● $d(c_{\upsilon}, g_{0}) = d(f_{0}, c_{\upsilon})+1 = m-\upsilon+2,$

● $d(c_{\omega}, f_{0}) = d(f_{0}, c_{\omega}) = m-\omega+1,$

● $d(c_{\omega}, g_{0}) = d(f_{0}, c_{\omega})+1 = m-\omega+2.$

So, $d(c_{\tau}, f_{0})- d(c_{\tau}, g_{0}) = d(c_{\upsilon}, f_{0})- d(c_{\upsilon}, g_{0}) = d(c_{\omega}, f_{0})- d(c_{\omega}, g_{0}) = d(f_{0}, f_{0})- d(f_{0}, g_{0}) = -1$, that is, the set $\{c_{\tau}, c_{\upsilon}, c_{\omega}, f_{0}; 0\leq \tau < \upsilon < \omega\leq m-1\}$ is not a DRS of $J_m$. Accordingly, we can investigate all the possible types of subset $D_{J_{m}}$ shown in Table 2 and verify their associated non-doubly resolved pairs of vertices. □

Lemma 2.2. For any odd positive integer $m\geq 6$, $\psi\big(J_{m}\big) > 3$.

Proof. To prove the DMD $\psi\big(J_{m}\big) > 3$, we must show that every subset $D_{J_{m}}\subseteq V_{J_{m}}$ of cardinality 3 is not a DRS for $J_{m}$. Table 3 demonstrates the non-doubly resolved pairs of vertices from the set $V_{J_{m}}$ as well as all possible forms of subset $D_{J_{m}}$. Let us compute that any two vertices of the set $\{f_{0}, g_{\tau}, h_{\upsilon}; 0\leq \tau, \upsilon\leq m-1\}$ do not doubly resolve the vertices $c_{0}, f_{0}$. For example, it is clear that $d(c_{0}, f_{0}) = 1, d(f_{0}, f_{0}) = 0$. Now, for $0\leq \tau, \upsilon\leq \frac{m-1}{2}$, we have

● $d(c_{0}, g_{\tau}) = d(f_{0}, c_{\tau})+1 = \tau+2,$

● $d(f_{0}, g_{\tau}) = d(f_{0}, g_{\tau}) = \tau+1,$

● $d(c_{0}, h_{\upsilon}) = d(f_{0}, c_{\upsilon})+1 = \upsilon+2,$

● $d(f_{0}, h_{\upsilon}) = d(f_{0}, g_{\upsilon}) = \upsilon+1.$

Also, for $\frac{m+1}{2}\leq \tau, \upsilon\leq m-1$, we have

● $d(c_{0}, g_{\tau}) = d(f_{0}, c_{\tau})+1 = m-\tau+2,$

● $d(f_{0}, g_{\tau}) = d(f_{0}, g_{\tau}) = m-\tau+1,$

● $d(c_{0}, h_{\upsilon}) = d(f_{0}, c_{\upsilon})+1 = m-\upsilon+2,$

● $d(f_{0}, h_{\upsilon}) = d(f_{0}, g_{\upsilon}) = m-\upsilon+1.$

So, $d(c_{0}, g_{\tau})- d(f_{0}, g_{\tau}) = d(c_{0}, h_{\upsilon})- d(f_{0}, h_{\upsilon}) = d(c_{0}, f_{0})- d(f_{0}, f_{0}) = 1$, that is, the set $\{f_{0}, g_{\tau}, h_{\upsilon}; 0\leq \tau, \upsilon\leq m-1\}$ is not a DRS of $J_m$. Accordingly, we can investigate all the possible types of subset $D_{J_{m}}$ shown in Table 3 and verify their associated non-doubly resolved pairs of vertices. □

Lemma 2.3. $\psi\big(J_m\big) = 5, \forall$ even integers $m\geq 6$.

Proof. It suffices to identify a DRS having order 5 to demonstrate that $\psi\big(J_m\big) = 5$, if $m\geq 6$ is an even integer. Now, by using the sets $S_{\tau}(f_{0})$ from Table 1, the metric coordinate vectors are demonstrated in Table 4 for each vertex of $J_m$ with respect to the set $D_{J_m} = \{c_{0}, c_{1}, c_{\frac{m}{2}}, g_{0}, g_{m-1}\}$.

Now, consider Table 4, where the vector of $f_{0}\in S_{\tau}(f_{0})$ has its first metric coordinate equal to 1. We may also check that no two vertices $a_1, a_2 \in S_{\tau}(f_{0})$ exist such as $r(a_1, D_{J_m})- r(a_2, D_{J_m}) = 0I$, where $I$ is the unit vector and $\tau\in \{1, 2, \ldots, \frac{m+4}{2}\}$. Furthermore, no two vertices $a_1 \in S_{\tau}(f_{0})$ and $a_2 \in S_{\upsilon}(f_{0})$ exist such as $r(a_1, D_{J_m})- r(a_2, D_{J_m}) = \tau- \upsilon$, for some $\tau, \upsilon\in \{1, 2, \ldots, \frac{m+4}{2}\}$ and $\tau\neq \upsilon$. Finally, the set $D_{J_m} = \{c_{0}, c_{1}, c_{\frac{m}{2}}, g_{0}, g_{m-1}\}$ is the MDRS. As a result, Lemma 2.3 holds true. □

Lemma 2.4. $\psi\big(J_m\big) = 4, \forall$ odd integers $m\geq 6$.

Proof. To demonstrate that $\psi\big(J_m\big) = 4$, where $m\geq 6$ is an odd integer, it is enough to find a DRS of order 4. Now, by using the sets $S_{\tau}(f_{0})$ from Table 1, the metric coordinate vectors are demonstrated in Table 5 for each vertex of $J_m$ with respect to the set $D_{J_m} = \{c_{0}, c_{\frac{m-3}{2}}, f_{\frac{m-1}{2}}, g_{0}\}$.

Now, consider Table 5, where the vector of $f_{0}\in S_{\tau}(f_{0})$ has its first metric coordinate equal to 1. We may also check that no two vertices $a_1, a_2 \in S_{\tau}(f_{0})$ exist such as $r(a_1, D_{J_m})- r(a_2, D_{J_m}) = 0I$, where $I$ is the unit vector and $\tau\in \{1, 2, \ldots, \frac{m+3}{2}\}$. Furthermore, no two vertices $a_1 \in S_{\tau}(f_{0})$ and $a_2 \in S_{\upsilon}(f_{0})$ exist such as $r(a_1, D_{J_m})- r(a_2, D_{J_m}) = \tau- \upsilon$, for some $\tau, \upsilon\in \{1, 2, \ldots, \frac{m+3}{2}\}$ and $\tau\neq \upsilon$. Finally, the set $D_{J_m} = \{c_{0}, c_{\frac{m-3}{2}}, f_{\frac{m-1}{2}}, g_{0}\}$ is the MDRS. As a result, Lemma 2.4 holds true. □

The combination of Lemmas 2.3 and 2.4 yields the following main theorem:

Theorem 2.5. Let $J_m$ be the flower snark, then for $m\geq 6$,

3.   Double metric dimension for the quasi-flower snarks $G_{m}$

In this section, we will concentrate on determining the DMD of quasi-flower snarks $G_{m}$.

Figure 2 demonstrates the network of quasi-flower snark $G_{m}$, which has $4m$ vertices and $6m$ edges. The vertex set for the quasi-flower snarks is $V_{G_{m}}$ = $\{c_{\tau}, f_{\tau}, g_{\tau}, h_{\tau}$: $\forall$ $0\leq \tau\leq m-1\}$, and the edge set is $E_{G_{m}}$ = $\{c_{\tau}c_{\tau+1}, c_{\tau}f_{\tau}, f_{\tau}g_{\tau}, f_{\tau}h_{\tau}, g_{\tau}g_{\tau+1}, h_{\tau}h_{\tau+1}$: $\forall$ $0\leq \tau\leq m-2\}$ $\bigcup$ $\{c_{m-1}c_{0}, c_{m-1}f_{m-1}, f_{m-1}g_{m-1}, f_{m-1}h_{m-1}, g_{m-1}g_{0}, h_{m-1}h_{0}\}$.

As shown in Figure 2, the inner cycle vertices are labeled as $\{c_\tau$ : $\forall$ $0\leq \tau\leq m-1\}$, the set of central vertices are labeled as $\{f_\tau$ : $\forall$ $0\leq \tau\leq m-1\}$, and the outer cycle vertices are labeled as $\{g_\tau$ : $\forall$ $0\leq \tau\leq m-1\}$ $\bigcup$ $\{h_\tau$ : $\forall$ $0\leq \tau\leq m-1\}$.

MDRSs for $G_{m}$ are to be found in this section. It follows from Theorem 1.4 that

for all $m\geq 6$. We shall also show that $\psi(G_{m}) = 4$, for all $m\geq 6$.

Define the vertex subset $S_{\tau}(f_{0}) = \{g\in V_{G_{m}}: d(f_{0}, g) = \tau\} \subseteq V_{G_{m}}$ having distance $\tau$ from $f_{0}$. The Table 6 is a simple formulation for $S_{\tau}(f_{0})$ and will be used to compute the distances between each pair of vertices in $V_{G_{m}}$.

The following facts can be demonstrated as a result of the symmetry of $G_{m}$, where $m\geq 6$:

$d(f_{\tau}, g_{\upsilon}) = d(f_{\tau}, h_{\upsilon}) = d(f_{0}, g_{|\tau-\upsilon|})$ if $0\leq |\tau-\upsilon|\leq m-1;$

$d(c_{\tau}, c_{\upsilon}) = d(f_{0}, c_{|\tau-\upsilon|})-1$ if $0\leq |\tau-\upsilon|\leq m-1;$

$d(c_{\tau}, f_{\upsilon}) = d(f_{0}, c_{|\tau-\upsilon|})$ if $0\leq |\tau-\upsilon|\leq m-1;$

$d(c_{\tau}, g_{\upsilon}) = d(c_{\tau}, h_{\upsilon}) = d(f_{0}, c_{|\tau-\upsilon|})+1$ if $0\leq |\tau-\upsilon|\leq m-1;$

$d(g_{\tau}, h_{\upsilon}) = d(f_{0}, c_{|\tau-\upsilon|})+1$ if $0\leq |\tau-\upsilon|\leq m-1;$

$d(f_{\tau}, f_{\upsilon}) = d(f_{0}, f_{|\tau-\upsilon|})$ if $0\leq |\tau-\upsilon|\leq m-1;$

$d(g_{\tau}, g_{\upsilon}) = d(h_{\tau}, h_{\upsilon}) = d(f_{0}, g_{|\tau-\upsilon|})-1$ if $0\leq |\tau-\upsilon|\leq m-1.$

Therefore, we can recalculate the distances between each pair of vertices in $V_{G_{m}}$ if $d(f_{0}, g)$ is known for each $g\in V_{G_{m}}$.

Lemma 3.1. For any positive integer $m\geq 6$, $\psi\big(G_{m}\big) > 3$.

Proof. To prove the DMD $\psi\big(G_{m}\big) > 3$, we must show that every subset $D_{G_{m}}\subseteq V_{G_{m}}$ of cardinality 3 is not a DRS for $G_{m}$. Table 7 demonstrates the non-doubly resolved pairs of vertices from the set $V_{G_{m}}$ as well as all possible forms of subset $D_{G_{m}}$. Let us compute that any two vertices of the set $\{c_{\tau}, c_{\upsilon}, f_{0}; 0\leq \tau < \upsilon\leq m-1\}$ do not doubly resolve the vertices $f_{0}, g_{0}$. For example, it is clear that $d(f_{0}, f_{0}) = 0, d(f_{0}, g_{0}) = 1$. Now, for $0\leq \tau\leq \frac{m}{2}, 1\leq \upsilon\leq \frac{m}{2}$, we have

● $d(c_{\tau}, f_{0}) = d(f_{0}, c_{\tau}) = \tau+1;$

● $d(c_{\tau}, g_{0}) = d(f_{0}, c_{\tau})+1 = \tau+2;$

● $d(c_{\upsilon}, f_{0}) = d(f_{0}, c_{\upsilon}) = \upsilon+1;$

● $d(c_{\upsilon}, g_{0}) = d(f_{0}, c_{\upsilon})+1 = \upsilon+2.$

Also, for $\frac{m+2}{2}\leq \tau\leq m-2, \frac{m+2}{2}\leq \upsilon\leq m-1$, we have

● $d(c_{\tau}, f_{0}) = d(f_{0}, c_{\tau}) = m-\tau+1;$

● $d(c_{\tau}, g_{0}) = d(f_{0}, c_{\tau})+1 = m-\tau+2;$

● $d(c_{\upsilon}, f_{0}) = d(f_{0}, c_{\upsilon}) = m-\upsilon+1;$

● $d(c_{\upsilon}, g_{0}) = d(f_{0}, c_{\upsilon})+1 = m-\upsilon+2.$

So, $d(c_{\tau}, f_{0})- d(c_{\tau}, g_{0}) = d(c_{\upsilon}, f_{0})- d(c_{\upsilon}, g_{0}) = d(f_{0}, f_{0})- d(f_{0}, g_{0}) = -1,$ that is, the set $\{c_{\tau}, c_{\upsilon}, f_{0}; 0\leq \tau < \upsilon\leq m-1\}$ is not a DRS of $G_{m}$. Accordingly, we can investigate all the possible types of subset $D_{G_{m}}$ shown in Table 7 and verify their associated non-doubly resolved pairs of vertices. □

Lemma 3.2. $\psi\big(G_{m}\big) = 4, \forall$ even integers $m\geq 6$.

Proof. To demonstrate that $\psi\big(G_{m}\big) = 4$, where $m\geq 6$ is an even integer, it is enough to find a DRS of order 4. Now, by using the sets $S_{\tau}(f_{0})$ from Table 6, the metric coordinate vectors are demonstrated in Table 8 for every vertex of $G_{m}$ with respect to the set $D_{G_{m}} = \{c_{0}, c_{\frac{m}{2}}, f_{1}, g_{\frac{m+2}{2}}\}$.

Now, consider Table 8, where the vector of $f_{0}\in S_{\tau}(f_{0})$ has its first metric coordinate equal to 1. We may also check that no two vertices $b_1, b_2 \in S_{\tau}(f_{0})$ exist such as $r(b_1, D_{G_{m}})- r(b_2, D_{G_{m}}) = 0I$, where $I$ is the unit vector and $\tau\in \{1, 2, \ldots, \frac{m+4}{2}\}$. Furthermore, no two vertices $b_1 \in S_{\tau}(f_{0})$ and $b_2 \in S_{\upsilon}(f_{0})$ exist such as $r(b_1, D_{G_{m}})- r(b_2, D_{G_{m}}) = \tau- \upsilon$, for some $\tau, \upsilon\in \{1, 2, \ldots, \frac{m+4}{2}\}$ and $\tau\neq \upsilon$. Finally, the set $D_{G_{m}} = \{c_{0}, c_{\frac{m}{2}}, f_{1}, g_{\frac{m+2}{2}}\}$ is the MDRS. As a result, Lemma 3.2 holds true. □

Lemma 3.3. $\psi\big(G_{m}\big) = 4, \forall$ odd integers $m\geq 6$.

Proof. To demonstrate that $\psi\big(G_{m}\big) = 4$, where $m\geq 6$ is an odd integer, it is enough to find a DRS of order 4. Now, by using the sets $S_{\tau}(f_{0})$ from Table 6, the metric coordinate vectors are demonstrated in Table 9 for every vertex of $G_{m}$ with respect to the set $D_{G_{m}} = \{c_{0}, c_{\frac{m-3}{2}}, f_{\frac{m-1}{2}}, g_{0}\}$.

Now, consider Table 9, where the vector of $f_{0}\in S_{\tau}(f_{0})$ has its first metric coordinate equal to 1. We may also check that no two vertices $b_1, b_2 \in S_{\tau}(f_{0})$ exist such as $r(b_1, D_{G_{m}})- r(b_2, D_{G_{m}}) = 0I$, where $I$ denotes the unit vector and $\tau \in \{1, 2, \ldots, \frac{m+3}{2}\}$. Furthermore, no two vertices $b_1 \in S_{\tau}(f_{0})$ and $b_2 \in S_{\upsilon}(f_{0})$ exist such as $r(b_1, D_{G_{m}})- r(b_2, D_{G_{m}}) = \tau- \upsilon$, for some $\tau, \upsilon\in \{1, 2, \ldots, \frac{m+3}{2}\}$ and $\tau\neq \upsilon$. Finally, the set $D_{G_{m}} = \{c_{0}, c_{\frac{m-3}{2}}, f_{\frac{m-1}{2}}, g_{0}\}$ is the MDRS. As a result, Lemma 3.3 holds true. □

The combination of Lemmas 3.2 and 3.3 yields the following main theorem:

Theorem 3.4. Let $G_{m}$ be the quasi-flower snark for $m\geq 6.$ Then, $\psi(G_{m}) = 4.$

4.   Application

DRSs have recently been employed to find the origin of epidemics in several complex networks, including social networks, human epidemics, the cause of a disease outbreak, etc. (see ^[51,52]). To get the best possible detection of an epidemic source, we specifically take into account a network that uses DRSs to lower the number of observers.

Assume a social network set up as a flower snark network $J_{5}$, where the node set $V_{J_{5}}$ = $\{c_{\tau}, f_{\tau}, g_{\tau}, h_{\tau}$: $\forall$ $0\leq \tau\leq 4\}$ stands in for the individuals and the edge set $E_{J_{5}}$ = $\{c_{\tau}c_{\tau+1}, c_{\tau}f_{\tau}, f_{\tau}g_{\tau}, f_{\tau}h_{\tau}, g_{\tau}g_{\tau+1}, h_{\tau}h_{\tau+1}, g_{0}h_{n-1}, g_{n-1}h_{0}$: $\forall$ $0\leq \tau\leq 4\}$ between the nodes stands in for the connections between the individuals. An immediate solution can be found when observers are placed throughout the network, and the inter-node distances are reliable and well-known. However, the entire process would be very costly and time-consuming.

Then, what number of observers is necessary to account for epidemic sources with an unknown starting time and node-to-node transmission delays? Each node has a unique representation depending upon the minimum distance from the observer nodes. We employed the MDRS $D_{J_{5}} = \{c_{0}, c_{1}, f_{2}, g_{0}\}$ of the flower snark network $J_{5}$ to reduce the number of observers.

We only placed the observers on the nodes $c_{0}, c_{1}, f_{2}, g_{0}$ by applying Lemma 2.4 and Theorem 2.5. It is clear from Table 5 and Figure 3 that each node has a unique representation and the epidemic propagation will be optimal by placing observers at the nodes $c_{0}, c_{1}, f_{2}, g_{0}$. This hypothetical situation clarifies how MDRSs can be used to solve source localization issues.

Moreover, the DRSs are valuable for identifying faults in communication networks, assisting administrators in promptly locating and repairing issues for reliable operations. Additionally, they are beneficial in cybersecurity to detect and localize cyberattacks, allowing for quick responses to breaches. In environmental monitoring, DRSs aid in identifying sources of pollution, facilitating swift actions to address environmental hazards. The findings of this study provide a fundamental understanding of DRSs and their potential to enhance source detection in various real-world scenarios.

5.   Conclusions

In this article, the DMD for the flower snarks $J_{m}$ and quasi-flower snarks $G_{m}$ is computed by describing their MDRSs. We conclude that the DMD for the flower snarks $J_{m}$ is finite and depends upon the order of the network. Also, the DMD for the quasi-flower snarks $G_{m}$ is finite and free from the order of the network. An algorithm is created to calculate the MDRSs and DMD of a network with the help of Matlab or any other simulation tool. Further, an application of the work done in the context of source localization is also provided. It is also clearly observed that computing MDRSs for a network is an NP-hard problem (see ^[35]), which explains the limitations of computing this parameter and the importance of the obtained results. Exploring future directions for DRSs in various families of networks can help in the development of combinatorial designs, error-correcting codes, network analysis, and optimization problems, among other fields. Following are a few points that address the limitations of the study:

● Constructing DRSs with desirable properties can be a challenging task.

● The problem of finding MDRSs is known to be NP-hard, which means that there is no known efficient algorithm to solve it for all cases.

● As a result, finding optimal DRSs can require significant computational effort.

In conclusion, DRSs have limitations in terms of size, optimality, ambiguity, construction difficulty, practical implementation, and generalization to various problem domains. These restrictions emphasize the importance of carefully taking into account the particular problem requirements and limits and illustrate the difficulties and complexities involved with using DRSs in different scenarios.

Open Problem 5.1. Investigate the DRSs for the power paths $P^r_n$ for all integers $r$, and $n$, where $r < \frac{n}{2}$.

Author contributions

Muhammad Ahmad was an engaged participant in initiating the problem, and ensuring the validation of results. Muhammad Faheem contributed to the methodology and conducting the final review. Sanaa A. Bajri played a crucial role in analyzing and computing the results, as well as initiating the drafting process of the study. Zohaib Zahid played a pivotal role in problem discussion, gathering essential data, and providing continuous supervision. Muhammad Javaid participated in characterizing and calculating the results and assisted with software in drafting the study. Hamiden Abd El-Wahed Khalifa contributed to the discussing the problem, and meticulously proofread the final version. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research is funded by Princess Nourah bint Abdulrahman University Researchers Supporting Project number (PNURSP2024R527), Princess Nourah bint Abdulrahman University, Riyadh, Saudi Arabia.

Conflict of interest

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.