
Patients with lesions in the posterior cingulate gyrus (PCG), including the retrosplenial cortex (RSC) and posterior cingulate cortex (PCC), cannot navigate in familiar environments, nor draw routes on a 2D map of the familiar environments. This suggests that the topographical knowledge of the environments (i.e., cognitive map) to find the right route to a goal is represented in the PCG, and the patients lack such knowledge. However, theoretical backgrounds in neuronal levels for these symptoms in primates are unclear. Recent behavioral studies suggest that human spatial knowledge is constructed based on a labeled graph that consists of topological connections (edges) between places (nodes), where local metric information, such as distances between nodes (edge weights) and angles between edges (node labels), are incorporated. We hypothesize that the population neural activity in the PCG may represent such knowledge based on a labeled graph to encode routes in both 3D environments and 2D maps. Since no previous data are available to test the hypothesis, we recorded PCG neuronal activity from a monkey during performance of virtual navigation and map drawing-like tasks. The results indicated that most PCG neurons responded differentially to spatial parameters of the environments, including the place, head direction, and reward delivery at specific reward areas. The labeled graph-based analyses of the data suggest that the population activity of the PCG neurons represents the distance traveled, locations, movement direction, and navigation routes in the 3D and 2D virtual environments. These results support the hypothesis and provide a neuronal basis for the labeled graph-based representation of a familiar environment, consistent with PCG functions inferred from the human clinicopathological studies.
Citation: Yang Yu, Tsuyoshi Setogawa, Jumpei Matsumoto, Hiroshi Nishimaru, Hisao Nishijo. Neural basis of topographical disorientation in the primate posterior cingulate gyrus based on a labeled graph[J]. AIMS Neuroscience, 2022, 9(3): 373-394. doi: 10.3934/Neuroscience.2022021
[1] | Ahmed Alamer, Hassan Zafar, Muhammad Javaid . Study of modified prism networks via fractional metric dimension. AIMS Mathematics, 2023, 8(5): 10864-10886. doi: 10.3934/math.2023551 |
[2] | Fozia Bashir Farooq, Furqan Ahmad, Muhammad Kamran Jamil, Aisha Javed, Nouf Abdulrahman Alqahtani . Uniquely identifying vertices and edges of a heptagonal snake graph using distance formulas. AIMS Mathematics, 2025, 10(6): 15069-15087. doi: 10.3934/math.2025676 |
[3] | Bana Al Subaiei, Ahlam AlMulhim, Abolape Deborah Akwu . Vertex-edge perfect Roman domination number. AIMS Mathematics, 2023, 8(9): 21472-21483. doi: 10.3934/math.20231094 |
[4] | Ali N. A. Koam . Metric based resolvability of cycle related graphs. AIMS Mathematics, 2024, 9(4): 9911-9925. doi: 10.3934/math.2024485 |
[5] | Dalal Awadh Alrowaili, Uzma Ahmad, Saira Hameeed, Muhammad Javaid . Graphs with mixed metric dimension three and related algorithms. AIMS Mathematics, 2023, 8(7): 16708-16723. doi: 10.3934/math.2023854 |
[6] | Maryam Salem Alatawi, Ali Ahmad, Ali N. A. Koam, Sadia Husain, Muhammad Azeem . Computing vertex resolvability of benzenoid tripod structure. AIMS Mathematics, 2022, 7(4): 6971-6983. doi: 10.3934/math.2022387 |
[7] | Syed Ahtsham Ul Haq Bokhary, Zill-e-Shams, Abdul Ghaffar, Kottakkaran Sooppy Nisar . On the metric basis in wheels with consecutive missing spokes. AIMS Mathematics, 2020, 5(6): 6221-6232. doi: 10.3934/math.2020400 |
[8] | Ali N. A. Koam, Sikander Ali, Ali Ahmad, Muhammad Azeem, Muhammad Kamran Jamil . Resolving set and exchange property in nanotube. AIMS Mathematics, 2023, 8(9): 20305-20323. doi: 10.3934/math.20231035 |
[9] | Chenggang Huo, Humera Bashir, Zohaib Zahid, Yu Ming Chu . On the 2-metric resolvability of graphs. AIMS Mathematics, 2020, 5(6): 6609-6619. doi: 10.3934/math.2020425 |
[10] | Mohra Zayed, Ali Ahmad, Muhammad Faisal Nadeem, Muhammad Azeem . The comparative study of resolving parameters for a family of ladder networks. AIMS Mathematics, 2022, 7(9): 16569-16589. doi: 10.3934/math.2022908 |
Patients with lesions in the posterior cingulate gyrus (PCG), including the retrosplenial cortex (RSC) and posterior cingulate cortex (PCC), cannot navigate in familiar environments, nor draw routes on a 2D map of the familiar environments. This suggests that the topographical knowledge of the environments (i.e., cognitive map) to find the right route to a goal is represented in the PCG, and the patients lack such knowledge. However, theoretical backgrounds in neuronal levels for these symptoms in primates are unclear. Recent behavioral studies suggest that human spatial knowledge is constructed based on a labeled graph that consists of topological connections (edges) between places (nodes), where local metric information, such as distances between nodes (edge weights) and angles between edges (node labels), are incorporated. We hypothesize that the population neural activity in the PCG may represent such knowledge based on a labeled graph to encode routes in both 3D environments and 2D maps. Since no previous data are available to test the hypothesis, we recorded PCG neuronal activity from a monkey during performance of virtual navigation and map drawing-like tasks. The results indicated that most PCG neurons responded differentially to spatial parameters of the environments, including the place, head direction, and reward delivery at specific reward areas. The labeled graph-based analyses of the data suggest that the population activity of the PCG neurons represents the distance traveled, locations, movement direction, and navigation routes in the 3D and 2D virtual environments. These results support the hypothesis and provide a neuronal basis for the labeled graph-based representation of a familiar environment, consistent with PCG functions inferred from the human clinicopathological studies.
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 EG and vertex set VG. For a vertex ν∈VG, the representation (l-tuple) r(ν)=(dτ|1≤τ≤l), where dτ=dτ(ν,ντ), is said to be the distance vector of the vertex ν. The distance vector between two vertices ν≠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∈VG determines (resolves) the vertices v,w∈VG if d(v,x)≠d(w,x).
2) Let WG⊆VG, where WG={yτ|1≤τ≤l};(l≤n) is an ordered set and z∈VG, then the notation r(z|WG) is the distance vector of the vertex z in association with WG is the l-tuple (d(z,yτ))lτ=1, also called the vector of metric coordinates.
3) The set WG is said to be a resolving set for network G, if the l-tuple (d(z,yτ))lτ=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 e1,e2∈G (where |G|≥2) are said to doubly resolve the vertices f1,f2 of network G if d(e1,f1)−d(e1,f2)≠d(e2,f1)−d(e2,f2).
2) An ordered set DG={eτ|1≤τ≤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 DG.
3) In other words, all coordinates of the vector r(f1|DG)−r(f2|DG) cannot be the same for any pair of distinct vertices f1,f2∈VG. i.e. r(f1|DG)−r(f2|DG)≠γI, where I is the unit vector (1,1,…,1) and γ 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 ψ(G). Moreover, a DRS is a resolving set as well, and ψ(G)≤dim(G). It was shown in [35] (and, respectively, in [6]) that finding ψ(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 ψ(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 Jm and quasi-flower snarks Gm were determined by Imran et al. [53] and Naeem et al. [54] and are given in the following theorems:
Theorem 1.3. [53] Let Jm be the flower snark. Then, for every odd positive integer m≥5, we have dim(Jm)=3.
Theorem 1.4. [54] Let Gm be the quasi-flower snark. Then, for every positive integer m≥4, we have dim(Gm)={3,if m is odd≤4,otherwise.
The results presented above determine the lower bound on the DMD of flower snarks Jm and quasi-flower snarks Gm. Following is how the main contribution of the article is structured:
● We compute the DMD for flower snarks Jm and quasi-flower snarks Gm 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.
In this section, we will concentrate on determining the DMD of flower snarks Jm.
The flower snark Jm, depicted in Figure 1, is a cubic network comprising 4m vertices and 6m edges. The vertex set for the flower snarks Jm is VJm = {cτ,fτ,gτ,hτ: ∀ 0≤τ≤m−1}, and the edge set is EJm = {cτcτ+1,cτfτ,fτgτ,fτhτ,gτgτ+1,hτhτ+1: ∀ 0≤τ≤m−2}⋃ {cm−1c0,cm−1fm−1,fm−1gm−1,fm−1hm−1,gm−1g0,hm−1h0,g0hm−1,gm−1h0}.
As shown in Figure 1, the inner cycle vertices are labeled as {cτ : ∀ 0≤τ≤m−1}, the set of central vertices are labeled as {fτ : ∀ 0≤τ≤m−1}, and the outer cycle vertices are labeled as {gτ : ∀ 0≤τ≤m−1} ⋃ {hτ : ∀ 0≤τ≤m−1}.
MDRSs for Jm are to be found in this section. It follows from Theorem 1.3 that ψ(Jm)≥3, for all m≥6. We shall also show, for all m≥6:
ψ(Jm)={4,if m is odd;5,if m is even. |
Define the vertex subset Sτ(f0)={g∈VJm:d(f0,g)=τ}⊆VJm having distance τ from f0. The Table 1 is a simple formulation for Sτ(f0) and will be used to compute the distances between each pair of vertices in VJm.
m | τ | Sτ(f0) |
1 | {c0, g0, h0} | |
2 | {c1, cm−1, g1, gm−1, h1, hm−1} | |
3≤τ≤⌊m2⌋ | {cτ−1, cm−τ+1, fτ−2, fm−τ+2, gτ−1, gm−τ+1, hτ−1, hm−τ+1} | |
even | m+22 | {cm2, fm−22, fm+22, gm2, hm2} |
m+42 | {fm2} | |
odd | m+12 | {cm−12, cm+12, fm−32, fm+32, gm−12, gm+12, hm−12, hm+12} |
m+32 | {fm−12, fm+12} |
The following facts can be demonstrated as a result of the symmetry of Jm, where m≥6:
d(fτ,fυ)=d(f0,f|τ−υ|) if 0≤|τ−υ|≤m−1; d(cτ,cυ)=d(f0,c|τ−υ|)−1 if 0≤|τ−υ|≤m−1;
d(cτ,fυ)=d(f0,c|τ−υ|) if 0≤|τ−υ|≤m−1;
d(cτ,gυ)=d(cτ,hυ)=d(f0,c|τ−υ|)+1 if 0≤|τ−υ|≤m−1;
d(fτ,gυ)=d(fτ,hυ)=d(f0,g|τ−υ|) if 0≤|τ−υ|≤m−1.
If m is an odd integer, then
d(gτ,hυ)={d(f0,c|τ−υ|)+1,if 0≤|τ−υ|≤m−12;d(f0,c|τ−υ|)−1,if m+12≤|τ−υ|≤m−1.d(gτ,gυ)=d(hτ,hυ)={d(f0,g|τ−υ|)−1,if 0≤|τ−υ|≤m−12;d(f0,g|τ−υ|)+1,if m+12≤|τ−υ|≤m−1. |
If m is an even integer, then
d(gτ,hυ)={d(f0,c|τ−υ|)+1,if 0≤|τ−υ|≤m−22;d(f0,c|τ−υ|)−1,if m2≤|τ−υ|≤m−1.d(gτ,gυ)=d(hτ,hυ)={d(f0,g|τ−υ|)−1,if 0≤|τ−υ|≤m2;d(f0,g|τ−υ|)+1,if m+22≤|τ−υ|≤m−1. |
Therefore, we can recalculate the distances between each pair of vertices in VJm if d(f0,g) is known for each g∈VJm.
Lemma 2.1. For any even positive integer m≥6, ψ(Jm)>4.
Proof. To prove the DMD ψ(Jm)>4, we must show that every subset DJm⊆VJm of cardinality 4 is not a DRS for Jm. Table 2 demonstrates the non-doubly resolved pairs of vertices from the set VJm as well as all possible forms of subset DJm. Let us compute that any two vertices of the set {cτ,cυ,cω,f0;0≤τ<υ<ω≤m−1} do not doubly resolve the vertices f0,g0. For example, it is clear that d(f0,f0)=0,d(f0,g0)=1. Now, for 0≤τ≤m−22,1≤υ≤m−22,2≤ω≤m−22, we have
DJm | Non-doubly resolved pairs |
{cτ,cυ,cω,f0}, 0≤τ<υ<ω≤m−1 | {f0,g0} |
{cτ,cυ,f0,fω}, 0≤τ<υ≤m−1, 1≤ω≤m−1 | {g0,h0} |
{cτ,f0,fυ,fω}, 0≤τ≤m−1, 1≤υ<ω≤m−1 | {g0,h0} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, 0≤ω≤m−22 | {gm+2ω2,hm+2ω2} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, ω=m−1 | {gm−22,hm−22} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, 0≤ω≤m−22 | {f0,h0} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, ω=m−1 | {f0,g0} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, 0≤ω≤m−22 | {f0,g0} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, ω=m−1 | {f0,h0} |
{f0,fτ,fυ,fω}, 1≤τ<υ<ω≤m−1 | {c0,g0} |
{f0,gτ,gυ,hω}, 0≤τ<υ≤m−1, 0≤ω≤m−1 | {c0,f0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, 0≤ω≤m−22 | {c0,h0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, ω=m2 | {g0,h0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, m+22≤ω≤m−1 | {c0,g0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, 0≤ω≤m−22 | {c0,g0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, ω=m2 | {g0,h0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, m+22≤ω≤m−1 | {c0,h0} |
{f0,gτ,gυ,gω} ⋃ {f0,hτ,hυ,hω}, 0≤τ<υ<ω≤m−1 | {c0,f0} |
{f0,gτ,hυ,hω}, 0≤τ≤m−1, 0≤υ<ω≤m−1 | {c0,f0} |
● d(cτ,f0)=d(f0,cτ)=τ+1,
● d(cτ,g0)=d(f0,cτ)+1=τ+2,
● d(cυ,f0)=d(f0,cυ)=υ+1,
● d(cυ,g0)=d(f0,cυ)+1=υ+2,
● d(cω,f0)=d(f0,cω)=ω+1,
● d(cω,g0)=d(f0,cω)+1=ω+2.
Also, for m2≤τ≤m−3,m2≤υ≤m−2,m2≤ω≤m−1, we have
● d(cτ,f0)=d(f0,cτ)=m−τ+1,
● d(cτ,g0)=d(f0,cτ)+1=m−τ+2,
● d(cυ,f0)=d(f0,cυ)=m−υ+1,
● d(cυ,g0)=d(f0,cυ)+1=m−υ+2,
● d(cω,f0)=d(f0,cω)=m−ω+1,
● d(cω,g0)=d(f0,cω)+1=m−ω+2.
So, d(cτ,f0)−d(cτ,g0)=d(cυ,f0)−d(cυ,g0)=d(cω,f0)−d(cω,g0)=d(f0,f0)−d(f0,g0)=−1, that is, the set {cτ,cυ,cω,f0;0≤τ<υ<ω≤m−1} is not a DRS of Jm. Accordingly, we can investigate all the possible types of subset DJm shown in Table 2 and verify their associated non-doubly resolved pairs of vertices.
Lemma 2.2. For any odd positive integer m≥6, ψ(Jm)>3.
Proof. To prove the DMD ψ(Jm)>3, we must show that every subset DJm⊆VJm of cardinality 3 is not a DRS for Jm. Table 3 demonstrates the non-doubly resolved pairs of vertices from the set VJm as well as all possible forms of subset DJm. Let us compute that any two vertices of the set {f0,gτ,hυ;0≤τ,υ≤m−1} do not doubly resolve the vertices c0,f0. For example, it is clear that d(c0,f0)=1,d(f0,f0)=0. Now, for 0≤τ,υ≤m−12, we have
DJm | Non-doubly resolved pairs |
{cτ,cυ,f0}, 0≤τ<υ≤m−1 | {f0,g0} |
{cτ,f0,fυ}, 0≤τ≤m−1, 1≤υ≤m−1 | {g0,h0} |
{f0,fτ,fυ}, 1≤τ<υ≤m−1 | {c0,g0} |
{f0,fτ,gυ}, 1≤τ≤m−1, 0≤υ≤m−32 | {c0,h0} |
{f0,fτ,gυ}, 1≤τ≤m−1, m−12≤υ≤m−1 | {cυ−1,hυ−1} |
{f0,fτ,hυ}, 1≤τ≤m−1, 0≤υ≤m−32 | {c0,g0} |
{f0,fτ,hυ}, 1≤τ≤m−1, m−12≤υ≤m−1 | {cυ−1,gυ−1} |
{f0,gτ,gυ} ⋃ {f0,hτ,hυ}, 0≤τ<υ≤m−1 | {c0,f0} |
{f0,gτ,hυ}, 0≤τ,υ≤m−1 | {c0,f0} |
● d(c0,gτ)=d(f0,cτ)+1=τ+2,
● d(f0,gτ)=d(f0,gτ)=τ+1,
● d(c0,hυ)=d(f0,cυ)+1=υ+2,
● d(f0,hυ)=d(f0,gυ)=υ+1.
Also, for m+12≤τ,υ≤m−1, we have
● d(c0,gτ)=d(f0,cτ)+1=m−τ+2,
● d(f0,gτ)=d(f0,gτ)=m−τ+1,
● d(c0,hυ)=d(f0,cυ)+1=m−υ+2,
● d(f0,hυ)=d(f0,gυ)=m−υ+1.
So, d(c0,gτ)−d(f0,gτ)=d(c0,hυ)−d(f0,hυ)=d(c0,f0)−d(f0,f0)=1, that is, the set {f0,gτ,hυ;0≤τ,υ≤m−1} is not a DRS of Jm. Accordingly, we can investigate all the possible types of subset DJm shown in Table 3 and verify their associated non-doubly resolved pairs of vertices.
Lemma 2.3. ψ(Jm)=5,∀ even integers m≥6.
Proof. It suffices to identify a DRS having order 5 to demonstrate that ψ(Jm)=5, if m≥6 is an even integer. Now, by using the sets Sτ(f0) from Table 1, the metric coordinate vectors are demonstrated in Table 4 for each vertex of Jm with respect to the set DJm={c0,c1,cm2,g0,gm−1}.
τ | Sτ(f0) | DJm={c0,c1,cm2,g0,gm−1} |
0 | f0 | (1,2,m+22,1,2) |
1 | c0 | (0,1,m2,2,3) |
g0 | (2,3,m+42,0,3) | |
h0 | (2,3,m+42,2,1) | |
2 | c1 | (1,0,m−22,3,4) |
cm−1 | (1,2,m−22,3,2) | |
g1 | (3,2,m+22,1,4) | |
gm−1 | (3,4,m+22,3,0) | |
h1 | (3,2,m+22,3,2) | |
hm−1 | (3,4,m+22,1,2) | |
3≤τ≤m2 | cτ−1 | (τ−1,τ−2,m−2τ+22,τ+1,τ+2) |
cm−τ+1 | (τ−1,τ,m−2τ+22,τ+1,τ) | |
fτ−2 | (τ−1,τ−2,m−2τ+62,τ−1,τ) | |
fm−τ+2 | ={(τ+1,τ,m−2τ+62,τ−1,τ+2), if τ<m2;(m+22,m2,3,m−22,m2), if τ=m2. | |
gm−τ+1 | (τ+1,τ+2,m−2τ+62,τ+1,τ−2) | |
hτ−1 | (τ+1,τ,m−2τ+62,τ+1,τ) | |
hm−τ+1 | (τ+1,τ+2,m−2τ+62,τ−1,τ) | |
m+22 | cm2 | (m2,m−22,0,m+42,m+22) |
fm−22 | (m2,m−22,2,m2,m+22) | |
fm+22 | (m2,m+22,2,m2,m−22) | |
gm2 | (m+42,m+22,2,m2,m−22) | |
hm2 | (m+42,m+22,2,m2,m+22) | |
m+42 | fm2 | (m+22,m2,1,m+22,m2) |
Now, consider Table 4, where the vector of f0∈Sτ(f0) has its first metric coordinate equal to 1. We may also check that no two vertices a1,a2∈Sτ(f0) exist such as r(a1,DJm)−r(a2,DJm)=0I, where I is the unit vector and τ∈{1,2,…,m+42}. Furthermore, no two vertices a1∈Sτ(f0) and a2∈Sυ(f0) exist such as r(a1,DJm)−r(a2,DJm)=τ−υ, for some τ,υ∈{1,2,…,m+42} and τ≠υ. Finally, the set DJm={c0,c1,cm2,g0,gm−1} is the MDRS. As a result, Lemma 2.3 holds true.
Lemma 2.4. ψ(Jm)=4,∀ odd integers m≥6.
Proof. To demonstrate that ψ(Jm)=4, where m≥6 is an odd integer, it is enough to find a DRS of order 4. Now, by using the sets Sτ(f0) from Table 1, the metric coordinate vectors are demonstrated in Table 5 for each vertex of Jm with respect to the set DJm={c0,cm−32,fm−12,g0}.
τ | Sτ(f0) | DJm={c0,cm−32,fm−12,g0} |
0 | f0 | (1,m−12,m+32,1) |
1 | c0 | (0,m−32,m+12,2) |
g0 | (2,m+12,m+12,0) | |
h0 | (2,m+12,m+12,2) | |
2 | c1 | (1,m−52,m−12,3) |
cm−1 | (1,m−12,m+12,3) | |
g1 | (3,m−12,m−12,1) | |
gm−1 | (3,m+32,m+12,3) | |
h1 | (3,m−12,m−12,3) | |
hm−1 | (3,m+32,m+12,1) | |
3≤τ≤m−12 | cτ−1 | (τ−1,m−2τ−12,m−2τ+32,τ+1) |
cm−τ+1 | (τ−1,m−2τ+52,m−2τ+52,τ+1) | |
fτ−2 | (τ−1,m−2τ+32,m−2τ+72,τ−1) | |
fm−τ+2 | ={(2,m+12,m+32,2), if τ=3;(τ−1,m−2τ+92,m−2τ+92,τ−1), if τ>3. | |
gτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ−1) | |
gm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ+1) | |
hτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ+1) | |
hm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ−1) | |
m+12 | cm−12 | (m−12,1,1,m+32) |
cm+12 | (m−12,2,2,m+32) | |
fm−32 | (m−12,1,3,m−12) | |
fm+32 | (m−12,4,4,m−12) | |
gm−12 | (m+32,3,1,m−12) | |
gm+12 | (m+32,4,2,m+12) | |
hm−12 | (m+32,3,1,m+12) | |
hm+12 | (m+32,4,2,m−12) | |
m+32 | fm−12 | (m+12,2,0,m+12) |
fm+12 | (m+12,3,3,m+12) |
Now, consider Table 5, where the vector of f0∈Sτ(f0) has its first metric coordinate equal to 1. We may also check that no two vertices a1,a2∈Sτ(f0) exist such as r(a1,DJm)−r(a2,DJm)=0I, where I is the unit vector and τ∈{1,2,…,m+32}. Furthermore, no two vertices a1∈Sτ(f0) and a2∈Sυ(f0) exist such as r(a1,DJm)−r(a2,DJm)=τ−υ, for some τ,υ∈{1,2,…,m+32} and τ≠υ. Finally, the set DJm={c0,cm−32,fm−12,g0} 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 Jm be the flower snark, then for m≥6,
ψ(Jm)={4,if m is odd ;5,if m is even . |
In this section, we will concentrate on determining the DMD of quasi-flower snarks Gm.
Figure 2 demonstrates the network of quasi-flower snark Gm, which has 4m vertices and 6m edges. The vertex set for the quasi-flower snarks is VGm = {cτ,fτ,gτ,hτ: ∀ 0≤τ≤m−1}, and the edge set is EGm = {cτcτ+1,cτfτ,fτgτ,fτhτ,gτgτ+1,hτhτ+1: ∀ 0≤τ≤m−2} ⋃ {cm−1c0,cm−1fm−1,fm−1gm−1,fm−1hm−1,gm−1g0,hm−1h0}.
As shown in Figure 2, the inner cycle vertices are labeled as {cτ : ∀ 0≤τ≤m−1}, the set of central vertices are labeled as {fτ : ∀ 0≤τ≤m−1}, and the outer cycle vertices are labeled as {gτ : ∀ 0≤τ≤m−1} ⋃ {hτ : ∀ 0≤τ≤m−1}.
MDRSs for Gm are to be found in this section. It follows from Theorem 1.4 that
ψ(Gm)≥{3,if m is odd;≤4, otherwise, |
for all m≥6. We shall also show that ψ(Gm)=4, for all m≥6.
Define the vertex subset Sτ(f0)={g∈VGm:d(f0,g)=τ}⊆VGm having distance τ from f0. The Table 6 is a simple formulation for Sτ(f0) and will be used to compute the distances between each pair of vertices in VGm.
m | τ | Sτ(f0) |
1 | {c0, g0, h0} | |
2 | {c1, cm−1, g1, gm−1, h1, hm−1} | |
3≤τ≤⌊m2⌋ | {cτ−1, cm−τ+1, fτ−2, fm−τ+2, gτ−1, gm−τ+1, hτ−1, hm−τ+1} | |
even | m+22 | {cm2, fm−22, fm+22, gm2, hm2} |
m+42 | {fm2} | |
odd | m+12 | {cm−12, cm+12, fm−32, fm+32, gm−12, gm+12, hm−12, hm+12} |
m+32 | {fm−12, fm+12} |
The following facts can be demonstrated as a result of the symmetry of Gm, where m≥6:
d(fτ,gυ)=d(fτ,hυ)=d(f0,g|τ−υ|) if 0≤|τ−υ|≤m−1;
d(cτ,cυ)=d(f0,c|τ−υ|)−1 if 0≤|τ−υ|≤m−1;
d(cτ,fυ)=d(f0,c|τ−υ|) if 0≤|τ−υ|≤m−1;
d(cτ,gυ)=d(cτ,hυ)=d(f0,c|τ−υ|)+1 if 0≤|τ−υ|≤m−1;
d(gτ,hυ)=d(f0,c|τ−υ|)+1 if 0≤|τ−υ|≤m−1;
d(fτ,fυ)=d(f0,f|τ−υ|) if 0≤|τ−υ|≤m−1;
d(gτ,gυ)=d(hτ,hυ)=d(f0,g|τ−υ|)−1 if 0≤|τ−υ|≤m−1.
Therefore, we can recalculate the distances between each pair of vertices in VGm if d(f0,g) is known for each g∈VGm.
Lemma 3.1. For any positive integer m≥6, ψ(Gm)>3.
Proof. To prove the DMD ψ(Gm)>3, we must show that every subset DGm⊆VGm of cardinality 3 is not a DRS for Gm. Table 7 demonstrates the non-doubly resolved pairs of vertices from the set VGm as well as all possible forms of subset DGm. Let us compute that any two vertices of the set {cτ,cυ,f0;0≤τ<υ≤m−1} do not doubly resolve the vertices f0,g0. For example, it is clear that d(f0,f0)=0,d(f0,g0)=1. Now, for 0≤τ≤m2,1≤υ≤m2, we have
DGm | Non-doubly resolved pairs |
{cτ,cυ,f0}, 0≤τ<υ≤m−1 | {f0,g0} |
{cτ,f0,gυ}, 0≤τ,υ≤m−1 | {f0,h0} |
{cτ,f0,fυ}, 0≤τ≤m−1, 1≤υ≤m−1 | {g0,h0} |
{cτ,f0,hυ}, 0≤τ,υ≤m−1 | {f0,g0} |
{f0,fτ,gυ}, 1≤τ≤m−1, 0≤υ≤m−1 | {c0,h0} |
{f0,fτ,fυ}, 1≤τ<υ≤m−1 | {c0,g0} |
{f0,gτ,hυ}, 0≤τ,υ≤m−1 | {c0,f0} |
{f0,fτ,hυ}, 1≤τ≤m−1, 0≤υ≤m−1 | {c0,g0} |
{f0,hτ,hυ}, 0≤τ<υ≤m−1 | {f0,g0} |
{f0,gτ,gυ}, 0≤τ<υ≤m−1 | ={{c0,h0}, if m is even {c0,f0}, if m is odd |
● d(cτ,f0)=d(f0,cτ)=τ+1;
● d(cτ,g0)=d(f0,cτ)+1=τ+2;
● d(cυ,f0)=d(f0,cυ)=υ+1;
● d(cυ,g0)=d(f0,cυ)+1=υ+2.
Also, for m+22≤τ≤m−2,m+22≤υ≤m−1, we have
● d(cτ,f0)=d(f0,cτ)=m−τ+1;
● d(cτ,g0)=d(f0,cτ)+1=m−τ+2;
● d(cυ,f0)=d(f0,cυ)=m−υ+1;
● d(cυ,g0)=d(f0,cυ)+1=m−υ+2.
So, d(cτ,f0)−d(cτ,g0)=d(cυ,f0)−d(cυ,g0)=d(f0,f0)−d(f0,g0)=−1, that is, the set {cτ,cυ,f0;0≤τ<υ≤m−1} is not a DRS of Gm. Accordingly, we can investigate all the possible types of subset DGm shown in Table 7 and verify their associated non-doubly resolved pairs of vertices.
Lemma 3.2. ψ(Gm)=4,∀ even integers m≥6.
Proof. To demonstrate that ψ(Gm)=4, where m≥6 is an even integer, it is enough to find a DRS of order 4. Now, by using the sets Sτ(f0) from Table 6, the metric coordinate vectors are demonstrated in Table 8 for every vertex of Gm with respect to the set DGm={c0,cm2,f1,gm+22}.
τ | Sτ(f0) | DGm={c0,cm2,f1,gm+22} |
0 | f0 | (1,m+22,3,m2) |
1 | c0 | (0,m2,2,m+22) |
g0 | (2,m+42,2,m−22) | |
h0 | (2,m+42,2,m+22) | |
2 | c1 | (1,m−22,1,m+42) |
cm−1 | (1,m−22,3,m2) | |
g1 | (3,m+22,1,m2) | |
gm−1 | (3,m+22,3,m−42) | |
h1 | (3,m+22,1,m+42) | |
hm−1 | (3,m+22,3,m2) | |
3≤τ≤m2 | cτ−1 | (τ−1,m−2τ+22,τ−1,m−2τ+82) |
cm−τ+1 | (τ−1,m−2τ+22,τ+1,m−2τ+42) | |
fτ−2 | ={(2,m2,0,m+22), if τ=3;(τ−1,m−2τ+62,τ−1,m−2τ+82), if τ>3. | |
fm−τ+2 | (τ−1,m−2τ+62,τ+1,m−2τ+42) | |
gτ−1 | (τ+1,m−2τ+62,τ−1,m−2τ+42) | |
gm−τ+1 | (τ+1,m−2τ+62,τ+1,m−2τ2) | |
hτ−1 | (τ+1,m−2τ+62,τ−1,m−2τ+82) | |
hm−τ+1 | (τ+1,m−2τ+62,τ+1,m−2τ+42) | |
m+22 | cm2 | (m2,0,m2,3) |
fm−22 | (m2,2,m2,3) | |
fm+22 | (m2,2,m+42,1) | |
gm2 | (m+42,2,m2,1) | |
hm2 | (m+42,2,m2,3) | |
m+42 | fm2 | (m+22,1,m+22,2) |
Now, consider Table 8, where the vector of f0∈Sτ(f0) has its first metric coordinate equal to 1. We may also check that no two vertices b1,b2∈Sτ(f0) exist such as r(b1,DGm)−r(b2,DGm)=0I, where I is the unit vector and τ∈{1,2,…,m+42}. Furthermore, no two vertices b1∈Sτ(f0) and b2∈Sυ(f0) exist such as r(b1,DGm)−r(b2,DGm)=τ−υ, for some τ,υ∈{1,2,…,m+42} and τ≠υ. Finally, the set DGm={c0,cm2,f1,gm+22} is the MDRS. As a result, Lemma 3.2 holds true.
Lemma 3.3. ψ(Gm)=4,∀ odd integers m≥6.
Proof. To demonstrate that ψ(Gm)=4, where m≥6 is an odd integer, it is enough to find a DRS of order 4. Now, by using the sets Sτ(f0) from Table 6, the metric coordinate vectors are demonstrated in Table 9 for every vertex of Gm with respect to the set DGm={c0,cm−32,fm−12,g0}.
τ | Sτ(f0) | DGm={c0,cm−32,fm−12,g0} |
0 | f0 | (1,m−12,m+32,1) |
1 | c0 | (0,m−32,m+12,2) |
g0 | (2,m+12,m+12,0) | |
h0 | (2,m+12,m+12,2) | |
2 | c1 | (1,m−52,m−12,3) |
cm−1 | (1,m−12,m+12,3) | |
g1 | (3,m−12,m−12,1) | |
gm−1 | (3,m+32,m+12,1) | |
h1 | (3,m−12,m−12,3) | |
hm−1 | (3,m+32,m+12,3) | |
3≤τ≤m−12 | cτ−1 | (τ−1,m−2τ−12,m−2τ+32,τ+1) |
cm−τ+1 | (τ−1,m−2τ+52,m−2τ+52,τ+1) | |
fτ−2 | (τ−1,m−2τ+32,m−2τ+72,τ−1) | |
fm−τ+2 | ={(2,m+12,m+32,2), if τ=3;(τ−1,m−2τ+92,m−2τ+92,τ−1), if τ>3. | |
gτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ−1) | |
gm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ−1) | |
hτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ+1) | |
hm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ+1) | |
m+12 | cm−12 | (m−12,1,1,m+32) |
cm+12 | (m−12,2,2,m+32) | |
fm−32 | (m−12,1,3,m−12) | |
fm+32 | (m−12,4,4,m−12) | |
gm−12 | (m+32,3,1,m−12) | |
gm+12 | (m+32,4,2,m−12) | |
hm−12 | (m+32,3,1,m+32) | |
hm+12 | (m+32,4,2,m+32) | |
m+32 | fm−12 | (m+12,2,0,m+12) |
fm+12 | (m+12,3,3,m+12) |
Now, consider Table 9, where the vector of f0∈Sτ(f0) has its first metric coordinate equal to 1. We may also check that no two vertices b1,b2∈Sτ(f0) exist such as r(b1,DGm)−r(b2,DGm)=0I, where I denotes the unit vector and τ∈{1,2,…,m+32}. Furthermore, no two vertices b1∈Sτ(f0) and b2∈Sυ(f0) exist such as r(b1,DGm)−r(b2,DGm)=τ−υ, for some τ,υ∈{1,2,…,m+32} and τ≠υ. Finally, the set DGm={c0,cm−32,fm−12,g0} 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 Gm be the quasi-flower snark for m≥6. Then, ψ(Gm)=4.
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 J5, where the node set VJ5 = {cτ,fτ,gτ,hτ: ∀ 0≤τ≤4} stands in for the individuals and the edge set EJ5 = {cτcτ+1,cτfτ,fτgτ,fτhτ,gτgτ+1,hτhτ+1,g0hn−1,gn−1h0: ∀ 0≤τ≤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 DJ5={c0,c1,f2,g0} of the flower snark network J5 to reduce the number of observers.
We only placed the observers on the nodes c0,c1,f2,g0 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 c0,c1,f2,g0. 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.
In this article, the DMD for the flower snarks Jm and quasi-flower snarks Gm is computed by describing their MDRSs. We conclude that the DMD for the flower snarks Jm is finite and depends upon the order of the network. Also, the DMD for the quasi-flower snarks Gm 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 Prn for all integers r, and n, where r<n2.
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.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
This research is funded by Princess Nourah bint Abdulrahman University Researchers Supporting Project number (PNURSP2024R527), Princess Nourah bint Abdulrahman University, Riyadh, Saudi Arabia.
The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.
[1] |
Epstein RA (2008) Parahippocampal and retrosplenial contributions to human spatial navigation. Trends Cognitive Sci 12: 388-396. https://doi.org/10.1016/j.tics.2008.07.004 ![]() |
[2] |
Vann SD, Aggleton JP, Maguire EA (2009) What does the retrosplenial cortex do?. Nat Rev Neurosci 10: 792-802. https://doi.org/10.1038/nrn2733 ![]() |
[3] |
Ghaem O, Mellet E, Crivello F, et al. (1997) Mental navigation along memorized routes activates the hippocampus, precuneus, and insula. Neuroreport 8: 739-744. https://doi.org/10.1097/00001756-199702100-00032 ![]() |
[4] |
Maguire EA, Burgess N, Donnett JG, et al. (1998) Knowing where and getting there: a human navigation network. Science 280: 921-4. https://doi.org/10.1126/science.280.5365.921 ![]() |
[5] |
Nemmi F, Piras F, Péran P, et al. (2013) Landmark sequencing and route knowledge: an fMRI study. Cortex 49: 507-19. https://doi.org/10.1016/j.cortex.2011.11.016 ![]() |
[6] | Nguyen HM, Matsumoto J, Tran AH, et al. (2014) sLORETA current source density analysis of evoked potentials for spatial updating in a virtual navigation task. Front Behav Neurosci 8: 66. https://doi.org/10.3389/fnbeh.2014.00066 |
[7] |
Patai EZ, Javadi AH, Ozubko JD, et al. (2019) Hippocampal and Retrosplenial Goal Distance Coding After Long-term Consolidation of a Real-World Environment. Cereb Cortex 29: 2748-2758. https://doi.org/10.1093/cercor/bhz044 ![]() |
[8] |
Spiers HJ, Maguire EA (2006) Thoughts, behaviour, and brain dynamics during navigation in the real world. Neuroimage 31: 1826-40. https://doi.org/10.1016/j.neuroimage.2006.01.037 ![]() |
[9] |
Brown TI, Carr VA, LaRocque KF, et al. (2016) Prospective representation of navigational goals in the human hippocampus. Science 352: 1323-6. https://doi.org/10.1126/science.aaf0784 ![]() |
[10] |
Auger SD, Mullally SL, Maguire EA (2012) Retrosplenial cortex codes for permanent landmarks. PLoS One 7: e43620. https://doi.org/10.1371/journal.pone.0043620 ![]() |
[11] |
Auger SD, Zeidman P, Maguire EA (2015) A central role for the retrosplenial cortex in de novo environmental learning. eLife 4: e09031. https://doi.org/10.7554/eLife.09031 ![]() |
[12] |
Viard A, Doeller CF, Hartley T, et al. (2011) Anterior hippocampus and goal-directed spatial decision making. J Neurosci 31: 4613-21. https://doi.org/10.1523/JNEUROSCI.4640-10.2011 ![]() |
[13] |
Takahashi N, Kawamura M, Shiota J, et al. (1997) Pure topographic disorientation due to right retrosplenial lesion. Neurology 49: 464-469. https://doi.org/10.1212/WNL.49.2.464 ![]() |
[14] |
Aguirre GK, D'Esposito M (1999) Topographical disorientation: a synthesis and taxonomy. Brain 122: 1613-28. https://doi.org/10.1093/brain/122.9.1613 ![]() |
[15] |
Vann SD, Aggleton JP (2002) Extensive cytotoxic lesions of the rat retrosplenial cortex reveal consistent deficits on tasks that tax allocentric spatial memory. Behav Neurosci 116: 85-94. https://doi.org/10.1037/0735-7044.116.1.85 ![]() |
[16] |
Vann SD, Wilton LAK, Muir JL, et al. (2003) Testing the importance of the caudal retrosplenial cortex for spatial memory in rats. Behav Brain Res 140: 107-118. https://doi.org/10.1016/S0166-4328(02)00274-7 ![]() |
[17] | Nelson AJ, Powell AL, Holmes JD, et al. (2015) What does spatial alternation tell us about retrosplenial cortex function. Front Behav Neurosci 9: 126. https://doi.org/10.3389/fnbeh.2015.00126 |
[18] |
Chen LL, Lin LH, Barnes CA, et al. (1994a) Head-direction cells in the rat posterior cortex II. Contributions of visual and ideothetic information to the directional firing. Exp Brain Res 101: 24-34. https://doi.org/10.1007/BF00243213 ![]() |
[19] |
Chen LL, Lin LH, Green EJ, et al. (1994b) Head-direction cells in the rat posterior cortex I. Anatomical distribution and behavioral modulation. Exp Brain Res 101: 8-23. https://doi.org/10.1007/BF00243212 ![]() |
[20] |
Cho J, Sharp PE (2001) Head direction, place, and movement correlates for cells in the rat retrosplenial cortex. Behav Neurosci 115: 3-25. https://doi.org/10.1037/0735-7044.115.1.3 ![]() |
[21] |
Jacob PY, Casali G, Spieser L, et al. (2017) An independent, landmark-dominated head-direction signal in dysgranular retrosplenial cortex. Nat Neurosci 20: 173-175. https://doi.org/10.1038/nn.4465 ![]() |
[22] |
Chinzorig C, Nishimaru H, Matsumoto J, et al. (2020) Rat retrosplenial cortical involvement in wayfinding using visual and locomotor cues. Cereb Cortex 30: 1985-2004. https://doi.org/10.1093/cercor/bhz183 ![]() |
[23] |
Fischer LF, Mojica Soto-Albors R, Buck F, et al. (2020) Representation of visual landmarks in retrosplenial cortex. Elife 9: e51458. https://doi.org/10.7554/eLife.51458 ![]() |
[24] |
Alexander AS, Nitz DA (2015) Retrosplenial cortex maps the conjunction of internal and external spaces. Nat Neurosci 18: 1143-1151. https://doi.org/10.1038/nn.4058 ![]() |
[25] |
Alexander AS, Nitz DA (2017) Spatially periodic activation patterns of retrosplenial cortex encode route sub-spaces and distance traveled. Curr Biol 27: 1551-1560. https://doi.org/10.1016/j.cub.2017.04.036 ![]() |
[26] |
Miller AMP, Mau W, Smith DM (2019) Retrosplenial Cortical Representations of Space and Future Goal Locations Develop with Learning. Curr Biol 29: 2083-2090.e4. https://doi.org/10.1016/j.cub.2019.05.034 ![]() |
[27] |
Dean HL, Platt ML (2006) Allocentric spatial referencing of neuronal activity in macaque posterior cingulate cortex. J Neurosci 26: 1117-1127. https://doi.org/10.1523/JNEUROSCI.2497-05.2006 ![]() |
[28] |
Chrastil ER, Warren WH (2014) From cognitive maps to cognitive graphs. PLoS One 9: e112544. https://doi.org/10.1371/journal.pone.0112544 ![]() |
[29] |
Muryy A, Glennerster A (2021) Route selection in non-Euclidean virtual environments. PLoS One 16: e0247818. https://doi.org/10.1371/journal.pone.0247818 ![]() |
[30] |
Matsumura N, Nishijo H, Tamura R, et al. (1999) Spatial- and task-dependent neuronal responses during real and virtual translocation in the monkey hippocampal formation. J Neurosci 19: 2381-2393. https://doi.org/10.1523/JNEUROSCI.19-06-02381.1999 ![]() |
[31] |
Hori E, Nishio Y, Kazui K, et al. (2005) Place-related neural responses in the monkey hippocampal formation in a virtual space. Hippocampus 15: 991-996. https://doi.org/10.1002/hipo.20108 ![]() |
[32] |
Furuya Y, Matsumoto J, Hori E, et al. (2014) Place-related neuronal activity in the monkey parahippocampal gyrus and hippocampal formation during virtual navigation. Hippocampus 24: 113-130. https://doi.org/10.1002/hipo.22209 ![]() |
[33] |
Bretas RV, Matsumoto J, Nishimaru H, et al. (2019) Neural Representation of Overlapping Path Segments and Reward Acquisitions in the Monkey Hippocampus. Front Syst Neurosci 13: 48. https://doi.org/10.3389/fnsys.2019.00048 ![]() |
[34] |
Matsuda K (1996) Measurement system of the eye positions by using oval fitting of a pupil. Neurosci Res 25: S270-S270. https://doi.org/10.1016/0168-0102(96)89315-1 ![]() |
[35] | Saleem KS, Logothetis NK (2012) A combined MRI and histology atlas of the rhesus monkey brain in stereotaxic coordinates. Waltham, Mass: Academic Press. |
[36] |
Sun D, Unnithan RR, French C (2021b) Scopolamine Impairs Spatial Information Recorded With “Miniscope” Calcium Imaging in Hippocampal Place Cells. Front Neurosci 15: 640350. https://doi.org/10.3389/fnins.2021.640350 ![]() |
[37] |
Mao D, Kandler S, McNaughton BL, et al. (2017) Sparse orthogonal population representation of spatial context in the retrosplenial cortex. Nat Commun 8: 243. https://doi.org/10.1038/s41467-017-00180-9 ![]() |
[38] |
Sun W, Choi I, Stoyanov S, et al. (2021a) Context value updating and multidimensional neuronal encoding in the retrosplenial cortex. Nat Commun 12: 6045. https://doi.org/10.1038/s41467-021-26301-z ![]() |
[39] |
Liu B, Tian Q, Gu Y (2021) Robust vestibular self-motion signals in macaque posterior cingulate region. Elife 10: e64569. https://doi.org/10.7554/eLife.64569 ![]() |
[40] |
Peer M, Ron Y, Monsa R, et al. (2019) Processing of different spatial scales in the human brain. Elife 8: e47492. https://doi.org/10.7554/eLife.47492 ![]() |
[41] |
Peer M, Epstein RA (2021a) The human brain uses spatial schemas to represent segmented environments. Curr Biol 31: 4677-4688.e8. https://doi.org/10.1016/j.cub.2021.08.012 ![]() |
[42] |
Enkhjargal N, Matsumoto J, Chinzorig C, et al. (2014) Rat thalamic neurons encode complex combinations of heading and movement directions and the trajectory route during translocation with sensory conflict. Front Behav Neurosci 8: 242. https://doi.org/10.3389/fnbeh.2014.00242 ![]() |
[43] |
Frank LM, Brown EN, Wilson M (2000) Trajectory encoding in the hippocampus and entorhinal cortex. Neuron 27: 169-178. https://doi.org/10.1016/S0896-6273(00)00018-0 ![]() |
[44] |
Wood ER, Dudchenko PA, Robitsek RJ, et al. (2000) Hippocampal neurons encode information about different types of memory episodes occurring in the same location. Neuron 27: 623-633. https://doi.org/10.1016/S0896-6273(00)00071-4 ![]() |
[45] |
Ferbinteanu J, Shapiro ML (2003) Prospective and retrospective memory coding in the hippocampus. Neuron 40: 1227-1239. https://doi.org/10.1016/S0896-6273(03)00752-9 ![]() |
[46] |
Dayawansa S, Kobayashi T, Hori E, et al. (2006) Conjunctive effects of reward and behavioral episodes on hippocampal place-differential neurons of rats on a mobile treadmill. Hippocampus 16: 586-595. https://doi.org/10.1002/hipo.20186 ![]() |
[47] |
Sato N, Sakata H, Tanaka YL, et al. (2006) Navigation-associated medial parietal neurons in monkeys. Proc Natl Acad Sci U S A 103: 17001-17006. https://doi.org/10.1073/pnas.0604277103 ![]() |
[48] | Vedder LC, Miller AMP, Harrison MB, et al. (2017) Retrosplenial cortical neurons encode navigational cues, trajectories and reward locations during goal directed navigation. Cereb Cortex 27: 3713-3723. https://doi.org/10.1093/cercor/bhw192 |
[49] |
Franco LM, Goard MJ (2021) A distributed circuit for associating environmental context with motor choice in retrosplenial cortex. Sci Adv 7: eabf9815. https://doi.org/10.1126/sciadv.abf9815 ![]() |
[50] | Zhang N, Grieves RM, Jeffery KJ (2021) Environment symmetry drives a multidirectional code in rat retrosplenial cortex. bioRxiv . https://doi.org/10.1101/2021.08.22.457261 |
[51] |
Yan Y, Burgess N, Bicanski A (2021) A model of head direction and landmark coding in complex environments. PLoS Comput Biol 17: e1009434. https://doi.org/10.1371/journal.pcbi.1009434 ![]() |
[52] |
Shinder ME, Taube JS (2011) Active and passive movement are encoded equally by head direction cells in the anterodorsal thalamus. J Neurophysiol 106: 788-800. https://doi.org/10.1152/jn.01098.2010 ![]() |
[53] |
Vogt BA, Miller MW (1983) Cortical connections between rat cingulate cortex and visual, motor, and postsubicular cortices. J Comp Neurol 216: 192-210. https://doi.org/10.1002/cne.902160207 ![]() |
[54] | Zilles K, Wree A (1995) Cortex: areal and laminar structure. The rat nervous system . San Diego, CA: Academic Press 649-685. |
[55] |
Vogt BA, Vogt L, Laureys S (2006) Cytology and functionally correlated circuits of human posterior cingulate areas. Neuroimage 29: 452-466. https://doi.org/10.1016/j.neuroimage.2005.07.048 ![]() |
[56] |
Rolls ET (2019) The cingulate cortex and limbic systems for emotion, action, and memory. Brain Struct Funct 224: 3001-3018. https://doi.org/10.1007/s00429-019-01945-2 ![]() |
[57] |
Vann SD, Aggleton JP (2005) Selective dysgranular retrosplenial cortex lesions in rats disrupt allocentric performance of the radial-arm maze task. Behav Neurosci 119: 1682-1686. https://doi.org/10.1037/0735-7044.119.6.1682 ![]() |
[58] |
Diekmann V, Jurgens R, Becker W (2009) Deriving angular displacement from optic flow: a fMRI study. Exp Brain Res 195: 101-116. https://doi.org/10.1007/s00221-009-1753-1 ![]() |
[59] |
Huffman DJ, Ekstrom AD (2019) A Modality-Independent Network Underlies the Retrieval of Large-Scale Spatial Environments in the Human Brain. Neuron 104: 611-622.e7. https://doi.org/10.1016/j.neuron.2019.08.012 ![]() |
[60] |
Burgess N, O'Keefe J (1996) Neuronal computations underlying the firing of place cells and their role in navigation. Hippocampus 6: 749-762. https://doi.org/10.1002/(SICI)1098-1063(1996)6:6<749::AID-HIPO16>3.0.CO;2-0 ![]() |
[61] |
Poucet B, Hok V (2017) Remembering goal locations. Curr Opin Behav Sci 17: 51-56. https://doi.org/10.1016/j.cobeha.2017.06.003 ![]() |
[62] |
Sarel A, Finkelstein A, Las L, et al. (2017) Vectorial representation of spatial goals in the hippocampus of bats. Science 355: 176-180. https://doi.org/10.1126/science.aak9589 ![]() |
[63] |
Smith DM, Barredo J, Mizumori SJ (2012) Complimentary roles of the hippocampus and retrosplenial cortex in behavioral context discrimination. Hippocampus 22: 1121-1133. https://doi.org/10.1002/hipo.20958 ![]() |
[64] |
Yoshida M, Chinzorig C, Matsumoto J, et al. (2021) Configural Cues Associated with Reward Elicit Theta Oscillations of Rat Retrosplenial Cortical Neurons Phase-Locked to LFP Theta Cycles. Cereb Cortex 31: 2729-2741. https://doi.org/10.1093/cercor/bhaa395 ![]() |
[65] |
McCoy AN, Crowley JC, Haghighian G, et al. (2003) Saccade reward signals in posterior cingulate cortex. Neuron 40: 1031-1040. https://doi.org/10.1016/S0896-6273(03)00719-0 ![]() |
[66] |
McCoy AN, Platt ML (2005) Risk-sensitive neurons in macaque posterior cingulate cortex. Nat Neurosci 8: 1220-1227. https://doi.org/10.1038/nn1523 ![]() |
[67] |
Gauthier JL, Tank DW (2018) A dedicated population for reward coding in the hippocampus. Neuron 99: 179-193. https://doi.org/10.1016/j.neuron.2018.06.008 ![]() |
[68] |
Dabaghian Y, Brandt VL, Frank LM (2014) Reconceiving the hippocampal map as a topological template. Elife 3: e03476. https://doi.org/10.7554/eLife.03476 ![]() |
[69] |
Muller RU, Kubie JL, Saypoff R (1991) The hippocampus as a cognitive graph (abridged version). Hippocampus 1: 243-246. https://doi.org/10.1002/hipo.450010306 ![]() |
[70] |
Trullier O, Wiener SI, Berthoz A, et al. (1997) Biologically based artificial navigation systems: review and prospects. Prog Neurobiol 51: 483-544. https://doi.org/10.1016/S0301-0082(96)00060-3 ![]() |
[71] |
Peer M, Brunec IK, Newcombe NS, et al. (2021b) Structuring Knowledge with Cognitive Maps and Cognitive Graphs. Trends Cogn Sci 25: 37-54. https://doi.org/10.1016/j.tics.2020.10.004 ![]() |
[72] |
Poucet B, Herrmann T (2001) Exploratory patterns of rats on a complex maze provide evidence for topological coding. Behav Processes 53: 155-162. https://doi.org/10.1016/S0376-6357(00)00151-0 ![]() |
[73] |
Xu Z, Skorheim S, Tu M, et al. (2017) Improving efficiency in sparse learning with the feedforward inhibitory motif. Neurocomputing 267: 141-151. https://doi.org/10.1016/j.neucom.2017.05.016 ![]() |
[74] |
Tukker JJ, Beed P, Brecht M, et al. (2022) Microcircuits for spatial coding in the medial entorhinal cortex. Physiol Rev 102: 653-688. https://doi.org/10.1152/physrev.00042.2020 ![]() |
[75] |
Stacho M, Manahan-Vaughan D (2022) Mechanistic flexibility of the retrosplenial cortex enables its contribution to spatial cognition. Trends Neurosci 45: 284-296. https://doi.org/10.1016/j.tins.2022.01.007 ![]() |
[76] |
Ison MJ, Mormann F, Cerf M, et al. (2011) Selectivity of pyramidal cells and interneurons in the human medial temporal lobe. J Neurophysiol 106: 1713-1721. https://doi.org/10.1152/jn.00576.2010 ![]() |
[77] |
Dinh HT, Nishimaru H, Matsumoto J, et al. (2018) Superior Neuronal Detection of Snakes and Conspecific Faces in the Macaque Medial Prefrontal Cortex. Cereb Cortex 28: 2131-2145. https://doi.org/10.1093/cercor/bhx118 ![]() |
[78] |
Sulpizio V, Committeri G, Lambrey S, et al. (2013) Selective role of lingual/parahippocampal gyrus and retrosplenial complex in spatial memory across viewpoint changes relative to the environmental reference frame. Behav Brain Res 242: 62-75. https://doi.org/10.1016/j.bbr.2012.12.031 ![]() |
[79] |
Epstein RA, Vass LK (2013) Neural systems for landmark-based wayfinding in humans. Philos Trans R Soc Lond B Biol Sci 369: 20120533. https://doi.org/10.1098/rstb.2012.0533 ![]() |
[80] |
Lambrey S, Doeller C, Berthoz A, et al. (2012) Imagining being somewhere else: neural basis of changing perspective in space. Cereb Cortex 22: 166-174. https://doi.org/10.1093/cercor/bhr101 ![]() |
[81] |
Chrastil ER, Sherrill KR, Hasselmo ME, et al. (2015) There and Back Again: Hippocampus and Retrosplenial Cortex Track Homing Distance during Human Path Integration. J Neurosci 35: 15442-15452. https://doi.org/10.1523/JNEUROSCI.1209-15.2015 ![]() |
[82] |
Chrastil ER, Sherrill KR, Aselcioglu I, et al. (2017) Individual Differences in Human Path Integration Abilities Correlate with Gray Matter Volume in Retrosplenial Cortex, Hippocampus, and Medial Prefrontal Cortex. eNeuro 4: ENEURO.0346-16.2017. https://doi.org/10.1523/ENEURO.0346-16.2017 ![]() |
[83] |
Byrne P, Becker S, Burgess N (2007) Remembering the past and imagining the future: a neural model of spatial memory and imagery. Psychol Rev 114: 340-375. https://doi.org/10.1037/0033-295X.114.2.340 ![]() |
[84] |
Chrastil ER (2013) Neural evidence supports a novel framework for spatial navigation. Psychon Bull Rev 20: 208-27. https://doi.org/10.3758/s13423-012-0351-6 ![]() |
[85] |
Guterstam A, Björnsdotter M, Gentile G, et al. (2015) Posterior cingulate cortex integrates the senses of self-location and body ownership. Curr Biol 25: 1416–25. https://doi.org/10.1016/j.cub.2015.03.059 ![]() |
[86] |
Hirshhorn M, Grady C, Rosenbaum RS, et al. (2012) Brain regions involved in the retrieval of spatial and episodic details associated with a familiar environment: an fMRI study. Neuropsychologia 50: 3094-106. https://doi.org/10.1016/j.neuropsychologia.2012.08.008 ![]() |
[87] |
Ziv Y, Burns LD, Cocker ED, et al. (2013) Long-term dynamics of CA1 hippocampal place codes. Nat Neurosci 16: 264-266. https://doi.org/10.1038/nn.3329 ![]() |
[88] |
Mao D, Neumann AR, Sun J, et al. (2018) Hippocampus-dependent emergence of spatial sequence coding in retrosplenial cortex. Proc Natl Acad Sci U S A 115: 8015-8018. https://doi.org/10.1073/pnas.1803224115 ![]() |
[89] |
Steel A, Billings MM, Silson EH, et al. (2021) A network linking scene perception and spatial memory systems in posterior cerebral cortex. Nat Commun 12: 2632. https://doi.org/10.1038/s41467-021-22848-z ![]() |
[90] |
Papma JM, Smits M, de Groot M, et al. (2017) The effect of hippocampal function, volume and connectivity on posterior cingulate cortex functioning during episodic memory fMRI in mild cognitive impairment. Eur Radiol 27: 3716-3724. https://doi.org/10.1007/s00330-017-4768-1 ![]() |
[91] |
Vanneste S, Luckey A, McLeod SL, et al. (2021) Impaired posterior cingulate cortex-parahippocampus connectivity is associated with episodic memory retrieval problems in amnestic mild cognitive impairment. Eur J Neurosci 53: 3125-3141. https://doi.org/10.1111/ejn.15189 ![]() |
![]() |
![]() |
m | τ | Sτ(f0) |
1 | {c0, g0, h0} | |
2 | {c1, cm−1, g1, gm−1, h1, hm−1} | |
3≤τ≤⌊m2⌋ | {cτ−1, cm−τ+1, fτ−2, fm−τ+2, gτ−1, gm−τ+1, hτ−1, hm−τ+1} | |
even | m+22 | {cm2, fm−22, fm+22, gm2, hm2} |
m+42 | {fm2} | |
odd | m+12 | {cm−12, cm+12, fm−32, fm+32, gm−12, gm+12, hm−12, hm+12} |
m+32 | {fm−12, fm+12} |
DJm | Non-doubly resolved pairs |
{cτ,cυ,cω,f0}, 0≤τ<υ<ω≤m−1 | {f0,g0} |
{cτ,cυ,f0,fω}, 0≤τ<υ≤m−1, 1≤ω≤m−1 | {g0,h0} |
{cτ,f0,fυ,fω}, 0≤τ≤m−1, 1≤υ<ω≤m−1 | {g0,h0} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, 0≤ω≤m−22 | {gm+2ω2,hm+2ω2} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, ω=m−1 | {gm−22,hm−22} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, 0≤ω≤m−22 | {f0,h0} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, ω=m−1 | {f0,g0} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, 0≤ω≤m−22 | {f0,g0} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, ω=m−1 | {f0,h0} |
{f0,fτ,fυ,fω}, 1≤τ<υ<ω≤m−1 | {c0,g0} |
{f0,gτ,gυ,hω}, 0≤τ<υ≤m−1, 0≤ω≤m−1 | {c0,f0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, 0≤ω≤m−22 | {c0,h0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, ω=m2 | {g0,h0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, m+22≤ω≤m−1 | {c0,g0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, 0≤ω≤m−22 | {c0,g0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, ω=m2 | {g0,h0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, m+22≤ω≤m−1 | {c0,h0} |
{f0,gτ,gυ,gω} ⋃ {f0,hτ,hυ,hω}, 0≤τ<υ<ω≤m−1 | {c0,f0} |
{f0,gτ,hυ,hω}, 0≤τ≤m−1, 0≤υ<ω≤m−1 | {c0,f0} |
DJm | Non-doubly resolved pairs |
{cτ,cυ,f0}, 0≤τ<υ≤m−1 | {f0,g0} |
{cτ,f0,fυ}, 0≤τ≤m−1, 1≤υ≤m−1 | {g0,h0} |
{f0,fτ,fυ}, 1≤τ<υ≤m−1 | {c0,g0} |
{f0,fτ,gυ}, 1≤τ≤m−1, 0≤υ≤m−32 | {c0,h0} |
{f0,fτ,gυ}, 1≤τ≤m−1, m−12≤υ≤m−1 | {cυ−1,hυ−1} |
{f0,fτ,hυ}, 1≤τ≤m−1, 0≤υ≤m−32 | {c0,g0} |
{f0,fτ,hυ}, 1≤τ≤m−1, m−12≤υ≤m−1 | {cυ−1,gυ−1} |
{f0,gτ,gυ} ⋃ {f0,hτ,hυ}, 0≤τ<υ≤m−1 | {c0,f0} |
{f0,gτ,hυ}, 0≤τ,υ≤m−1 | {c0,f0} |
τ | Sτ(f0) | DJm={c0,c1,cm2,g0,gm−1} |
0 | f0 | (1,2,m+22,1,2) |
1 | c0 | (0,1,m2,2,3) |
g0 | (2,3,m+42,0,3) | |
h0 | (2,3,m+42,2,1) | |
2 | c1 | (1,0,m−22,3,4) |
cm−1 | (1,2,m−22,3,2) | |
g1 | (3,2,m+22,1,4) | |
gm−1 | (3,4,m+22,3,0) | |
h1 | (3,2,m+22,3,2) | |
hm−1 | (3,4,m+22,1,2) | |
3≤τ≤m2 | cτ−1 | (τ−1,τ−2,m−2τ+22,τ+1,τ+2) |
cm−τ+1 | (τ−1,τ,m−2τ+22,τ+1,τ) | |
fτ−2 | (τ−1,τ−2,m−2τ+62,τ−1,τ) | |
fm−τ+2 | ={(τ+1,τ,m−2τ+62,τ−1,τ+2), if τ<m2;(m+22,m2,3,m−22,m2), if τ=m2. | |
gm−τ+1 | (τ+1,τ+2,m−2τ+62,τ+1,τ−2) | |
hτ−1 | (τ+1,τ,m−2τ+62,τ+1,τ) | |
hm−τ+1 | (τ+1,τ+2,m−2τ+62,τ−1,τ) | |
m+22 | cm2 | (m2,m−22,0,m+42,m+22) |
fm−22 | (m2,m−22,2,m2,m+22) | |
fm+22 | (m2,m+22,2,m2,m−22) | |
gm2 | (m+42,m+22,2,m2,m−22) | |
hm2 | (m+42,m+22,2,m2,m+22) | |
m+42 | fm2 | (m+22,m2,1,m+22,m2) |
τ | Sτ(f0) | DJm={c0,cm−32,fm−12,g0} |
0 | f0 | (1,m−12,m+32,1) |
1 | c0 | (0,m−32,m+12,2) |
g0 | (2,m+12,m+12,0) | |
h0 | (2,m+12,m+12,2) | |
2 | c1 | (1,m−52,m−12,3) |
cm−1 | (1,m−12,m+12,3) | |
g1 | (3,m−12,m−12,1) | |
gm−1 | (3,m+32,m+12,3) | |
h1 | (3,m−12,m−12,3) | |
hm−1 | (3,m+32,m+12,1) | |
3≤τ≤m−12 | cτ−1 | (τ−1,m−2τ−12,m−2τ+32,τ+1) |
cm−τ+1 | (τ−1,m−2τ+52,m−2τ+52,τ+1) | |
fτ−2 | (τ−1,m−2τ+32,m−2τ+72,τ−1) | |
fm−τ+2 | ={(2,m+12,m+32,2), if τ=3;(τ−1,m−2τ+92,m−2τ+92,τ−1), if τ>3. | |
gτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ−1) | |
gm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ+1) | |
hτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ+1) | |
hm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ−1) | |
m+12 | cm−12 | (m−12,1,1,m+32) |
cm+12 | (m−12,2,2,m+32) | |
fm−32 | (m−12,1,3,m−12) | |
fm+32 | (m−12,4,4,m−12) | |
gm−12 | (m+32,3,1,m−12) | |
gm+12 | (m+32,4,2,m+12) | |
hm−12 | (m+32,3,1,m+12) | |
hm+12 | (m+32,4,2,m−12) | |
m+32 | fm−12 | (m+12,2,0,m+12) |
fm+12 | (m+12,3,3,m+12) |
m | τ | Sτ(f0) |
1 | {c0, g0, h0} | |
2 | {c1, cm−1, g1, gm−1, h1, hm−1} | |
3≤τ≤⌊m2⌋ | {cτ−1, cm−τ+1, fτ−2, fm−τ+2, gτ−1, gm−τ+1, hτ−1, hm−τ+1} | |
even | m+22 | {cm2, fm−22, fm+22, gm2, hm2} |
m+42 | {fm2} | |
odd | m+12 | {cm−12, cm+12, fm−32, fm+32, gm−12, gm+12, hm−12, hm+12} |
m+32 | {fm−12, fm+12} |
DGm | Non-doubly resolved pairs |
{cτ,cυ,f0}, 0≤τ<υ≤m−1 | {f0,g0} |
{cτ,f0,gυ}, 0≤τ,υ≤m−1 | {f0,h0} |
{cτ,f0,fυ}, 0≤τ≤m−1, 1≤υ≤m−1 | {g0,h0} |
{cτ,f0,hυ}, 0≤τ,υ≤m−1 | {f0,g0} |
{f0,fτ,gυ}, 1≤τ≤m−1, 0≤υ≤m−1 | {c0,h0} |
{f0,fτ,fυ}, 1≤τ<υ≤m−1 | {c0,g0} |
{f0,gτ,hυ}, 0≤τ,υ≤m−1 | {c0,f0} |
{f0,fτ,hυ}, 1≤τ≤m−1, 0≤υ≤m−1 | {c0,g0} |
{f0,hτ,hυ}, 0≤τ<υ≤m−1 | {f0,g0} |
{f0,gτ,gυ}, 0≤τ<υ≤m−1 | ={{c0,h0}, if m is even {c0,f0}, if m is odd |
τ | Sτ(f0) | DGm={c0,cm2,f1,gm+22} |
0 | f0 | (1,m+22,3,m2) |
1 | c0 | (0,m2,2,m+22) |
g0 | (2,m+42,2,m−22) | |
h0 | (2,m+42,2,m+22) | |
2 | c1 | (1,m−22,1,m+42) |
cm−1 | (1,m−22,3,m2) | |
g1 | (3,m+22,1,m2) | |
gm−1 | (3,m+22,3,m−42) | |
h1 | (3,m+22,1,m+42) | |
hm−1 | (3,m+22,3,m2) | |
3≤τ≤m2 | cτ−1 | (τ−1,m−2τ+22,τ−1,m−2τ+82) |
cm−τ+1 | (τ−1,m−2τ+22,τ+1,m−2τ+42) | |
fτ−2 | ={(2,m2,0,m+22), if τ=3;(τ−1,m−2τ+62,τ−1,m−2τ+82), if τ>3. | |
fm−τ+2 | (τ−1,m−2τ+62,τ+1,m−2τ+42) | |
gτ−1 | (τ+1,m−2τ+62,τ−1,m−2τ+42) | |
gm−τ+1 | (τ+1,m−2τ+62,τ+1,m−2τ2) | |
hτ−1 | (τ+1,m−2τ+62,τ−1,m−2τ+82) | |
hm−τ+1 | (τ+1,m−2τ+62,τ+1,m−2τ+42) | |
m+22 | cm2 | (m2,0,m2,3) |
fm−22 | (m2,2,m2,3) | |
fm+22 | (m2,2,m+42,1) | |
gm2 | (m+42,2,m2,1) | |
hm2 | (m+42,2,m2,3) | |
m+42 | fm2 | (m+22,1,m+22,2) |
τ | Sτ(f0) | DGm={c0,cm−32,fm−12,g0} |
0 | f0 | (1,m−12,m+32,1) |
1 | c0 | (0,m−32,m+12,2) |
g0 | (2,m+12,m+12,0) | |
h0 | (2,m+12,m+12,2) | |
2 | c1 | (1,m−52,m−12,3) |
cm−1 | (1,m−12,m+12,3) | |
g1 | (3,m−12,m−12,1) | |
gm−1 | (3,m+32,m+12,1) | |
h1 | (3,m−12,m−12,3) | |
hm−1 | (3,m+32,m+12,3) | |
3≤τ≤m−12 | cτ−1 | (τ−1,m−2τ−12,m−2τ+32,τ+1) |
cm−τ+1 | (τ−1,m−2τ+52,m−2τ+52,τ+1) | |
fτ−2 | (τ−1,m−2τ+32,m−2τ+72,τ−1) | |
fm−τ+2 | ={(2,m+12,m+32,2), if τ=3;(τ−1,m−2τ+92,m−2τ+92,τ−1), if τ>3. | |
gτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ−1) | |
gm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ−1) | |
hτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ+1) | |
hm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ+1) | |
m+12 | cm−12 | (m−12,1,1,m+32) |
cm+12 | (m−12,2,2,m+32) | |
fm−32 | (m−12,1,3,m−12) | |
fm+32 | (m−12,4,4,m−12) | |
gm−12 | (m+32,3,1,m−12) | |
gm+12 | (m+32,4,2,m−12) | |
hm−12 | (m+32,3,1,m+32) | |
hm+12 | (m+32,4,2,m+32) | |
m+32 | fm−12 | (m+12,2,0,m+12) |
fm+12 | (m+12,3,3,m+12) |
m | τ | Sτ(f0) |
1 | {c0, g0, h0} | |
2 | {c1, cm−1, g1, gm−1, h1, hm−1} | |
3≤τ≤⌊m2⌋ | {cτ−1, cm−τ+1, fτ−2, fm−τ+2, gτ−1, gm−τ+1, hτ−1, hm−τ+1} | |
even | m+22 | {cm2, fm−22, fm+22, gm2, hm2} |
m+42 | {fm2} | |
odd | m+12 | {cm−12, cm+12, fm−32, fm+32, gm−12, gm+12, hm−12, hm+12} |
m+32 | {fm−12, fm+12} |
DJm | Non-doubly resolved pairs |
{cτ,cυ,cω,f0}, 0≤τ<υ<ω≤m−1 | {f0,g0} |
{cτ,cυ,f0,fω}, 0≤τ<υ≤m−1, 1≤ω≤m−1 | {g0,h0} |
{cτ,f0,fυ,fω}, 0≤τ≤m−1, 1≤υ<ω≤m−1 | {g0,h0} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, 0≤ω≤m−22 | {gm+2ω2,hm+2ω2} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,f0,fυ,gω} ⋃ {cτ,f0,fυ,hω}, 0≤τ≤m−1, 1≤υ≤m−1, ω=m−1 | {gm−22,hm−22} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, 0≤ω≤m−22 | {f0,h0} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,cυ,f0,gω}, 0≤τ<υ≤m−1, ω=m−1 | {f0,g0} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, 0≤ω≤m−22 | {f0,g0} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, m2≤ω≤m−2 | {g2ω−m2,h2ω−m2} |
{cτ,cυ,f0,hω}, 0≤τ<υ≤m−1, ω=m−1 | {f0,h0} |
{f0,fτ,fυ,fω}, 1≤τ<υ<ω≤m−1 | {c0,g0} |
{f0,gτ,gυ,hω}, 0≤τ<υ≤m−1, 0≤ω≤m−1 | {c0,f0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, 0≤ω≤m−22 | {c0,h0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, ω=m2 | {g0,h0} |
{f0,fτ,fυ,gω}, 1≤τ<υ≤m−1, m+22≤ω≤m−1 | {c0,g0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, 0≤ω≤m−22 | {c0,g0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, ω=m2 | {g0,h0} |
{f0,fτ,fυ,hω}, 1≤τ<υ≤m−1, m+22≤ω≤m−1 | {c0,h0} |
{f0,gτ,gυ,gω} ⋃ {f0,hτ,hυ,hω}, 0≤τ<υ<ω≤m−1 | {c0,f0} |
{f0,gτ,hυ,hω}, 0≤τ≤m−1, 0≤υ<ω≤m−1 | {c0,f0} |
DJm | Non-doubly resolved pairs |
{cτ,cυ,f0}, 0≤τ<υ≤m−1 | {f0,g0} |
{cτ,f0,fυ}, 0≤τ≤m−1, 1≤υ≤m−1 | {g0,h0} |
{f0,fτ,fυ}, 1≤τ<υ≤m−1 | {c0,g0} |
{f0,fτ,gυ}, 1≤τ≤m−1, 0≤υ≤m−32 | {c0,h0} |
{f0,fτ,gυ}, 1≤τ≤m−1, m−12≤υ≤m−1 | {cυ−1,hυ−1} |
{f0,fτ,hυ}, 1≤τ≤m−1, 0≤υ≤m−32 | {c0,g0} |
{f0,fτ,hυ}, 1≤τ≤m−1, m−12≤υ≤m−1 | {cυ−1,gυ−1} |
{f0,gτ,gυ} ⋃ {f0,hτ,hυ}, 0≤τ<υ≤m−1 | {c0,f0} |
{f0,gτ,hυ}, 0≤τ,υ≤m−1 | {c0,f0} |
τ | Sτ(f0) | DJm={c0,c1,cm2,g0,gm−1} |
0 | f0 | (1,2,m+22,1,2) |
1 | c0 | (0,1,m2,2,3) |
g0 | (2,3,m+42,0,3) | |
h0 | (2,3,m+42,2,1) | |
2 | c1 | (1,0,m−22,3,4) |
cm−1 | (1,2,m−22,3,2) | |
g1 | (3,2,m+22,1,4) | |
gm−1 | (3,4,m+22,3,0) | |
h1 | (3,2,m+22,3,2) | |
hm−1 | (3,4,m+22,1,2) | |
3≤τ≤m2 | cτ−1 | (τ−1,τ−2,m−2τ+22,τ+1,τ+2) |
cm−τ+1 | (τ−1,τ,m−2τ+22,τ+1,τ) | |
fτ−2 | (τ−1,τ−2,m−2τ+62,τ−1,τ) | |
fm−τ+2 | ={(τ+1,τ,m−2τ+62,τ−1,τ+2), if τ<m2;(m+22,m2,3,m−22,m2), if τ=m2. | |
gm−τ+1 | (τ+1,τ+2,m−2τ+62,τ+1,τ−2) | |
hτ−1 | (τ+1,τ,m−2τ+62,τ+1,τ) | |
hm−τ+1 | (τ+1,τ+2,m−2τ+62,τ−1,τ) | |
m+22 | cm2 | (m2,m−22,0,m+42,m+22) |
fm−22 | (m2,m−22,2,m2,m+22) | |
fm+22 | (m2,m+22,2,m2,m−22) | |
gm2 | (m+42,m+22,2,m2,m−22) | |
hm2 | (m+42,m+22,2,m2,m+22) | |
m+42 | fm2 | (m+22,m2,1,m+22,m2) |
τ | Sτ(f0) | DJm={c0,cm−32,fm−12,g0} |
0 | f0 | (1,m−12,m+32,1) |
1 | c0 | (0,m−32,m+12,2) |
g0 | (2,m+12,m+12,0) | |
h0 | (2,m+12,m+12,2) | |
2 | c1 | (1,m−52,m−12,3) |
cm−1 | (1,m−12,m+12,3) | |
g1 | (3,m−12,m−12,1) | |
gm−1 | (3,m+32,m+12,3) | |
h1 | (3,m−12,m−12,3) | |
hm−1 | (3,m+32,m+12,1) | |
3≤τ≤m−12 | cτ−1 | (τ−1,m−2τ−12,m−2τ+32,τ+1) |
cm−τ+1 | (τ−1,m−2τ+52,m−2τ+52,τ+1) | |
fτ−2 | (τ−1,m−2τ+32,m−2τ+72,τ−1) | |
fm−τ+2 | ={(2,m+12,m+32,2), if τ=3;(τ−1,m−2τ+92,m−2τ+92,τ−1), if τ>3. | |
gτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ−1) | |
gm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ+1) | |
hτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ+1) | |
hm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ−1) | |
m+12 | cm−12 | (m−12,1,1,m+32) |
cm+12 | (m−12,2,2,m+32) | |
fm−32 | (m−12,1,3,m−12) | |
fm+32 | (m−12,4,4,m−12) | |
gm−12 | (m+32,3,1,m−12) | |
gm+12 | (m+32,4,2,m+12) | |
hm−12 | (m+32,3,1,m+12) | |
hm+12 | (m+32,4,2,m−12) | |
m+32 | fm−12 | (m+12,2,0,m+12) |
fm+12 | (m+12,3,3,m+12) |
m | τ | Sτ(f0) |
1 | {c0, g0, h0} | |
2 | {c1, cm−1, g1, gm−1, h1, hm−1} | |
3≤τ≤⌊m2⌋ | {cτ−1, cm−τ+1, fτ−2, fm−τ+2, gτ−1, gm−τ+1, hτ−1, hm−τ+1} | |
even | m+22 | {cm2, fm−22, fm+22, gm2, hm2} |
m+42 | {fm2} | |
odd | m+12 | {cm−12, cm+12, fm−32, fm+32, gm−12, gm+12, hm−12, hm+12} |
m+32 | {fm−12, fm+12} |
DGm | Non-doubly resolved pairs |
{cτ,cυ,f0}, 0≤τ<υ≤m−1 | {f0,g0} |
{cτ,f0,gυ}, 0≤τ,υ≤m−1 | {f0,h0} |
{cτ,f0,fυ}, 0≤τ≤m−1, 1≤υ≤m−1 | {g0,h0} |
{cτ,f0,hυ}, 0≤τ,υ≤m−1 | {f0,g0} |
{f0,fτ,gυ}, 1≤τ≤m−1, 0≤υ≤m−1 | {c0,h0} |
{f0,fτ,fυ}, 1≤τ<υ≤m−1 | {c0,g0} |
{f0,gτ,hυ}, 0≤τ,υ≤m−1 | {c0,f0} |
{f0,fτ,hυ}, 1≤τ≤m−1, 0≤υ≤m−1 | {c0,g0} |
{f0,hτ,hυ}, 0≤τ<υ≤m−1 | {f0,g0} |
{f0,gτ,gυ}, 0≤τ<υ≤m−1 | ={{c0,h0}, if m is even {c0,f0}, if m is odd |
τ | Sτ(f0) | DGm={c0,cm2,f1,gm+22} |
0 | f0 | (1,m+22,3,m2) |
1 | c0 | (0,m2,2,m+22) |
g0 | (2,m+42,2,m−22) | |
h0 | (2,m+42,2,m+22) | |
2 | c1 | (1,m−22,1,m+42) |
cm−1 | (1,m−22,3,m2) | |
g1 | (3,m+22,1,m2) | |
gm−1 | (3,m+22,3,m−42) | |
h1 | (3,m+22,1,m+42) | |
hm−1 | (3,m+22,3,m2) | |
3≤τ≤m2 | cτ−1 | (τ−1,m−2τ+22,τ−1,m−2τ+82) |
cm−τ+1 | (τ−1,m−2τ+22,τ+1,m−2τ+42) | |
fτ−2 | ={(2,m2,0,m+22), if τ=3;(τ−1,m−2τ+62,τ−1,m−2τ+82), if τ>3. | |
fm−τ+2 | (τ−1,m−2τ+62,τ+1,m−2τ+42) | |
gτ−1 | (τ+1,m−2τ+62,τ−1,m−2τ+42) | |
gm−τ+1 | (τ+1,m−2τ+62,τ+1,m−2τ2) | |
hτ−1 | (τ+1,m−2τ+62,τ−1,m−2τ+82) | |
hm−τ+1 | (τ+1,m−2τ+62,τ+1,m−2τ+42) | |
m+22 | cm2 | (m2,0,m2,3) |
fm−22 | (m2,2,m2,3) | |
fm+22 | (m2,2,m+42,1) | |
gm2 | (m+42,2,m2,1) | |
hm2 | (m+42,2,m2,3) | |
m+42 | fm2 | (m+22,1,m+22,2) |
τ | Sτ(f0) | DGm={c0,cm−32,fm−12,g0} |
0 | f0 | (1,m−12,m+32,1) |
1 | c0 | (0,m−32,m+12,2) |
g0 | (2,m+12,m+12,0) | |
h0 | (2,m+12,m+12,2) | |
2 | c1 | (1,m−52,m−12,3) |
cm−1 | (1,m−12,m+12,3) | |
g1 | (3,m−12,m−12,1) | |
gm−1 | (3,m+32,m+12,1) | |
h1 | (3,m−12,m−12,3) | |
hm−1 | (3,m+32,m+12,3) | |
3≤τ≤m−12 | cτ−1 | (τ−1,m−2τ−12,m−2τ+32,τ+1) |
cm−τ+1 | (τ−1,m−2τ+52,m−2τ+52,τ+1) | |
fτ−2 | (τ−1,m−2τ+32,m−2τ+72,τ−1) | |
fm−τ+2 | ={(2,m+12,m+32,2), if τ=3;(τ−1,m−2τ+92,m−2τ+92,τ−1), if τ>3. | |
gτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ−1) | |
gm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ−1) | |
hτ−1 | (τ+1,m−2τ+32,m−2τ+32,τ+1) | |
hm−τ+1 | (τ+1,m−2τ+92,m−2τ+52,τ+1) | |
m+12 | cm−12 | (m−12,1,1,m+32) |
cm+12 | (m−12,2,2,m+32) | |
fm−32 | (m−12,1,3,m−12) | |
fm+32 | (m−12,4,4,m−12) | |
gm−12 | (m+32,3,1,m−12) | |
gm+12 | (m+32,4,2,m−12) | |
hm−12 | (m+32,3,1,m+32) | |
hm+12 | (m+32,4,2,m+32) | |
m+32 | fm−12 | (m+12,2,0,m+12) |
fm+12 | (m+12,3,3,m+12) |