Networks with smaller strong diameters generally have better fault tolerance because they enable closer connections between vertices, leading to shorter information paths. This allows the network to maintain communication and functionality more effectively during attacks or failures. In contrast, larger strong diameters mean vertices are connected over longer distances, increasing vulnerability to disruptions. Thus, the strong diameter is a key metric for assessing and optimizing network fault tolerance. This paper determines the optimal orientations for the Cartesian and strong products of even cycles, provides the minimum strong diameters and their bounds under specific conditions, and establishes a lower bound for the maximum strong diameter. A conjecture about the exact value of the maximum strong diameter is also proposed.
The structure of a network is fundamentally analogous to that of a graph, where routers in the network correspond to vertices in the graph, and physical links represent edges connecting these vertices. This parallel makes graphs an essential tool for analyzing complex networks. Furthermore, in disciplines such as social sciences, biology, and computer science, employing graph theory concepts like paths and connectivity to analyze model structures enhances our understanding of the properties and behaviors of these models but also fosters the development of interdisciplinary knowledge and innovation.
Compared to undirected networks, the research on directed networks still needs to be explored. However, to fully understand complex real-world systems, integrating the study of both is essential. Directed networks reveal information flow directionality and node dependencies, which is crucial for analyzing dynamics in social networks, Internet data flow, and ecosystem energy flow. The strong diameter of directed networks is critical as it measures fault tolerance between nodes, identifies critical nodes, and determines optimal transmission paths. It is vital in network topology optimization, traffic scheduling, and community structure detection. Understanding strong diameter properties helps researchers and engineers assess network robustness and optimize transmission efficiency.
We define the graph \(G=(V(G), E(G))\), where \(V(G)\) is the vertex set of graph \(G\), and \(E(G)\) is the edge set of graph \(G\). The two vertices of an edge are called its end-vertices. We call an edge with identical end-vertices a loop. We denote the number of vertices in a graph \(G\) by \(v(G) = |V(G)|\) and refer to it as the order of \(G\). We denote the number of edges by \(\epsilon(G) = |E(G)|\). If both \(v(G)\) and \(\epsilon(G)\) are finite, \(G\) is called a finite graph. This paper primarily studies finite graphs. For graphs \(G\) and \(H\), if there exist two bijections \(\theta: V(G) \to V(H)\) and \(\varphi: E(G) \to E(H)\) such that for any \(e \in E(G)\), \(\psi(e) = (u, v) \Leftrightarrow \psi'(\varphi(e)) = (\theta(u), \theta(v))\), then \(G\) and \(H\) are said to be isomorphic, denoted by \(G \cong H\).
Let \(u,v\in V(G)\), then a \(uv\)-walk of length \(l\) is a sequence of vertices \(W = (v_0, v_1, \ldots, v_l)\). A walk in which all edges \(e_1, e_2, \ldots, e_l\) are distinct is called a trail, and a trail in which all vertices are distinct is called a path. We call walks, trails, and paths that start and end at the same vertex closed walks, closed trails, and cycles, respectively. We call a cycle of odd length an odd cycle, while we call a cycle of even length an even cycle. A cycle of length \(l\) is referred to as a \(l\)-cycle, and a cycle of length three is called a triangle. Any \(uv\)-walk contains a shortest \(uv\)-path, any closed walk must contain a closed trail, and any closed trail must contain a cycle.
For a connected undirected graph \(G\), the eccentricity of \(v\) is defined as \[e(v) = \max\{d(v,x) \mid x \in V(G)\},\tag{1}\] where \(d(v,x)\) represents the distance from \(v\) to \(x\). The diameter of \(G\) is denoted as \[diam(G)=\max\{e(v) \vert v \in V(G)\},\tag{2}\] thus, the diameter of an undirected graph \(G\) is the maximum distance between any two vertices. In an undirected graph, Certain concepts and conclusions relate to the direction of edges in graph \(G\).
By assigning a direction to each edge of an undirected graph \(G\), we obtain a digraph \(D\), referred to as an orientation of graph \(G\). If any two vertices in the orientation \(D\) can be mutually reached, \(D\) is called a strong orientation of graph \(G\). We call the orientation with the minimum diameter among all possible orientations the minimum diameter orientation of graph \(G\). We denote its minimum diameter by \(\vec{d}(G)\). Among all strong orientations of graph \(G\), the strong orientation with the minimum directed diameter is called the optimal orientation of graph \(G\). Similarly, we define the minimum strong diameter of a graph \(G\) as the minimum strong diameter among all possible orientations of graph \(G\), and we denote it by \(sdiam(G)\). According to the famous Robbins’ theorem [21], a connected undirected graph \(G\) has a strong orientation only if \(G\) has no bridge. Therefore, a strong orientation must exist for a connected undirected graph \(G\) without bridges.
Let \(D(G)\) denote the family of all strong orientations of \(G\). Define \(\vec{d}(G) = min\{ diam(D) \vert D \in D(G) \}\). Determining \(\vec{d}(G)\) for any connected undirected graph is highly challenging. In fact, Chvátal and Thomassen [5] have proven that deciding whether an undirected graph has an orientation with a diameter of 2 is an NP-hard problem. Additionally, the parameter \(\vec{d}(G)\) has been studied in various specific classes of graphs, including complete graphs, complete bipartite graphs and complete \(n\)-partite graphs (\(n\geq 3\)) [11,10, 12].
Assume \(D = (V(D), A(D))\) is a strong connected digraph. Chartrand et al. [3] first proposed the concept of strong distance as a novel metric parameter in the study of strongly oriented graphs. For any \(u, v\in V(D)\), we define the strong distance \(sd(u, v)\) between \(u\) and \(v\) as the minimum number of arcs in a strong connected subgraph of \(D\) that contains \(u\) and \(v\). For each \(v\in V(D)\), define the strong eccentricity of \(v\) as
\[se(v) = \max\{sd(v, x)\mid x\in V(D)\},\tag{3}\] then, the strong diameter of \(D\) is \[sdiam(D) = \max\{se(v)\mid v\in V(D)\}.\tag{4}\]
Lai et al. [13] defined the maximum strong diameter and minimum strong diameter of a connected undirected graph \(G\) as follows. For any \(D \in D(G)\), the minimum strong diameter of \(G\), denoted \(sdiam(G)\), is defined as \[sdiam(G) = \min\{sdiam(D)\mid D\in D(G)\},\tag{5}\] the maximum strong diameter of \(G\), denoted \(SDIAM(G)\), is defined as \[SDIAM(G) = \max\{sdiam(D)\mid D\in D(G)\}.\tag{6}\]
As one of the four classical products, the Cartesian product is often used to construct large-scale networks. Let \(G_a = (V_a, E_a)\) and \(G_b = (V_b, E_b)\) be two undirected graphs. The Cartesian product of \(G_a\) and \(G_b\) is denoted as \(G_{a}\times G_{b}\), where \(V(G_{a}\times G_{b})=V_{a}\times V_{b}\). Two distinct vertices \(u_{a}u_{b}\) and \(v_{a}v_{b}\) (\(u_{a},u_{b}\in V(G_{a}),v_{a},v_{b}\in V(G_{b})\)) are adjacent if and only if \(u_{a}=v_{a}\) and \(u_{b}v_{b}\in E(G_{b})\), or \(u_{b}=v_{b}\) and \(u_{a}v_{a}\in E(G_{a})\). \(G_{a}\) and \(G_{b}\) are called the factor graph of \(G_{a}\times G_{b}\). The Cartesian product enables the ordered combination of the structural features of two graphs, creating a graph with new structures and properties. Interested readers can refer to the references [6,9, 22,26] for more research on Cartesian products.
The strong product is also one of the most extensively studied products. Let \(G_a = (V_a, E_a)\) and \(G_b = (V_b, E_b)\) be two undirected graphs. Their Cartesian product is denoted as \(G_{a}\otimes G_{b}\), where \(V(G_{a}\otimes G_{b})=V_{a}\times V_{b}\). Two distinct vertices \(u_{a}u_{b}\) and \(v_{a}v_{b}\) (\(u_{a},u_{b}\in V(G_{a}),v_{a},v_{b}\in V(G_{b})\)) are adjacent if and only if one of the following conditions holds: \(u_{a}=v_{a}\) and \(u_{b}v_{b}\in E(G_{b})\), \(u_{b}=v_{b}\) and \(u_{a}v_{a}\in E(G_{a})\), or \(u_{a}u_{b}\in E(G_{a})\) and \(v_{a}v_{b}\in E(G_{b})\). The definition of the strong product graph ingeniously integrates the concepts of Cartesian product and direct product. It captures the adjacency relationships of the original graphs and incorporates the comprehensive structural features among different graphs. Consequently, the strong product graph provides a powerful tool for analyzing the compound properties of graphs. Readers interested in the latest research progress on strong product graphs may refer to references [1,2, 25,28]. In addition to the strong product operation, commonly used graph product operations include direct and lexicographic products. For state-of-the-art research findings on these two types of products, readers can consult references [15,14,4,19].
Considerable research has been conducted on strong diameter problems for graphs. Xiaofeng Guo and Huifang Miao [18] proposed the minimum strong diameter of complete \(k\)-partite graphs. Juan et al. [8] investigated the strong distance problem in the Cartesian product of graphs. Yi Huang and Meirun Chen [7] provided the minimum and maximum oriented strong diameters of the Cartesian product of paths. The minimum strong diameter orientation of 2-vertex dilation graphs was studied by Guoxiang Zhang and Aiming Yang [29]. Shuyang Liu and Feng Li [17,16] explored the strong radius and strong diameter of the strong product of complete graphs, as well as the strong radius and strong diameter of the lexicographic product of complete graphs.
In this paper, we employ the Cartesian and the strong products to construct product networks of cycles. We determine the exact values and bounds of these networks’ minimum oriented diameter and maximum strong diameter under certain conditions. Furthermore, we provide new lower bounds for the maximum strong diameter and propose conjectures regarding their exact values. These findings offer insights into understanding and analyzing the complexity of cyclic structures and their potential applications in network theory.
Not all graphs have strong orientations (e.g., trees, star graphs, etc.), and only those with strong orientations are of research significance to us. Below, we present the edge connectivity of the Cartesian product of graphs and the famous Robbins theorem, and we prove that the Cartesian product of cycles has a strong orientation.
Lemma 2.1. [21] A graph \(G\) has strong orientation if and only if \(G\) is biconnected.
Lemma 2.2. [23] Let \(G_{1}\) and \(G_{2}\) be two connected undirected graphs. Denote the order, minimum degree, and edge connectivity of \(G_{i}(i=1,2)\) by \(n_{i}\), \(\delta_{i}\), and \(\lambda_{i}\), respectively. Then, we have \[\lambda(G_{1} \times G_{2}) = \min\{\delta_{1} + \delta_{2}, n_{1}\lambda_{2}, n_{2}\lambda_{1}\}.\tag{7}\]
Based on the above lemma, we can prove that the Cartesian product graph admits a strong orientation by demonstrating that it is an \(l\)-connected graph with \(l \geq 2\).
Theorem 2.1. Let \(G_{1}\) and \(G_{2}\) be non-trivial connected simple graphs of order \(m\) and \(n\), respectively. Then \(G_{1} \times G_{2}\) has strong orientation.
Proof. Let \(G_1\) and \(G_2\) be connected simple graphs of order \(m\) and \(n\), respectively. By Lemma 2.1, the edge connectivity of \(G_1 \times G_2\) is minimized when \(G_1\) and \(G_2\) attain minimal edge connectivity, order, size, and minimum degree. This minimum occurs at \(G_1 = G_2 = K_2\). Applying Lemma 2.2, \(\lambda(G_1 \times G_2) \geq \lambda(K_2 \times K_2) = 2\). Combined with Lemma 2.1, this ensures \(G_1 \times G_2\) admits a strong orientation. ◻
In [17], Liu provided a proof that the strong product graph admits a strong orientation, and we present his results as follows.
Lemma 2.3. [17] Let \(G_{1}\) and \(G_{2}\) be non-trivial connected simple graphs of order \(m\) and \(n\), respectively. Then \(G_{1} \otimes G_{2}\) has strong orientation.
In [7], Huang and Chen established the inequality \(sdiam(P_{m} \times P_{n}) \geq 2\,diam(P_{m} \times P_{n})\) for Cartesian product graphs. By applying the same methodology, we derive the following generalized results: \[\label{equation 8} sdiam(C_{m} \times C_{n}) \geq 2\,diam(C_{m} \times C_{n}),\tag{8}\] \[\label{equation 9} sdiam(C_{m} \otimes C_{n}) \geq 2\,diam(C_{m} \otimes C_{n}).\tag{9}\]
Below, we present the diameter formula for Cartesian product graphs, the distance formula for strong product graphs, and derive the diameters for the Cartesian product and strong product of cycles.
Lemma 2.4. [27] \(diam(G_{1}\times G_{2}\times \cdots \times G_{n})=diam(G_{1})+diam(G_{2})+\cdots + diam(G_{n})\).
Lemma 2.5. [20] If \((g,h)\) and \((g',h')\) are vertices of a strong product \(G\otimes H\), then \[d_{G\otimes H}((g,h),(g',h'))=max\{d_{G}(g,h),d_{H}(g',h')\}.\tag{10}\]
By Lemma 2.4, we can obtain
\[diam(C_{m} \times C_{n}) = diam(C_{m}) + diam(C_{n}),\tag{11}\]
where \(diam(C_{m}) = \lfloor m/2 \rfloor\) and \(diam(C_{n}) = \lfloor n/2 \rfloor\). By Lemma 2.5 and the definition of diameter, we have
\[diam(C_{m} \otimes C_{n}) = \max\{diam(C_{m}), diam(C_{n})\}.\tag{12}\]
All the undirected graphs considered are simple, and all the directed graphs are simple, strong connected directed graphs. For notation and terminology not mentioned above but used in the text, please refer to references [17,16].
By the definitions of oriented and strong diameters, if we can find a strong orientation \(F\) of a graph \(G\) such that \(\vec{d}(F)=diam(G)\), then we arrive at the minimum strong diameter \(sdiam(G)=2diam(G)\) of the graph \(G\). Below, we give the optimal oriented diameters of the Cartesian product of cycles under some conditions.
Theorem 3.1. Let \(m\geq 3,n\geq 2\), then there exists \(F\in D(C_{2n}\times C_{2m})\) such that
(i) \(\vec{d}(F)=diam(C_{2n}\times C_{2m})=m+n\),
(ii) In \(F\), every vertex in \(C_{2n}\times C_{2m}\) is in a cycle of length at most \(2(m+n)\).
Proof. Let \(C_m\) and \(C_n\) be two distinct cycles with \(m\geq 3,n\geq 2\). Since \(C_{2n}\times C_{2m}\cong C_{2m}\times C_{2n}\), without loss of generality, we will only discuss the case of \(m\geq n\), and in the following we will consider it in the following 3 cases.
Case 1. \(n = 2\), \(m \equiv 1~(mod~2)\), and \(m \geq 3\). Orient \(F \in D(C_{2n} \times C_{2m})\) as follows (see Figure 1):
For \(i=1,3\), and \(j=1,2,\cdots ,2n-1\), orient \((i,j)\rightarrow (i,j+1)\), and orient \((i,2m)\rightarrow (i,1)\);
For \(i=2,4\), and \(j=1,2,\cdots ,2n-1\), orient \((i,j+1)\rightarrow (i,j)\), and orient \((i,1)\rightarrow (i,2m)\);
For \(j\equiv 1~(mod~2)\), and \(i=1,2,\cdots ,2m-1\), orient \((i+1,j)\rightarrow (i,j)\), and orient \((2m,j)\rightarrow (1,j)\);
For \(j\equiv 0~(mod~2)\), and \(i=1,2,\cdots ,2m-1\), orient \((i+1,j)\rightarrow (i,j)\), and orient \((1,j)\rightarrow (2m,j)\).
Clearly, for the strong orientation \(F\), there is \(\vec{d}(F) = m+2\). Now, consider the following cycles (see Figure 1):
\((A_1)~(1,1)(2,1)(3,1)(3,2)(3,3)(3,4)(2,4)(1,4)(1,5)\) \((1,6)(1,1)\);
\((A_2)~(1,5)(2,5)(3,5)(3,6)(3,1)(3,2)(3,3)(3,4)(2,4)\) \((1,4)(1,5)\);
\((A_3)~(2,2)(2,1)(3,1)(4,1)(4,6)(4,5)(4,4)(4,3)(4,2)\) \((3,2)(2,1)\);
\((A_4)~(2,5)(3,5)(4,5)(4,4)(4,3)(4,2)(3,2)(2,2)(2,1)\) \((2,6)(2,5)\).
It can be verified that the above cycle has a length of at most \(2(m+2)\) and that each vertex in \(F\) is in a cycle of length at most \(2(m+2)\). In addition, every vertex in \(F\) exists in a cycle of length at least 4.
Case 2. \(n\geq 3\), \(m \equiv 1 ~(mod~2)\), and \(m \geq 3\). Orient \(F \in D(C_{2n} \times C_{2m})\) as follows (see Figure 2):
For \(i\equiv 1~(mod~2)\), and \(j=1,2,\cdots ,2n-1\), orient \((i,j)\rightarrow (i,j+1)\), and orient \((i,2m)\rightarrow (i,1)\);
For \(i\equiv 0~(mod~2)\), and \(j=1,2,\cdots ,2n-1\), orient \((i,j+1)\rightarrow (i,j)\), and orient \((i,1)\rightarrow (i,2m)\);
For \(j\equiv 1~(mod~2)\), and \(i=1,2,\cdots ,2m-1\), orient \((i,j)\rightarrow (i+1,j)\), and orient \((2n,j)\rightarrow (1,j)\);
For \(j\equiv 0~(mod~2)\), and \(i=1,2,\cdots ,2m-1\), orient \((i+1,j)\rightarrow (i,j)\), and orient \((1,j)\rightarrow (2n,j)\).
For the strong orientation \(F\), there is \(\vec{d}(F) = m+n\). Now, consider the following cycles (see Figure 2):
\((B_1)~(1,1)(2,1)(3,1)(3,2)(3,3)\cdots(3,10)(2,10)(1,10)(1,1)\);
\((B_2)~(3,3)(3,4)\cdots(3,8)(2,8)(1,8)(1,9)(2,9)(3,9)(3,10)(3,1)(3,2)(3,3)\);
\((B_3)~(3,1)(3,2)\cdots(3,6)(2,6)(1,6)(1,7)(1,8)(1,9)(2,9)(3,9)(3,10)(3,1)\);
\((B_4)~(1,4)(1,5)\cdots(1,9)(2,9)(3,9)(3,10)(2,10)(1,10)(1,1)(1,2)\) \((1,3)(1,4)\).
It can be verified that the above cycle has a length of at most \(2(m+n)\) and that each vertex in \(F\) is in a cycle of length at most \(2(m+n)\). In addition, every vertex in \(F\) exists in a cycle of length at least 4.
Case 3. \(n\geq 2,m \equiv 0~(mod~2)\). Orient \(F \in D(C_{2n} \times C_{2m})\) as follows (see Figure 3):
For \(i \equiv 0~(mod~2)\), and \(j=2,\cdots ,2m\), orient \((i,j)\rightarrow (i,j-1)\), and orient \((i,1)\rightarrow (i,2m)\);
For \(i \equiv 1~(mod~2)\), and \(j=1,2,\cdots ,2m-1\), orient \((i,j)\rightarrow (i,j+1)\), and orient \((i,2m)\rightarrow (i,1)\);
For \(j=1,3,\cdots ,m\), and \(i=1,2,\cdots ,2n-1\), orient \((i,j)\rightarrow (i+1,j)\), and orient \((n,j)\rightarrow (1,j)\);
For \(j=2,4,\cdots ,m-1\), and \(i=2,3,\cdots ,2n\), orient \((i,j)\rightarrow (i-1,j)\), and orient \((2n,j)\rightarrow (1,j)\);
For \(j=m+1,m+3,\cdots ,2m-1\), and \(i=2,3,\cdots ,2n\), orient \((i,j)\rightarrow (i-1,j),\) and orient \((1,j)\rightarrow (2n,j)\);
For \(j=m+2,m+4,\cdots ,2m\), and \(i=1,2,\cdots ,2n-1\), orient \((i,j)\rightarrow (i+1,j)\), and orient \((2n,j)\rightarrow (1,j)\).
For the strong orientation \(F\), there is \(\vec{d}(F) = m+n\). Now, consider the following cycles (see Figure 3):
\((C_1)~(1,1)(1,2)\cdots(1,5)(2,5)(3,5)\cdots(3,12)(3,1)(4,1)(1,1)\);
\((C_2)~(3,3)(2,3)(1,3)(1,4)\cdots(1,12)(2,12)\) \((3,12)(3,1)(3,1)(3,3)\);
\((C_3)~(2,11)(2,10)\cdots(2,6)(1,6)(4,6)(4,5)(1,5)(2,5)(2,4)\cdots(2,1)(2,12)(2,11)\);
\((C_4)~(4,9)(4,8)\cdots(4,4)(3,4)(2,4)(2,3)(2,2)(2,1)(2,12)(3,12)(4,12)(4,11)(4,10)(4,9)\).
It can be verified that the above cycle has a length of at most \(2(m+n)\) and that each vertex in \(F\) is in a cycle of length at most \(2(m+n)\). In addition, every vertex in \(F\) exists in a cycle of length at least 4. In summary, the proof is complete. ◻
Based on the above Theorem 3.1, we give the value of the minimum strong diameter of the Cartesian product of cycles and upper and lower bounds.
Theorem 3.2. . Let \(C_{2m}\) and \(C_n\) be two different cycles, \(G=C_{n}\times C_{2m} (m\geq 2,n\geq 3)\), then \[sdiam(G)=2diam(G).\tag{13}\]
Proof. Since \(C_{2m}\times C_n\cong C_n\times C_{2m}\), without loss of generality, we will only discuss the case of \(2m\geq n\). When \(m\geq 3,n\geq 3\), the conclusion holds by Theorem 3.1 and the definition of the minimum strong diameter, and below, we orientate the other cases separately as follows:
Case 1. \(m\geq 2, n\equiv 1 \pmod{2}\). Orient \(F \in D(C_{n} \times C_{2m})\) as follows (see Figure 4):
The orientation of \(F[P_{n-1}\times P_{2m}]\) is the same as that of \(F[P_{2n}\times P_{2m} ]\) in Case 2 of Theorem 3.1;
For \(j\equiv 1~(mod~2)\), and \(i=1,2,\cdots ,2m\), orient \((i,j)\rightarrow(i+1,j)\);
For \(j\equiv 0~(mod~2)\), and \(i=1,2,\cdots ,2m\), orient \((i+1,j)\rightarrow(i,j)\);
For \(i=n,j=1,2,\cdots ,n-1\), orient \((i,n)\rightarrow(i+1,n)\), orient \((2m,n)\rightarrow(1,n)\).
Case 2. \(m\geq 2, n\equiv 0 ~(mod~2)\). Orient \(F \in D(C_{n} \times C_{2m})\) as Case 2 of Theorem 3.1.
It is easy to verify that the orientation of both Case 1 and Case 2 is consistent with the question, and the proof is complete. ◻
Theorem 3.3. Let \(C_m\) and \(C_{n}\) be two odd cycles, \(G=C_n\times C_m(m\geq 3,n\geq 3)\), then \[\label{equation 12} 2diam(G)\leq sdiam(G)\leq 2diam(G)+1.\tag{14}\]
Proof. Without loss of generality, we only prove the case \(m \geq n\). The same can be proved when \(m < n\). We orient \(C_n \times C_m\) according to the following orientation:
For \(i\equiv 1 ~(mod~2)\), and \(j=1,2,\cdots ,n-1\), orient \((i,j)\rightarrow (i,j+1)\), and orient \((i,m)\rightarrow (i,1)\);
For \(i\equiv 0 ~(mod~2)\), and \(j=1,2,\cdots ,n-1\), orient \((i,j+1)\rightarrow (i,j)\), and orient \((i,1)\rightarrow (i,m)\);
For \(j\equiv 1 ~(mod~2)\), and \(i=1,2,\cdots ,m-1\), orient \((i,j)\rightarrow (i+1,j)\), and orient \((n,j)\rightarrow (1,j)\);
For \(j\equiv 0 ~(mod~2)\), and \(i=1,2,\cdots ,m-1\), orient \((i+1,j)\rightarrow (i,j)\), and orient \((1,j)\rightarrow (n,j)\).
Clearly, every vertex in \(F\) is contained in a cycle of length at most \(2diam(C_n\times C_m)+1\), i.e., \(sdiam(C_n\times C_m)\leq 2diam(C_n\times C_m)+1\), and by the definition of the minimum strong diameter, then we get \(sdiam(C_n\times C_m)\leq 2diam(C_n\times C_m)+1\), and also by (8), we have \(sdiam(G)\geq 2diam(G)\), so we can get (14). Proof is complete. ◻
Next, we will provide the potential lower bound for the maximum strong diameter of the Cartesian product of cycles. Before that, we will first present its possible maximum strong diameter.
Theorem 3.4. Let \(m \geq 3,n \geq 3\), then there exists a strong orientation \(D\) of \(G=C_{n}\times C_{m}\) such that
(i) if \(m \equiv 0 \pmod{2}\), then \(sdiam(G)=mn\),
(ii) if \(m \equiv 1 \pmod{2}\), then \(sdiam(G)=mn+1\).
Proof. Let \(P\) be a Hamiltonian path in \(C_m \times C_n\) with vertex \(x = (1, 1)\) as the start vertex, and \((u, v)\) be a successor vertex of \((u', v')\) if \(v < v'\) for any vertices \((u, v)\) and \((u', v')\). If \(m\) is even (odd), the end vertex of path \(P\) is \(y = (n, m)\) (\(y = (1, m)\)). In the strong orientation \(D\) of \(C_m \times C_n\), \(P\) is the shortest directed \((x, y)\)-path and \(Q\) is the shortest directed \((y, x)\)-path. Thus, we have \(\vert A(Q) \setminus A(P) \vert = 1\)(or \(2\)), from which we know that \(P \cup Q\) is the minimum strong connected subgraph containing the vertices \(x\) and \(y\), and hence we have \(sd_D(x, y) = mn\)(or \(mn+1\))(See Figure 5). Moreover, this strong connected subgraph contains all vertices in \(D\), so we have \(sdiam(D) = mn\)(or \(mn+1\)). ◻
Theorem 3.6. . Let \(C_m\) and \(C_n\) be two different cycles, \(G=C_n\times C_m(m\geq n \geq 3,m\equiv 0~(mod~2)\), then \(SDIAM(G) \geq mn\).
Proof. Since \(C_m \times C_n \cong C_n \times C_m\), without loss of generality, we only discuss the case \(m \geq n\). According to the above Theorem 3.4, if \(m \geq 3\) and \(n \geq 3\), there exists a strong orientation \(D\) of \(C_m \times C_n\) such that \(sdiam(D) = mn\). According to the definition of the maximum strong diameter, we obtain \[SDIAM(G) \geq sdiam(D) \geq mn,\tag{15}\]
i.e., \(SDIAM(G) \geq mn\), the proof is complete. ◻
Theorem 3.6. . Let \(C_m\) and \(C_n\) be two different cycles, \(G=C_n\times C_m(m\geq n \geq 3,m\equiv 1~(mod~2)\), then \(SDIAM(G) \geq mn+1\).
Proof. Proof is similar to Theorem 3.5. ◻
In this section, we present the optimal orientation for the strong product of even cycles, as well as the lower bounds for the minimum and maximum strong diameters of the strong product of cycles.
In [24], Ladinek and Špacapan obtained : For every even \(m, n \geq 2\), then \[\vec{d}(C_{2n} \otimes C_{2m}) \leq max\{m, n\} + 1,\tag{16}\]
based on the orientation of the Cartesian product of the above cycles, we now present the minimum oriented diameter of \(C_{2n} \otimes C_{2m}\).
Theorem 4.1. Let \(m\geq 3,n\geq 2\), then there exists \(F\in D(C_{2n}\otimes C_{2m})\) such that
(i) \(\vec{d}(F)=diam(C_{2n}\otimes C_{2m})\),
(ii) In \(F\), every vertex in \(C_{2n}\otimes C_{2m}\) is in a cycle of length at most \(2max(n,m)\).
Proof. In all the following cases, let \(G = C_{2n} \times C_{2m}\). The orientation with the minimum diameter is referred to as the optimal orientation. The optimal orientation for the Cartesian product of cycles is given in Theorem 3.1. We will discuss the following 3 cases.
Case 1. \(n = 2\), \(m \equiv 1 ~(mod~2)\), and \(m \geq 3\). Orient \(F \in D(C_{2n} \otimes C_{2m})\) as follows (see Figure 6):
Optimal orientation for \(C_{4} \times C_{2m}\);
Orient \((2m,2n) \rightarrow (1,1)\),\((2n,1)\rightarrow (1,2m)\);
For \(i = 1, 2, 3\) and \(j = 1, 2, \cdots, 2m-1\), orient \((i,j) \rightarrow (i+1,j+1)\);
For \(i = 1, 2, 3\) and \(j = 2, \cdots, 2m\), orient \((i,j) \rightarrow (i+1,j-1)\);
For \(i = 1, 2, 3\), orient \((i,2m) \rightarrow (i+1,2m)\), and otient \((i,1)\rightarrow (i+1,2m)\);
For \(j=1,2,\cdots ,2m-1\), orient \((2n,j) \rightarrow (2n,j+1)\), and for \(j=2,3,\cdots ,2m\), orient \((2n,j)\rightarrow (2n,j-1)\).
Based on the above orientation, it is easy to see that the oriented distance between any two vertices in \(F\) is less than or equal to \(2diam(C_{2n} \otimes C_{2m})\). Therefore, we can conclude that \(\vec{d}(C_{2n} \otimes C_{2m}) = diam(C_{2n} \otimes C_{2m})\). Now, consider the following cycles (see Figure 6):
\((A_1)~(1,1)(2,2)(3,3)(3,4)(4,3)(4,2)(1,1)\);
\((A_2)~(1,3)(2,2)(3,1)(4,6)(4,5)(4,4)(1,3)\);
\((A_3)~(2,5)(3,4)(4,3)(4,2)(1,3)(1,4)(2,5)\);
\((A_4)~(4,4)(1,3)(2,1)(3,1)(4,6)(4,5)(4,4)\).
It can be verified that the above cycle has a length of at most \(2diam(C_{2n}\otimes C_{2m})\) and that each vertex in \(F\) is in a cycle of length at most \(2max(n,m)\). In addition, every vertex in \(F\) exists in a cycle of length at least 4.
Case 2. \(n\equiv 0 ~(mod~2)\), \(m \equiv 1 ~(mod~2)\), and \(m \geq 3,n\geq 3\). Orient \(F \in D(C_{2n} \otimes C_{2m})\) as follows (see Figure 7):
Optimal orientation for \(C_{2m} \times C_{2n}\);
Orient \((2m,2n) \rightarrow (1,1)\),\((2n,1)\rightarrow (1,2m)\);
For \(i = 1, 2,\cdots , 2n-1\) and \(j = 1, 2, \cdots, 2m-1\), orient \((i,j) \rightarrow (i+1,j+1)\);
For \(i = 1, 2, \cdots, 2n-1\) and \(j = 2, \cdots, 2m\), orient \((i,j) \rightarrow (i+1,j-1)\);
For \(i = 1, 2,\cdots , 2n-1\), orient \((i,2m) \rightarrow (i+1,2m)\), and orient \((i,1)\rightarrow (i+1,2m)\);
For \(j=1,2,\cdots ,2m-1\), orient \((2n,j) \rightarrow (2n,j+1)\), and for \(j=2,3,\cdots ,2m\), orient \((2n,j)\rightarrow (2n,j-1)\).
Based on the above orientation, it is easy to see that the oriented distance between any two points in \(F\) is less than or equal to \(2diam(C_{2n} \otimes C_{2m})\). Therefore, we can conclude that \(\vec{d}(C_{2n} \otimes C_{2m}) = diam(C_{2n} \otimes C_{2m})\). Now, consider the following cycles (see Figure 7):
\((B_1)~(1,1)(1,2)(3,3)(3,4)(3,5)(3,6)(4,5)(4,4)(4,3)\) \((4,2)(1,1)\);
\((B_2)~(2,3)(3,4)(3,5)(3,6)(3,7)(4,8)(4,7)(4,6)(4,5)\) \((1,4)(2,3)\);
\((B_3)~(1,8)(2,7)(3,6)(4,5)(4,4)(4,3)(1,4)(1,5)(1,6)\) \((1,7)(1,8)\);
\((B_4)~(4,4)(1,5)(1,6)(1,7)(1,8)(2,9)(3,8)(4,7)(4,6)\) \((4,5)(4,4)\).
It can be verified that the above cycle has a length of at most \(2diam(C_{2n}\otimes C_{2m})\) and that each vertex in \(F\) is in a cycle of length at most \(2max(n,m)\). In addition, every vertex in \(F\) exists in a cycle of length at least 4.
Case 3. \(n\equiv 0 ~(mod~2), m\equiv 0 ~(mod~2),m\geq 2,n\geq 2\). Orient \(F \in D(C_{2n} \otimes C_{2m})\) as follows:
Optimal orientation for \(C_{2m} \times C_{2n}\);
Perform orientation for (2)-(6) in Case 2.
Based on the above orientation, it is easy to see that the oriented distance between any two points in \(F\) is less than or equal to \(2diam(C_{2n} \otimes C_{2m})\). Therefore, we can conclude that \(\vec{d}(C_{2n} \otimes C_{2m}) = diam(C_{2n} \otimes C_{2m})\). Now, consider the following cycles (\(C_{8}\otimes C_{4}\)):
\((C_1)~(4,3)(1,4)(2,5)(3,6)(3,7)(4,6)(4,5)(4,4)(4,3)\);
\((C_2)~(4,6)(1,5)(2,4)(2,3)(3,2)(4,1)(4,8)(4,7)(4,6)\);
\((C_3)~(4,4)(1,3)(2,2)(2,1)(3,8)(3,1)(3,2)(3,3)(4,4)\);
\((C_4)~(1,6)(2,5)(3,4)(4,3)(4,2)(1,3)(1,4)(1,5)(1,6)\).
It can be verified that the above cycle has a length of at most \(2diam(C_{2n}\otimes C_{2m})\) and that each vertex in \(F\) is in a cycle of length at most \(2max(n,m)\). In addition, every vertex in \(F\) exists in a cycle of length at least 4. In summary, the proof is complete. ◻
Next, we derive the minimum strong diameter of the strong product of cycles under this condition through the above Theorem 4.1.
Theorem 4.2. Let \(C_{m}\) and \(C_{n}\) are two different cycles, and \(G = C_{n} \otimes C_{m}\) (\(m \geq 4, n \geq 3, m\equiv 0~(mod~2)\)), then \(sdiam(G) = 2diam(G)\).
Proof. Since \(C_{m} \times C_{n} \cong C_{n} \times C_{m}\), without loss of generality, we only consider the case where \(m \geq n\). When \(m \geq 6\), \(n \geq 4\)(n\(\equiv 0 ~(mod~2)\), it is evident from Theorem 4.1 and the definition of the minimum strong diameter that the conclusion holds. Below, we orient the graph for the other as follows:
Case 1. \(n\equiv 1~(mod~2),m\equiv 0~(mod~2)\). Orient \(F \in D(C_{n} \otimes C_{m})\) as follows:
Orient \(C_{n} \times C_{m}\) according to Case 1 of Theorem 3.2;
Orient \((1,1)\rightarrow (m,n)\),\((n,1)\rightarrow (1,m)\);
For \(i=1,2,\cdots, n-1\), and \(j=1,2,\cdots,m-1\), orient \((i+1,j+1)\rightarrow (i,j)\);
For \(i=1,2,\cdots,n-1\), and \(j=2,3,\cdots,m\), orient \((i,j)\rightarrow (i+1,j-1)\);
For \(i=1,2,\cdots, n-1\), orient \((i,1)\rightarrow (i+1,m)\), and orient \((i+1,1)\rightarrow (i,m)\);
For \(j=2,3,\cdots,m\), orient \((n,j)\rightarrow (1,j-1)\), and orient \((1,j)\rightarrow (n,j-1)\).
Case 2. \(m=4,n=4\), orient
\((1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow (1,4)\rightarrow (1,1)\), \((3,1)\rightarrow (3,2)\rightarrow (3,3)\rightarrow (3,4)\rightarrow (3,1)\);
\((2,1)\rightarrow (2,4)\rightarrow (2,3)\rightarrow (2,2)\rightarrow (2,1)\), \((4,1)\rightarrow (4,4)\rightarrow (4,3)\rightarrow (4,2)\rightarrow (4,1)\);
\((1,1)\rightarrow (2,1)\rightarrow (3,1)\rightarrow (4,1)\rightarrow (1,1)\), \((1,3)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (4,3)\rightarrow(1,3)\);
\((1,2)\rightarrow (2,2)\rightarrow (3,2)\rightarrow (4,2)\rightarrow (1,2)\), \((1,4)\rightarrow (2,4)\rightarrow (3,4)\rightarrow (4,4)\rightarrow (1,4)\);
\((3,4)\rightarrow (1,4)\), \((4,2)\rightarrow (3,1)\rightarrow (2,4)\), \((1,4)\rightarrow (2,1)\rightarrow (3,2)\rightarrow (4,3)\), \((4,4)\rightarrow (3,3)\rightarrow (2,2)\rightarrow (1,1)\rightarrow (4,4)\), \((4,1)\rightarrow (1,2)\rightarrow (2,3)\rightarrow (3,4)\), \((2,4)\rightarrow (1,3)\rightarrow (4,2)\), \((4,3)\rightarrow (1,4)\);
\((4,1)\rightarrow (1,4)\), \((2,4)\rightarrow (1,1)\rightarrow (4,2)\), \((4,3)\rightarrow (1,2)\rightarrow (2,1)\rightarrow (3,4)\), \((4,4)\rightarrow (3,1)\rightarrow (2,2)\rightarrow (1,3)\rightarrow (4,4)\), \((1,4)\rightarrow (2,3)\rightarrow (3,2)\rightarrow (4,1)\), \((4,2)\rightarrow (3,3)\rightarrow (2,4)\), \((3,4)\rightarrow (4,3)\).
Clearly, cases 1 and 2 satisfy \(sdiam(G) = 2diam(G)\), thus the theorem is proven. ◻
For the minimum strong diameter of the strong product of odd cycles, we have established both upper and lower bounds.
Theorem 4.3. Let \(C_m\) and \(C_n\) are two different odd cycles, and \(G = C_m \otimes C_n\) (\(m \geq 5, n \geq 3\)), then \[\label{equation 15} 2diam(G) \leq sdiam(G) \leq 2diam(G) + 1.\tag{17}\]
Proof. Without loss of generality, we only prove the case \(m \geq n\). The same can be proved when \(m < n\). We orient \(C_m \otimes C_n\) according to the following orientation:
For \(i\equiv 1~(mod~2)\) and \(j=1,2,\cdots ,m-1\), orient \((i,j)\rightarrow (i,j+1)\), and orient \((i,m)\rightarrow (1,j)\);
For \(i\equiv 0~(mod~2)\) and \(j=1,2,\cdots ,m-1\), orient \((i,j+1)\rightarrow (i,j)\), and orient \((i,1)\rightarrow (i,m)\);
For \(j\equiv 1~(mod~2)\) and \(i=1,2,\cdots ,n-1\), orient \((i,j)\rightarrow (i+1,j)\), and orient \((n,j)\rightarrow (1,j)\);
For \(j\equiv 0~(mod~2)\) and \(i=1,2,\cdots ,n-1\), orient \((i+1,j)\rightarrow (i,j)\), and orient \((1,j)\rightarrow (n,j)\);
For \(i=1,2,\cdots ,n-1\) and \(j=1,2,\cdots ,m-1\), orient \((i+1,j+1)\rightarrow (i,j)\);
For \(i=1,2,\cdots ,n-1\) and \(j=2,\cdots ,m\), orient \((i,j)\rightarrow (i+1,j-1)\);
For \(i=1,2,\cdots ,n-1\), orient \((i+1,1)\rightarrow (i,m)\), and orient \((i,1)\rightarrow (i+1,m)\);
For \(j=1,2,\cdots , m-1\), orient \((n,j+1)\rightarrow (1,j)\), and orient \((j+1,1)\rightarrow (j,m)\).
As can be seen in Figure 8, every vertex in \(F\) is contained in a cycle of length at most \(2diam(C_m\otimes C_n)+1\), i.e., \(sdiam\leq 2diam(C_m\otimes C_n)+1\), and by the definition of the minimum strong diameter, then we get \(sdiam(C_m\otimes C_n)\leq 2diam(C_m\otimes C_n)+1\), and also by (9), we have \(sdiam(G)\geq 2diam(G)\), so we have (17). Proof is complete. ◻
In the above theorems, we did not provide the minimum strong diameter and diameter orientations for \(C_{3} \otimes C_{3}\). So we prove them as follows.
Theorem 4.4. Let \(C_m\) and \(C_n\) be two different cycles, with \(G = C_m \otimes C_n\)(\(m = 3,n = 3\)). Then, \(\vec{d}(G) = 2\) and \(sdiam(G) = 3\).
Proof. Let \(C_m\) and \(C_n\) be two different cycles, with \(m = 3\) and \(n = 3\). Based on the structure of \(C_3 \otimes C_3\), the point \((1,1)\) can connect to every other vertices in \(G\) through paths of length 1. If \(\vec{d}(C_3 \otimes C_3) = 1\) were true, it would imply that, for the vertex \((1,1)\), there exist directed paths of length one from \((1,1)\) to the remaining 8 vertices. This construction, however, would not yield a strongly connected directed graph, as no diameter of length one exists. Thus, \(\vec{d}(C_3 \otimes C_3) \geq 2\). We orient \(C_3 \otimes C_3\) as follows:
\((1,2)\rightarrow (3,2)\rightarrow (2,2)\rightarrow (1,2)\);
\((1,1)\rightarrow (2,1)\rightarrow (3,1)\rightarrow (1,1)\), \((1,3)\rightarrow (2,3)\rightarrow (3,3)\rightarrow (1,3)\);
\((1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow (1,1)\), \((3,1)\rightarrow (3,2)\rightarrow (3,3)\rightarrow (3,1)\);
\((3,2)\rightarrow (1,3)\rightarrow (2,1)\rightarrow (3,2)\), \((2,3)\rightarrow (1,2)\rightarrow (2,3)\), \((3,3)\rightarrow (1,1)\rightarrow (2,2)\rightarrow (3,3)\);
\((3,1)\rightarrow (1,3)\rightarrow (2,2)\rightarrow (3,1)\), \((2,3)\rightarrow (3,2)\rightarrow (1,1)\rightarrow (2,3)\), \((3,3)\rightarrow (1,3)\rightarrow (2,1)\rightarrow (3,3)\).
It is easily verified that \(\vec{d}(G) = 2\) and \(sdiam(G) = 3\). ◻
Theorem 4.5. Let \(m \geq 3,n \geq 3\), then there exists a strong orientation \(D\) of \(C_{m}\otimes C_{n}\) such that \(sdiam(D)=mn\).
Proof. Proof is similar to Theorem 3.4. ◻
We define \(\rho(G) = diam(G) – \vec{d}(G)\). Combined with Theorem 3.1, we have the following Corollary 4.1 and Corollary 4.2.
Corollary 4.1. Let \(m \geq 3\) and \(n \geq 2\), then \(\rho(C_{2n} \times C_{2m}) = 0\), where \(\rho(C_{2n} \times C_{2m}) = diam(C_{2n} \times C_{2m}) – \vec{d}(C_{2n} \times C_{2m})\).
Proof. According to the Theorem 3.1, if \(m \geq 3\) and \(n \geq 2\), then \(\vec{d}(C_{2n} \times C_{2m}) = m + n\). It is also easily seen that \(diam(C_{2n} \times C_{2m}) = diam(C_{2n}) + diam(C_{2m}) = m + n\). \(\rho(C_{2n} \times C_{2m})\) is defined as \(\rho(C_{2n} \times C_{2m}) = diam(C_{2n} \times C_{2m}) – \vec{d}(C_{2n} \times C_{2m})\), thus we obtain \(\rho(C_{2n} \times C_{2m}) = 0\). ◻
Corollary 4.2. Let \(m \geq 3\) and \(n \geq 2\), then \(\rho(C_{2n} \otimes C_{2m}) = 0\), where \(\rho(C_{2n} \otimes C_{2m}) = diam(C_{2n} \otimes C_{2m}) – \vec{d}(C_{2n} \otimes C_{2m})\).
Proof. The proof is similar to Corollary 4.1. ◻
Conjecture 4.1. Let \(C_n\) and \(C_m\) be two different cycles, \(G=C_n\times C_m(m\geq n \geq 3,m\equiv 0~(mod~2))\), then \(SDIAM(G) = mn\).
Conjecture 4.2. Let \(C_n\) and \(C_m\) be two different cycles, \(G=C_n\times C_m(m\geq n \geq 3,m\equiv 1~(mod~2))\), then \(SDIAM(G) = mn+1\).
Conjecture 4.3. Let \(C_n\) and \(C_m\) be two different cycles, \(G=C_n\otimes C_m(m\geq 3,n\geq 3)\), then \(SDIAM(G) = mn\).
This section delves into the application prospects of strong and Cartesian product networks in network structure design. Using simulation methods, we will conduct meticulous numerical simulations to determine the upper and lower bounds of the minimum and maximum strong diameters and the oriented diameter. By leveraging comprehensive simulations and precise calculations, we aim to gain a thorough understanding of the characteristics of these two network structures in terms of strong diameter and oriented diameter.
Additionally, this section explores the minimum and maximum strong diameter boundaries of Cartesian product networks and strong product networks with different factor graphs, drawing on existing research results. We compare the results to reveal the influence of different product operations and factor graph combinations on crucial network parameters. This comparison not only highlights the impact of these factors on network properties but also lays a crucial theoretical foundation and provides valuable design guidance for constructing complex network structures with specific strong diameter properties.
To facilitate a comparative analysis of the data, we first present the optimal oriented diameter of Cartesian product networks of paths, the optimal oriented diameter of Cartesian product networks of cycles and paths, and the minimum strong diameter of strong product networks of paths, based on the findings of previous studies.
In [11], Koh and Tay successfully determined the minimum oriented diameters of Cartesian product networks of paths and Cartesian product networks of cycles and paths. They achieved this by constructing minimum diameter orientations for these two types of networks. The specific results are as follows: Let \(P_{m}\) and \(P_{n}\) be two distinct paths. When \(m \geq 3\), \(n \geq 6\), and \((m, n) \neq (3, 6)\), we obtain \(\vec{d}(F) = diam(P_{m} \times P_{n}) = m + n – 2\). On the other hand, let \(C_{2n}\) be an even cycle. When \(n \geq 2\) and \(k \geq 4\), we have \(\vec{d}(F) = diam(C_{2m} \times P_{n}) = m + k – 1\). These results greatly facilitate our data computation and verification. Following the methodological framework established in (8) and (9), we extend Huang’s approach to determine the lower bound for the strong diameter in strong products of two paths: \(sdiam(P_{m} \otimes P_{n}) \geq 2\max(m-1, n-1)\).
In the following research, we will conduct four sets of comparative experiments focusing on the minimum oriented diameter of Cartesian product networks of cycles and the minimum strong diameter of strong product networks of cycles. The first set of experiments will fix a specific parameter and calculate and compare the minimum oriented diameters of Cartesian product networks with different factor graphs and the minimum oriented diameters of networks obtained from different product operations on the same factor graphs. The second set of experiments will comprehensively compare the minimum oriented diameters of networks with different factor graphs and product operations. In the third set of experiments, we will again fix a parameter and investigate the minimum strong diameters of product networks obtained from the same factor graphs under different product operations. We will also introduce strong product networks of paths for comparison. The fourth set of experiments will provide a comprehensive comparison based on the findings from the third set of experiments. Through this series of experimental designs, we aim to gain a more comprehensive understanding of the behavioral characteristics of product networks under different conditions, leading to more accurate conclusions.
In the first set of experiments, we fixed the number of vertices in the second factor graph at \(n = 20\) to meet the requirements and facilitate observation. The number of vertices in the first factor graph was set to \(6 \leq m \leq 30\) with \(m \equiv 0 \pmod{2}\). We calculated the minimum oriented diameters of the Cartesian product of cycles, the Cartesian product of paths, the Cartesian product of cycles and paths, and the strong product of cycles and plotted Figure 9. From this figure, it is evident that under the same product and order, \(\vec{d}(C_{m} \times C_{n}) \leq \vec{d}(C_{m} \times P_{n}) \leq \vec{d}(P_{m} \times P_{n})\). Observing the data in Figure 9 (b), we can see that the minimum oriented diameter of the strong product network of cycles is significantly smaller than that of the Cartesian product network of cycles. Additionally, \(\vec{d}(C_{m} \otimes C_{n})\) only changes with increasing \(m\) when \(m \geq 20\). By analyzing the product structures of these four types of graphs, we found that the observed changes are due to the differences in the diameters of the factor graphs: the performance of the product network of factor graphs with smaller diameters is better than that of the product network of factor graphs with larger diameters.
In the second set of experiments, we set the number of vertices in the two factor graphs to be \(30 \leq m \leq 60\) and \(30 \leq n \leq 60\), respectively, with \(m \equiv 0 \pmod{2}\) and \(n \equiv 0 \pmod{2}\). We then calculated \(\vec{d}(C_{m} \times C_{n})\), \(\vec{d}(C_{m} \times P_{n})\), and \(\vec{d}(P_{m} \times P_{n})\), see as Figure 10. Comparing the values of the minimum oriented diameters, we conclude that \(\vec{d}(C_{m} \times C_{n}) \leq \vec{d}(C_{m} \times P_{n}) \leq \vec{d}(P_{m} \times P_{n})\). Observing and comparing the value ranges, we find that \(\vec{d}(C_{m} \times C_{n})\) and \(\vec{d}(P_{m} \times P_{n})\) are equally affected by changes in the orders of the two factor graphs, resulting in their value ranges forming oblique planes. Although the value range of \(\vec{d}(C_{m} \times P_{n})\) is also an oblique plane, the values on the left are higher than those on the right, indicating that \(\vec{d}(C_{m} \times P_{n})\) is more influenced by \(v(C_{m})\). Meanwhile, the value of \(\vec{d}(C_{m} \otimes C_{n})\) at any given moment depends solely on either \(v(C_{m})\) or \(v(C_{n})\), exhibiting a different characteristic from the other three product networks. Through analysis and comparison, we discover that the smaller the diameter of the factor graph, the smaller the minimum oriented diameter of the product graph. Additionally, the more edges in the product graph, its minimum oriented diameter is smaller.
In the third set of experiments, we perform numerical simulations to compare the minimum strong diameters of product networks. First, we fix the number of vertices in the second factor graph at \(n = 20\) and set the number of vertices in the first factor graph to be \(10 \leq m \leq 30\). We then calculate \(sdiam(C_{m} \times C_{n})\), \(sdiam(C_{m} \otimes C_{n})\), and \(sdiam(P_{m} \times P_{n})\) (with \(m\) and \(n\) being odd numbers at different instances). From Figure 11(a), it can be observed that the numerical comparison yields \(sdiam(P_{m} \times P_{n}) \geq sdiam(C_{m} \times C_{n}) \geq sdiam(C_{m} \otimes C_{n})\). Moreover, the curves of \(sdiam(P_{m} \times P_{n})\) and \(sdiam(C_{m} \times C_{n})\) are relatively smooth, while \(sdiam(C_{m} \otimes C_{n})\) exhibits a sawtooth pattern. Because the values of \(sdiam(P_{m} \times P_{n})\) and \(sdiam(C_{m} \times C_{n})\) are simultaneously affected by both factor graphs. In contrast, the value of \(sdiam(C_{m} \otimes C_{n})\) is influenced primarily by the factor graph with the larger order.
In the fourth set of experiments, we comprehensively compare the minimum strong diameters of product networks through numerical simulations. We set the number of vertices in the factor graphs to be \(10 \leq m \leq 30\) and \(10 \leq n \leq 30\), with \(m\) and \(n\) being odd numbers at different instances and calculate \(sdiam(C_{m} \times C_{n})\), \(sdiam(C_{m} \otimes C_{n})\), and \(sdiam(P_{m} \otimes P_{n})\). From Figure 11 (b)-(d), it can be observed that the numerical comparisons yield the same conclusions as in experiment three. Regarding the value range distribution, the values of \(sdiam(C_{m} \otimes C_{n})\) and \(sdiam(P_{m} \otimes P_{n})\) are influenced primarily by one factor graph, resulting in their value ranges exhibiting a “V” shape. In contrast, the value range of \(sdiam(C_{m} \times C_{n})\) presents an oblique plane because both factor graphs simultaneously influence its values. Furthermore, since odd cycles and even cycles with a difference of 1 have the same diameter, the value ranges of \(sdiam(C_{m} \otimes C_{n})\) and \(sdiam(P_{m} \otimes P_{n})\) exhibit a wavy pattern.
In summary, through the numerical comparisons of the product above networks, we can draw the following conclusions: when the diameter of the factor graphs is smaller, the resulting product network, under the same product operation, has a smaller minimum oriented diameter and minimum strong diameter. Additionally, more complex product operations lead to higher connectivity of the product network, resulting in smaller minimum oriented diameter and minimum strong diameter. These findings provide valuable insights into understanding the impact of different product operations and factor graph combinations on the critical parameters of product networks. They lay a solid foundation for designing and optimizing future complex network structures with specific diameter characteristics.
In this paper, we have constructed a new product network using strong product and Cartesian product operations. These networks not only retain the characteristics of small networks but also meet the requirements of large-scale network design. This approach provides a new perspective for deeply understanding network topology, lays a solid data foundation, and offers a multi-dimensional analysis viewpoint. Additionally, this paper determines the minimum oriented diameter of Cartesian and strong products of cycles, as well as their upper and lower bounds under certain conditions. We have also established the minimum strong diameter of strong and Cartesian products of cycles, along with their upper and lower bounds under specific conditions, and explored the range of their maximum strong diameter. These findings open new avenues for network fault tolerance research and the development of network design and optimization strategies.
In the future, We plan to continue focusing on strong distance problems and further investigate the strong distance parameters of critical network structures such as hypercubes and twisted hypercubes. This will deepen our understanding of the interactions between these network structures and provide more theoretical support and practical guidance for constructing efficient and robust complex network systems.
This work was supported in part by the National Natural Science Foundation of China under Grant 11551002, in part by the Natural Science Foundation of Qinghai Province under Grant 2019-ZJ-7093.