Suppose \(G_1=(V_1, E_1)\) is a graph and \(G_2=(V_2, E_2)\) is a strong digraph of \(G_1\), where \(V_1\) and \(V_2\) represent the vertex sets, \(E_1\) and \(E_2\) represent the edge sets. Let \(u\) and \(v\) be any two vertices of \(G_2\). The strong distance \(sd(u,v)\) is the minimum value of edges in a strong subdiagraph of \(G_2\) that contains \(u\) and \(v\). The minimum strong diameter of \(G_2\) is defined as the maximum eccentricity \(se(u)\) from \(u\) to all other vertices in \(G_2\). In this paper, we propose different strong orientation methods to explore the minimum strong diameter of the strong product graph of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\), where \(K_{m_1,m_2,\ldots,m_k}\) and \(P_n\) represent respectively complete multipartite graph and path. In addition, based on strong orientation methods, a new algorithm is proposed to model the presence or absence of a minimum strong diameter in a strong product graph. Simulation experiments show a trend of simultaneous decrease and concentration in the minimum strong diameter of the strong product graph, as the value of parts in \(K_{m_1,m_2,\ldots,m_k}\) increases while the length of \(P_n\) remains constant.
The graph of \(G\) is formally defined as an ordered pair \((V(G),E(G))\), where \(V(G)\) denotes the set of vertices and \(E(G)\) denotes the set of edges. A simple graph is one without loops or multiple edges. A path is a sequence of distinct vertices where consecutive vertices are adjacent. A path on the \(n\) vertices, which has length \(n-1\), is denoted by \(P_n\). For any vertices \(u\) and \(v\) in \(G\), the distance \(d_G(u,v)\) is the length of a minimum \(u-v\) path.
A complete multipartite graph \(K_{m_1,m_2,\ldots,m_k}\) is a graph whose vertex set is partitioned into \(k\) classes of sizes \(m_1,m_2,\ldots,m_k\), such that two vertices are adjacent if and only if they belong to different partite sets.
The eccentricity of a vertex \(u\), denoted by \(e(u)\), is the maximum distance from \(u\) to any other vertex in the graph. The diameter of \(G\), denoted by \(diam(G)\), is the maximum eccentricity among all the vertices.
Given an unoriented simple graph \(G\), after orienting all edges in \(G\), a oriented graph \(D\) is obtained. An orientation \(D\) of \(G\) is called a strong orientation if \(D\) is strongly connected; that is, for every pair of vertices \(u\) and \(v\) in \(D\), there is an oriented path from \(u\) to \(v\) and an oriented path from \(v\) to \(u\). Meanwhile, we need to understand some basic definitions.
Chartrand et al. in [8] introduced the definition of strong distance. While in a strongly connected oriented graph \(D\), the strong distance between vertices \(u\) and \(v\) is defined as the sum of the lengths of the minimum oriented path from \(u\) to \(v\) and the minimum oriented path from \(v\) to \(u\), the formula is: \[\begin{equation} \begin{aligned} sd(u,v)=d(u,v)+d(v,u), \end{aligned} \end{equation} \tag{1}\] where \(d(u,v)\) denotes the value of arcs in the minimum oriented path from \(u\) to \(v\), \(d(v,u)\) denotes the value of arcs in the minimum oriented path from \(v\) to \(u\). As shown in Figure 1, the strong distance from \(u\) to the other six vertices is as follows:
\[\begin{align} sd(u,w)=&3, sd(u,x)=3, sd(u,m)=3;\notag\\ sd(u,t)=&3, sd(u,x)=3, sd(u,x)=5. \end{align} \tag{2}\]
The strong eccentricity of a vertex \(u\) is the maximum strong distance from \(u\) to all other vertices in \(D\), the formula is: \[\begin{equation} \begin{aligned} se(u)=max\{sd(u,v)\vert v\in V(D)\}. \end{aligned} \end{equation} \tag{3}\]
The minimum strong diameter of \(D\) is the maximum strong eccentricity over all vertices in \(D\), the formula is: \[\begin{equation} \begin{aligned}sdiam\left(D\right)=max\{se\left(v\right)|v\in V\left(D\right)\}. \end{aligned} \end{equation} \tag{4}\]
In addition to the definition of the strong eccentricity and the minimum strong diameter, based on the complex unoriented graph \(G\), Chen et al. in [10] introduced the minimum strong diameter in \(G\), which means the minimum strong diameter over all strong orientations of \(D\). The formula is: \[\begin{equation} \begin{aligned}&sdiam\left(G\right)=min\{sdiam\left(D\right)|D\in \textbf{D(G)}\}, \end{aligned} \end{equation} \tag{5}\] where \(\textbf{D(G)}\) denotes the set of all strong orientations of \(G\). In order to better understand the definition of strong diameter, as shown in Figure 1, the strong eccentricity of all vertices is as follows: \(se(m)=4\), \(se(u)=5\), \(se(x)=5\), \(se(y)=5\),\(se(v)=5\), \(se(v)=6\), \(se(t)=6\). From the above strong diameters, the minimum strong diameter is \(4\).
The strong product makes simple graphs easy to build large-scale graphs. Here is a formal definition of the strong product: establishing two unoriented simple graphs \(G_1\) = \((V(G_1),E(G_1))\), \(G_2\) = \((V(G_2),E(G_2))\). The set of vertices of \(G_1\otimes G_2\) is indicated by \(V(G_1\otimes G_2)\) = \(V(G_1)\times V(G_2)\), two vertices \((u_1,v_1)\), \((u_2,v_2)\) are adjacent in \(G_1 \otimes G_2\) only if: (1) \(u_1 = u_2\) and \((v_1,v_2)\in E(G_2)\); (2) \(v_1\) = \(v_2\) and \((u_1,u_2)\in E(G_1)\); (3) \((u_1,u_2)\in E(G_1)\) and \((v_1,v_2)\in E(G_2)\). In order to better understand the definition and properties of the strong product, as shown in Figure 2, the strong product is performed using \(K_{1,2,1}\) and \(P_3\) as an example. More properties of other graph products can be found in [19, 20, 22].
So far, many meaningful diameter results have been obtained. Zhou in [28] and [29] constructed the cartesian product graph and the strong product graph of cycle and path, proposed several different methods of strong orientation, obtained the lower and upper bounds of the minimum and maximum strong diameter. Liu et al. in [21] proved that the strong product of any two nontrivial complete graphs is strongly oriented, obtained the exact value of the minimum strong diameter after orientation. Das et al. in [15] proposed an investigation on the minimum absolute oriented group of arcs, and it was observed that an oriented graph with a diameter not exceeding 2 is an absolute oriented graph, proved that the minimum absolute oriented group size of arcs is a strictly increasing function. Badu et al. in [2] separately proposed the orientational diameter of the graph and the maximum orientational diameter of the graph family. Based on the Chvátal and Thomassen’s research results, obtained the upper of the maximum directional diameter. Dankelmann et al. in [13] proposed two boundaries for the orientational diameter of two graphs derived from a given graph, namely the complement graph and the line graph, proved that the orientational diameter of the line graph in graph \(G\) cannot exceed the orientational diameter of \(G\) by more than 1, and is at least approximately the square root of the directional diameter of \(G\). Ciaci et al. in [11] generalized the property of strong diameters to two-dimensional bases, explored the stability under orient sums and tensor products under the condition that every convex sequence of slices of the unit ball intersects the unit ball. Sadhukhan et al. in [23] proposed a simple unoriented graph \(G\) to be acyclic, which has \(AOP\) properties (\(AOP\) represents there is absence of pendant vertices and absence of pendant vertices in graph \(G\)), constructed graphs with any odd perimeter that did not have \(AOP\) properties, proved these graphs did not have \(AOP\) properties when the existence of a perimeter equal to 5. Lakshmi et al. in [18] proved a definite size for \(sdiam(K-3)^3 = sdiam(K -4)^3 = 5\), and for \(sdiam(K-m) ^3-(P-n)\) by cyclic vertex multiplication. Carmesin in [6] proved that a graph \(G\) had an r-bounded subdivision only if it did not have graph decomposition limitations parameters and had a width of at most 2. Cambie et al. in [5] proposed the minimum diameter of the line graph for any maximum degree graph with multiple edges, and obtained a sufficiently large upper bound on the degree graph for the boundary problem of distance color index.
Before obtaining the minimum strong diameter, it is of utmost importance to orient all the edges in the strong product graph. Cochran in [12] discussed that there is at most a size in the form of a boundary, considered the perimeter \(g\) of graph \(G\), proved that every graph of \(n\)-order with minimum degree can make orientation. Špacapan in [24] directly considered the orientation of the cartesian product of graphs with bridges, proved that for every connected unbridged graph \(H\) and any simple unoriented graph \(G\), the cartesian product of both had at most the minimum allowed weak diameter orientation. Ladinek et al. in [17] proved that for arbitrary connected graphs \(G_1\) and \(G_2\), there exists a strongly connected oriented graph \(D\) of \(G_1 \otimes G_2\) such that \(diam(D)\le2r+15\). Aksoy et al. in [1] established a mild condition when a possibly irregular sparse graph \(G\) had many strong orientations, proved that if \(G\) satisfied the minimality condition and the size of Cheeger’s constant is to be minimal. More research on diameter and orientation can be found in [3, 4, 9, 25].
With the graph strong product being increasingly used in modeling, calculating the strong diameter of arbitrary graphs is known to be NP-hard. To circumvent this computational intractability, we focus on specific classes of graphs for which this problem becomes tractable. This paper addresses the unexplored problem of the minimum strong diameter for \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\). We analyze two different conditions and present illustrative examples. Our simulations show a clear trend: for a fixed path length \(P_n\), increasing the value of parts in \(K_{m_1,m_2,\ldots,m_k}\) leads to a smaller and more concentrated minimum strong diameter, a result effectively validated by our numerical experiments.
The structure of this paper can be organized as follows. Section 2 presents the relevant lemmas, the main results, and an algorithm to find the minimum strong diameter of the strong product of a complete multipartite graph and a path. Section 3 provides application examples and analysis under three different order conditions for this minimum strong diameter. Section 4 summarizes the full paper.
Before presenting the main theorem of this section, we first state some essential lemmas for investigating the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\).
Lemma 2.1. [7] Let \(D\) be a strong orientation of a \(n\)-vertex graph. Then the minimum strong diameter satisfies: \[\begin{equation} \begin{aligned} sdiam(D)\le \left\lfloor \frac{5(n-1)}{3} \right\rfloor. \end{aligned} \end{equation} \tag{6}\]
Dankelmann et al. in [14] based on the relationship between connectivity \(k\) and girth \(g\), the minimum strong diameter of \(D\) can be simplified \(sdiam\left(D\right)\le\frac{5}{3}\left(1+\frac{\left(g-2\right)}{k}\right)\).
Lemma 2.2. [10] Let \(K_{m_1,m_2,…,m_k}\) be any complete multipartite graph with \(k\geq3\), \(m = \sum\limits_{i=1}^{k-1} m_i\), if \(m_k\geq 2\), then the minimum strong diameter of \(K_{m_1,m_2,…,m_k}\) is given by: \[\begin{equation} \begin{aligned} \text{sdiam}(K_{m_1, m_2, \ldots, m_k}) = \begin{cases} 4, & \text{if}\ \frac{m}{\left\lfloor \frac{m}{2} \right\rfloor} \geq m_k; \\\\ 5, & \text{if }\ \frac{m}{\left\lfloor \frac{m}{2} \right\rfloor} < m_k. \end{cases} \end{aligned} \end{equation} \tag{7}\]
Lemma 2.3. [7] Let \(D\) be a strongly oriented graph with order \(n\), and for any vertex \(u\) in \(D\), then the following holds: \[\begin{equation} \begin{aligned} se(u) \le srad(D) \le sdiam(D)\le 2srad(D). \end{aligned} \end{equation} \tag{8}\]
Here, \(srad(D)\) represents the minimum strong radius. We can obtain the strong diameter of the strong product graph \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\) is affected by the diameters of its subdigraphs. Given that \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\cong P_n\otimes K_{m_1,m_2,\ldots,m_k}\). In the following paper, we simplify the subsequent analysis by focusing on \(K_{m_1,m_2,\ldots,m_k}\otimes\ P_n\).
Lemma 2.4. [16] Let \((u,v)\) and \((u',v')\) be any two vertices in strong product graph \(G\otimes H\), among them, \((u,u')\) belongs to one any vertex in \(G\), and \((v,v')\) belongs to one any vertex in \(H\), then the distance between \((u,v)\) and \((u',v')\) satisfies: \[\begin{equation} \begin{aligned} d_{G\otimes H}((u,v),(u',v'))=max\ \{d_G(u,u'),d_H(v,v')\}. \end{aligned} \end{equation} \tag{9}\]
Liu [21] studied the strong product \(K_m\otimes K_n\) by partitioning its set of vertex into four regions and proposed two fundamental strong orientations for these regions. Inspired by this approach, we investigate strong orientations of the strong product between a complete multipartite graph and a path.
Now, we consider a non-trivial, simple, connected unoriented graph \(G\) and one of its strong orientations \(D\). For any vertex \(u\) in \(D\), the following inequality holds: \[\begin{equation} \begin{aligned} se(u)\le sdiam(D)\le sdiam(G). \end{aligned} \end{equation} \tag{10}\]
According to the above relationship, our objective is to determine the minimum strong diameter achievable by a strong orientation \(D\) of \(G\).
Theorem 2.5. Let \(K_{m_1,m_2,\ldots,m_k}\) be a complete multipartite graph and \(P_n\) be a path with \(k\geq3\), \(1<n\le5\), then the minimum strong diameter of \(K_{m_1,m_2,m_3,\ldots,m_k}\otimes P_n\) is: \[\begin{equation} \begin{aligned} sdiam(K_{m_1,m_2,\ldots,m_k}\otimes P_n)=2\max\{2,n-1\}. \end{aligned} \end{equation} \tag{11}\]
Proof. Assuming \(m = \sum\limits_{i=1}^{k} m_i\), the proof distinguishes two cases for the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\), based on the values of \(m\) and \(n\). These cases are discussed in the following.
Case 1. Let \(k\geq3\), \(m\equiv 0,1(mod\ 2)\), \(n\equiv 0,1(mod\ 2)\) and \(1<n\le 3\). Let \(D_1\) be the minimum strong oriented graph of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\). So, the vertex set of \(D_1\) can be represented as: \[\begin{equation} \begin{aligned} V(D_1)=\{(u,v)|1\le u \le m, 1\le v \le n\}, \end{aligned} \end{equation} \tag{12}\] where \(m = \sum\limits_{i=1}^k m_i\). Next, we will demonstrate Case 1 in 5 steps.
Step 1.1. Preliminary Results.
According to Lemma 2.1, the strong diameter of \(D_1\) satisfies: \[\begin{equation} sdiam(D_1) \le \left\lfloor \frac{5(mn – 1)}{3} \right\rfloor. \end{equation} \tag{13}\]
According to Lemma 2.2, the strong eccentricity of any vertex \((u,v) \in V(K_{m_1, m_2, \ldots, m_k} \otimes P_n)\) satisfies: \[\begin{equation} \begin{aligned} se(u,v) \geq 2 \ diam(K_{m_1, m_2, \ldots, m_k} \otimes P_n). \end{aligned} \end{equation} \tag{14}\]
Furthermore, the diameter of the product graph relates to its factors as: \[\begin{equation} \begin{aligned} diam(K_{m_1, m_2, \ldots, m_k} \otimes P_n) = \max \left\{ diam(K_{m_1, m_2, \ldots, m_k}), diam(P_n) \right\}. \end{aligned} \end{equation} \tag{15}\]
According to Lemma 2.3, the strong eccentricity for any vertex \((u,v) \in V(D_1)\) satisfies: \[\begin{equation} \begin{aligned} se(u,v) \le 2\ diam(K_{m_1, m_2, \ldots, m_k})=2\ diam(K_{m_1, m_2, \ldots, m_k} \otimes P_n)=4. \end{aligned} \end{equation} \tag{16}\]
Step 1.2. Strong Orientation Rules.
The edges of \(D_1\) are oriented according to the following rules for an arbitrary vertex \((u,v)\):
\(\bullet\) For \(u\equiv m\), and \(v\equiv 1(mod\ 2)\), orient \((m,v)\to (m-1,v)\);
\(\bullet\) For \(u\equiv m\), and \(v\equiv 0(mod\ 2)\), orient \((m-1,v)\to (m,v)\);
\(\bullet\) For \(u\equiv m-2\), and \(v\equiv 1(mod\ 2)\), orient \((m-2,v)\to (m-3,v)\);
\(\bullet\) For \(u\equiv m-2\), and \(v\equiv 0(mod\ 2)\), orient \((m-3,v)\to (m-2,v)\);
\(\bullet\) For \(1\le u \le \lfloor \frac{m}{2}\rfloor+1\), and \(v\equiv 1(mod\ 2)\), orient \((u,v)\to (u+1,v)\);
\(\bullet\) For \(1\le u \le \lfloor \frac{m}{2}\rfloor+1\), and \(v\equiv 0(mod\ 2)\), orient \((u,v)\to (u-1,v)\);
\(\bullet\) For \(\lfloor \frac{m}{2}\rfloor<u \le m-1\), and \(v\equiv 1(mod\ 2)\), orient \((u-\lfloor \frac{m}{2}\rfloor,v)\to (u,v)\);
\(\bullet\) For \(\lfloor \frac{m}{2}\rfloor<u \le m-1\), and \(v\equiv 0(mod\ 2)\), orient \((u,v)\to(u-\lfloor \frac{m}{2}\rfloor,v)\);
\(\bullet\) For \(u\equiv \lfloor \frac{m}{2}\rfloor+1\), and \(v\equiv 1(mod\ 2)\), orient \((m,v)\to(u,v)\), \((u,v)\to (\lfloor\frac{u}{2}\rfloor-1,v)\);
\(\bullet\) For \(u\equiv \lfloor \frac{m}{2}\rfloor+1\), and \(v\equiv 0(mod\ 2)\), orient \((u,v)\to (m,v)\), \((\lfloor\frac{u}{2}\rfloor-1,v)\to (u,v)\).
Step 1.3. Upper Bound on Strong Eccentricity.
Let \(S\) be a proper subset of \(V(D_1)\), and denote \(\overline{S} = V(D_1) \setminus S\). Let \(P_1 = \{(u,v), \ldots, \\ (u_1,v_1), (u_2,v_2) \mid [u_1,u_2] \neq u; [v_1,v_2] \neq v\}\) be a minimum oriented path from \((u,v)\) to \(\overline{S}\). It is clear that \((u_1,v_1) \in S\) and \((u_2,v_2) \in \overline{S}\), and the segment \(\{(u,v),(u_1,v_1)\}\) of \(P_1\) must be a minimum oriented path. Therefore, the strong distance from \((u,v)\) to \((u_2,v_2)\) in \(D_1\) satisfies: \[\begin{equation} sd_{D_1}((u,v), (u_2,v_2)) = sd_{D_1}((u,v), (u_1,v_1)) + sd_{D_1}((u_1,v_1), (u_2,v_2)). \end{equation} \tag{17}\]
The minimum strong oriented distance from \((u,v)\) to \(\overline{S}\) satisfies: \[\begin{align} sd_{D_1}((u,v), \overline{S}) =& \min_{(u,v) \in S} \{ sd_{D_1}((u,v), S) \} + \min_{(u_2,v_2) \in \overline{S}} \{ sd_{D_1}(S, (u_2,v_2) \} \notag\\ <& 2 \ diam(K_{m_1, m_2, \ldots, m_k}). \end{align} \tag{18}\]
From the construction of \(D_1\), one can show that any two vertices in the same layer or adjacent layers are within a bounded strong distance. A detailed case analysis yields: \[\begin{equation} {sd}_{D_1}((u,v), \overline{S}) < 2\ diam(K_{m_1,m_2,\ldots,m_k}\otimes P_n) = 4. \end{equation} \tag{19}\]
Since this holds for any \(S\) and any \((u,v) \in S\), it follows that the strong eccentricity of any vertex is at most 4: \[\begin{equation} \operatorname{se}(u,v) \leq 4 | (u,v) \in V(D_1). \end{equation} \tag{20}\]
Step 1.4. Lower Bound and Tightness on Strong Distance.
We now show that the bound of the strong distance in \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\) is tight. Consider two vertices \((u_1, v_1)\) and \((u_2, v_2)\) chosen as follows:
a) \(u_1\) and \(u_2\) are in the same partite set of \(K_{m_1,m_2,\ldots,m_k}\), so they are not adjacent in \(K_{m_1,m_2,\ldots,m_k}\),
b) \(v_1\) and \(v_2\) are the endpoints of the path \(P_n\).
In the underlying graph of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\), the distance between \((u_1, v_1)\) and \((u_2, v_2)\) is: \[\begin{align} d_{K_{m_1,m_2,\ldots,m_k} \otimes P_n}((u_1,v_1), (u_2,v_2)) =& \max \{ d_{K_{m_1,m_2,\ldots,m_k}}(u_1,u_2),\ d_{P_n}(v_1,v_2) \} \notag\\ =& \max \{ 2,\ n-1 \}. \end{align} \tag{21}\]
For \(1<n\le 3\), the distance of \((v_1,v_2)\) is at least 2. However, according to the specific orientation rules in \(D_1\), any oriented path from \((u_1, v_1)\) to \((u_2, v_2)\) must traverse at least 4 edges. This can be verified by checking all possible paths under the orientation rules, leading to: \[\begin{equation} {sd}_{D_1}((u_1,v_1), (u_2,v_2)) \geq 4. \end{equation} \tag{22}\]
Hence, the strong diameter of \(D_1\) is at least 4. Combined with the upper bound of the strong eccentricity and the lower bound of the strong distance, we conclude: \[\begin{equation} \operatorname{sdiam}(D_1) = 4, \operatorname{se}(u,v) = 4| (u,v)\in V(D_1). \end{equation} \tag{23}\]
Since \(D_1\) is the minimum strong orientation of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\), the minimum strong diameter over all strong orientations is at most 4. But since we have exhibited an orientation with strong diameter exactly 4, it follows that: \[\begin{equation} \operatorname{sdiam}(K_{m_1, \ldots, m_k} \otimes P_n) = 4. \end{equation} \tag{24}\]
Step 1.5. Example.
As shown in Figure 3, the graph \(K_{1,2,4} \otimes P_3\) illustrates this result. Here, \(m = 7\), \(n = 3\), the red arrow represents the edge orientation that satisfies the orientation rule. Applying the orientation rules above yields a strong orientation where the maximum strong distance between any two vertices is 4, and every vertex has a strong eccentricity 4, confirming Case 1.
Case 2. Let \(k\geq3\), \(m\equiv 0,1(mod\ 2)\), \(n\equiv 0,1(mod\ 2)\) and \(3<n\le 5\). Let \(D_2\) be the minimum strong oriented graph of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\). The vertex set classification of \(D_2\) is similar to that of Case 1. Demonstrate Case 2 in 4 steps.
Step 2.1. Preliminary Results and Strong Orientation Rules.
According to Lemma 2.3, the strong eccentricity for any vertex \((u,v) \in V(D_1)\) satisfies: \[\begin{equation} \begin{aligned} se(u,v) \le 2\ diam(P_n)=2\ diam(K_{m_1, m_2, \ldots, m_k} \otimes P_n)=2\ (n-1). \end{aligned} \end{equation} \tag{25}\]
The edges of \(D_2\) are oriented according to the following rules for an arbitrary vertex \((u,v)\):
\(\bullet\) For \(u\equiv 1\), and \(1\le v\le \lfloor \frac{n}{2}\rfloor\), orient \((1,v)\to (\lfloor\frac{m}{2}\rfloor,v)\);
\(\bullet\) For \(u\equiv 1\), and \(\lfloor \frac{n}{2}\rfloor\le v \le n\), orient \((\lfloor\frac{m}{2}\rfloor,v)\to (1,v)\);
\(\bullet\) For \(u\equiv \lfloor \frac{m}{2}\rfloor\), \(1\le v\le \lfloor \frac{n}{2}\rfloor\), orient \((u,v)\to (m-1,v)\);
\(\bullet\) For \(u\equiv \lfloor \frac{m}{2}\rfloor\), and \(\lfloor \frac{n}{2}\rfloor <v \le n\), orient \((u,v)\to (\lfloor \frac{m}{2}\rfloor,v)\);
\(\bullet\) For \(u\equiv \lfloor \frac{m}{2}\rfloor\), and \(1\le v \le n-1\), orient \((\lfloor \frac{u}{2}\rfloor,v)\to (u,v)\);
\(\bullet\) For \(u\equiv \lfloor \frac{m}{2}\rfloor\), and \(\lfloor \frac{n}{2}\rfloor<v\le n\), orient \((m-1,v)\to (u,v)\);
\(\bullet\) For \(1\le u \le m\), and \(1\le v\le \lfloor \frac{n}{2}\rfloor\), orient \((u,v)\to (u+1,v)\);
\(\bullet\) For \(1\le u \le m\), and \(\lfloor \frac{n}{2}\rfloor\le v\le n\), orient \((u,v)\to (u-1,v)\);
\(\bullet\) For \(u\equiv 1(mod\ 2)\), and \(v\equiv1(mod\ 2)\), orient \((u,v)\to (u+2,v)\);
\(\bullet\) For \(u\equiv 0(mod\ 2), u\neq 2\), and \(1\le v \le \lfloor \frac{n}{2}\rfloor\), orient \((u,v)\to (\lfloor \frac{u}{2}\rfloor,v)\);
\(\bullet\) For \(u\equiv 0(mod\ 2), u\neq 2\), and \(\lfloor \frac{n}{2}\rfloor\le v \le n\), orient \((\lfloor \frac{u}{2}\rfloor,v)\to (u,v)\);
\(\bullet\) For \(u\equiv 1(mod\ 2)\), and \(v\equiv0(mod\ 2)\), orient \((u,v)\to (u+1,v-1)\);
\(\bullet\) For \(u\equiv 1(mod\ 2), u\neq 1, 1\le u\le \lfloor \frac{m}{2}\rfloor\), and \(1\le v \le \lfloor \frac{n}{2}\rfloor\), orient \((u,v)\to (2u-1,v)\);
\(\bullet\) For \(u\equiv 1(mod\ 2), u\neq 1, 1\le u\le \lfloor \frac{m}{2}\rfloor\), and \(\lfloor \frac{n}{2}\rfloor\le v \le n\), orient \((2u-1,v)\to (u,v)\).
Step 2.2. Upper Bound on Strong Eccentricity.
Let \(T\) and \(\overline{T}\) be two different sets of vertex \(V(D_2)\), suppose there are three different vertices \((u,v)\), \((u_3,v_3)\) and \((u_4,v_4)\), respectively expressed as: \[\begin{equation} \begin{aligned} T=\{(u,v),(u_3,v_3)\}; \overline{T}=\{V(D_2)\backslash T\}. \end{aligned} \end{equation} \tag{26}\]
For the set \(T\), the minimum strong oriented distance from \((u,v)\) to \((u_3,v_3)\) satisfies: \[\begin{equation} \begin{aligned} sd_{D_2}((u,v), (u_3,v_3)) < 2 \ diam(P_n). \end{aligned} \end{equation} \tag{27}\]
The minimum strong oriented loop distance from \((u,v)\) back to itself satisfies: \[\begin{align} sd_{D_2}((u,v), (u,v)) =& \min_{(u_3,v_3) \in T} \{ sd_{D_2}((u,v), (u_3,v_3)) \} + \min_{(u_4,v_4) \in \overline{T}} \{ sd_{D_2}((u_3,v_3), (u_4,v_4) \} \notag\\ \le& 2 \ diam(P_n). \end{align} \tag{28}\]
From the construction of \(D_2\) and the strong distance between any of the vertices mentioned above, the strong strong eccentricity of any vertex \((u,v)\) is at most \(2(n-1)\): \[\begin{equation} {se}(u,v) \leq 2(n-1) | (u,v) \in V(D_2). \end{equation} \tag{29}\]
Step 2.3. Lower Bound and Tightness on Strong Distance.
We now show that the bound of the strong distance in \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\) is tight. Consider two vertices \((u_3, v_3)\) and \((u_4, v_4)\) chosen as follows:
a) \(u_3\) and \(u_4\) are in the different partite set of \(K_{m_1,m_2,\ldots,m_k}\), so they are adjacent in \(K_{m_1,m_2,\ldots,m_k}\),
b) \(v_3\) and \(v_4\) are the endpoints of the path \(P_n\).
In the underlying graph of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\), the distance between \((u_3, v_3)\) and \((u_4, v_4)\) is: \[\begin{equation} d_{K_{m_1,m_2,\ldots,m_k} \otimes P_n}((u_3,v_3), (u_4,v_4)) = \max \{ d_{K_{m_1,m_2,\ldots,m_k}}(u_3,u_4),\ d_{P_n}(v_3,v_4) \} =2\ (n-1). \end{equation} \tag{30}\]
For \(3<n\le 5\), according to the specific orientation rules in \(D_2\), any oriented path from \((u_3,v_3)\) to \((u_4,v_4)\) satisfies: \[\begin{equation} {sd}_{D_2}((u_3,v_3), (u_4,v_4)) \geq 2\ (n-1). \end{equation} \tag{31}\]
Combined with the upper bound of the strong eccentricity and the lower bound of the strong distance, we conclude: \[\begin{equation} \operatorname{sdiam}(D_2) = 2\ (n-1), \operatorname{se}(u,v) = 2\ (n-1)| (u,v)\in V(D_2). \end{equation} \tag{32}\]
Step 2.4. Example.
As shown in Figure 4, the graph \(K_{1,2,3} \otimes P_4\) illustrates this result. Here, \(m = 6\), \(n = 4\), the red arrow represents the edge orientation that satisfies the orientation rule. Applying the orientation rules above yields a strong orientation where the maximum strong distance between any two vertices is 4, and every vertex has a strong eccentricity 4, confirming Case 2.
Therefore, according to above analysis, we can obtain: \[\begin{equation} \operatorname{sdiam}(K_{m_1, \ldots, m_k} \otimes P_n) = 2(n-1). \end{equation} \tag{33}\]
In summary, form Case 1 to Case 2 and formulas (11) to (33). We have analyzed and discussed two different conditions of the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\). In the following content, we will continue to investigate the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\) when \(n\) is greater than 5. Proof is complete. ◻
Theorem 2.6. Let \(K_{m_1,m_2,\ldots,m_k}\) be a complete multipartite graph and \(P_n\) be a path with \(k\geq3\), \(n>5\), then the lower and upper bounds of minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k}\\ \otimes P_n\) are:
\[\begin{equation} \label{eq34} 8<sdiam\left(K_{m_1,m_2,..,m_k}\otimes P_n\right)\le 2(n-1). \end{equation} \tag{34}\]
Proof. Let \(k\geq3\), \(n\equiv\ 0 \ 1\ (mod\ 2)\ and\ n>5\), \(m = \sum\limits_{i=1}^{k} m_i\). Let \(D_{3}\) be the minimum strong oriented graph of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\). Demonstrate Theorem 2.6 in 4 steps.
Step 1. Strong Orientation Rules.
Since the set of vertices of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\) are symmetric, the set of vertices of \(D_{3}\) can be divided into two parts, respectively: \[\begin{align} DO_1=&\{\left(u, v\right)|1\le u\le \lfloor \frac{m}{2}\rfloor,1\le v\le\left\lfloor\frac {n}{2}\right\rfloor\};\notag \\DO_2=&\{\left(u,v\right)|\lfloor \frac{m}{2}\rfloor \le i\le m,\left\lceil\frac{n}{2}\right\rceil\le j\le n\}. \end{align} \tag{35}\]
The edges of \(D_3\) are oriented according to the following rules for an arbitrary vertex \((u,v)\) in \(V(DO_1)\) and \(V(DO_2)\):
\(\bullet\) For \(1\le u \le \lfloor \frac{m}{2}\rfloor\), and \(1\le v \le \lfloor \frac{n}{2}\rfloor\), orient \((m,v)\to (u,v)\);
\(\bullet\) For \(\lfloor \frac{m}{2}\rfloor\le u \le m\), and \(v\equiv 1(mod\ 2)\), orient \((u,v)\to (m,v)\);
\(\bullet\) For \(1\le u \le \lfloor \frac{m}{2}\rfloor\), and \(v\equiv 1(mod\ 2)\), orient \((u,v)\to (\lfloor\frac{m}{2}\rfloor,v)\);
\(\bullet\) For \(\lfloor \frac{m}{2}\rfloor \le u \le m\), and \(\lfloor \frac{n}{2}\rfloor\le v \le n\), orient \((\lfloor\frac{m}{2}\rfloor,v)\to (u,v)\);
\(\bullet\) For \(u\equiv \lfloor \frac{m}{2}\rfloor\), and \(1\le v \le \lfloor \frac{n}{2}\rfloor\), orient \((\lfloor \frac{m}{2}\rfloor,v)\to (\lfloor \frac{m}{2}\rfloor +1,v)\);
\(\bullet\) For \(u\equiv \lfloor \frac{m}{2}\rfloor\), and \(\lfloor \frac{n}{2}\rfloor\le v \le n\), orient \((\lfloor \frac{m}{2}\rfloor +1,v)\to (\lfloor \frac{m}{2}\rfloor,v)\);
\(\bullet\) For \(u\equiv 1(mod \ 2)\), and \(v\equiv 1(mod\ 2)\), orient \((u,v)\to (u+1,v+1)\);
\(\bullet\) For \(u\equiv 0(mod\ 2)\), and \(v\equiv 0(mod\ 2)\), orient \((u,v)\to (u-1,v-1)\);
\(\bullet\) For \(1\le u \le \lfloor \frac{m}{2}\rfloor\), and \(1\le v <\lfloor \frac{n}{2}\rfloor\), orient \((u,v)\to (u+1,v)\), \((u,v)\to (u,v+1)\);
\(\bullet\) For \(\lfloor \frac{m}{2}\rfloor\le u \le m\), and \(\lfloor \frac{n}{2}\rfloor<v\le n\), orient \((u,v)\to(u-1,v)\), \((u,v)\to (u,v-1)\);
\(\bullet\) For \(u\equiv 1\), and \(1\le v\le n\), orient \((1,v)\to (2,v+1)\to (3,v)\to \ldots\to(m,v)\to (1,v+1)\to (2,v)\to (3,v+1)\to \ldots \to (m-1,v)\to (m,v+1)\to (1,v)\);
\(\bullet\) For \(1\le u \le m\), and \(1\le v \le n\), orient \((u,v)\to (u+1,v)\to (\lfloor\frac{3m}{2}\rfloor,v)\to (m,v)\to (\lfloor\frac{m}{2}\rfloor,v+1)\to \ldots\to (\lfloor\frac{m}{2}\rfloor+\lfloor\frac{3m}{2}\rfloor,v)\to (m,v+1)\to (m-\lfloor \frac{u}{2}\rfloor,v)\to (u,v)\).
Step 2. Prove that the Lower Bound is Strict.
According to Lemma 2.2 and the definition of diameter, when \(n>5\), there exists: \[\begin{align} diam(P_n)>&diam(K_{m_1,m_2,\ldots,m_k})=2;\notag\\ diam(K_{m_1,m_2,\ldots,m_k}\otimes P_n)=&diam(P_n)=n-1. \end{align} \tag{36}\]
We can obtain the diameter of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\) depends on the length of the path \(P_n\), \(n>5\), so \(2diam(P_n)>8\).
The strong eccentricity for any vertex \((u,v)\in V(D_3)\) satisfies: \[\begin{equation} \begin{aligned} 8<se(u,v)\le 2\ diam(P_n). \end{aligned} \end{equation} \tag{37}\]
Therefore, according to the above analysis and the definition of minimum diameter, it can be concluded that \(sdiam(K_{m_1,m_2,\ldots,m_k}\otimes P_n)>8\) is strict.
Step 3. Prove that the Upper Bound is Sharp.
Let \(J\) be a proper subset of \(V(D_3)\), and denote \(\overline{J} = V(D_3) \setminus J\). Let \(P_3 = \{(u,v), \ldots, \\ (u_5,v_5), (u_6,v_6) \mid [u_5,u_6] \neq u; [v_5,v_6] \neq v\}\) be a minimum oriented path from \((u,v)\) to \(\overline{J}\). It is clear that \((u_5,v_5) \in J\) and \((u_6,v_6) \in \overline{J}\), and the segment \(\{(u,v),(u_5,v_5)\}\) of \(P_3\) must be a minimum oriented path.
According to the results proven in step 2 and the definition of diameter, for any vertex \((u,v)\in V(D_3)\), the strong eccentricity satisfies: \[\begin{equation} \begin{aligned} 8<se(u,v)\le 2\ (n-1). \end{aligned} \end{equation} \tag{38}\]
From the construction of \(D_3\), the minimum strong orientation distance \(P_3\) is satisfied: \[\begin{align} {sd(P_3)} =& \min_{({u_5},{u_5}) \in J} \{ {sd_{D_3}((u,v),({u_5},{v_5}))}\}+\min_{({u_6},{v_6}) \in \overline{J}} \{ {sd_{D_3}((u_5,v_5),({u_6},{v_6}))}\} \notag \\ \le& se({u},{v})\le 2diam(P_n)=2(n-1). \end{align} \tag{39}\]
Thus, through the above analysis, it can be obtained that in \(D_{3}\), for any vertex \((u,v)\in V(D_3)\), the relationship between \(se(u,v)\), \(diam\left(D_{3}\right)\), \(sdiam\left( D_{3}\right)\), \(diam\left(P_n\right)\) can be summarized: \[\begin{equation} \begin{aligned} 8<2\ diam(P_n) \le 2\ diam(D_{3})< se(u,v) \le sdiam(D_{3})\le 2(n-1). \end{aligned} \end{equation} \tag{40}\]
Therefore, according to above analysis, we can obtain: \[\begin{equation} \label{eq41} 8<sdiam(K_{m_1,m_2,\ldots,m_k}\otimes P_n)\le 2(n-1). \end{equation} \tag{41}\]
We can concluded that \(sdiam(K_{m_1,m_2,\ldots,m_k}\otimes P_n)\le 2\ (n-1)\) is sharp.
Step 4. Example
As shown in Figure 5, the graph \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\) illustrates this result, the red arrow represents the edge orientation that satisfies the orientation rule. Here, \(m_1\) to \(m_k\), and \(n\) be both real number. Applying the orientation rules above yields a strong orientation where the maximum strong distance between any two vertices is 8 to \(2\ (n-1)\), and every vertex has a strong eccentricity 8 to \(2\ (n-1)\), confirming the Theorem 2.6.
In summary, according to the formulas (34) to (41) and proof process, the main results of this theorem can be easily obtained. Proof is complete. ◻
Following Theorems 2.5 and 2.6 on the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\), we state two corollaries. These can reveal structural insights by considering two extremes: firstly, when the multipartite graph becomes a complete graph \(K_k\), our result contains Liu’s [21] on \(K_k\) as a special case; secondly, when it reduces to a path \(P_n\), the problem simplifies to finding the strong diameter of \(P_n\).
Corollary 2.7. Let \(K_{k}\) be any complete graph, \(P_n\) be any path, \(k\) and \(n\) be both any real number, then the lower and upper bounds of minimum strong diameter of \(K_k \otimes P_n\) are: \[\begin{equation} \label{eq42} 2\le sdiam(K_{k}\otimes P_n)\le 2(n-1). \end{equation} \tag{42}\]
Proof. Let \(D_{4}\) be the minimum strong oriented graph of \(K_k\otimes P_n\). Since the set of vertices of \(K_{k} \otimes P_n\) is symmetric, the set of vertices of \(D_{4}\) is respectively:
\[\begin{align} DE_1=&\left\{\left(u,v\right)|1\le u\le k,1\le v\le\left\lceil\frac {n}{2}\right\rceil\right\};\notag\\ DE_2=&\left\{\left(u,v\right)|1\le u\le k,\left\lceil\frac{n}{2}\right\rceil\le v\le n\right\}. \end{align} \tag{43}\]
According to Lemma 2.1, it can obtained: \[\begin{equation} \begin{aligned} sdiam(D_{4})\le \left\lfloor \frac{5(kn-1)}{3} \right\rfloor. \end{aligned} \end{equation} \tag{44}\]
According to Liu’s method in [21], \(K_{k} \otimes P_n\) is strongly oriented, after completing the strong orientation of \(D_{4}\), it is found that for any vertex \((u,v)\in V(D_4)\), the \(sdiam(K_{k}\otimes P_n)\) and \(se(u,v)\) can be concluded: \[\begin{equation} \label{eq45} 2\le se(u,v)\le sdiam(D_4) \le sdiam(K_{k}\otimes P_n) \le 2\ (n-1). \end{equation} \tag{45}\]
According to formulas (42) to (45) and the proof process, the main results of this theorem can be easily obtained. Proof is complete. ◻
Corollary 2.8. Let \(P_n\) be any path, then the minimum strong diameter of the path is \(n-1\).
Corollary 2.8 generalizes Yue’s findings on the strong product of two paths [26, 27], establishes a basis for obtaining the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\). To further elucidate the strong diameter of a path itself, Figure 6 illustrates its strong diameter for paths with an odd and an even number of vertices.
Having established the theoretical value and bounds and the method for obtaining the minimum strong diameter of the strong product graph \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\) through the above theorems and corollaries, we now formalize this procedure into an algorithm.
This algorithm calculate the minimum strong diameter of a strong product graph through six main steps.
\(\bullet\) Graph Construction: The algorithm firstly constructs the strong product graph \(G=K_{m_1,m_2,\ldots,m_k}\otimes P_n\) of a complete multipartite graph \(K_{m_1,m_2,\ldots,m_k}\) and a path \(P_n\), creating a structure with three types of edges: multipartite edges within layers, horizontal path edges, and diagonal product edges.
\(\bullet\) Strong Orientation: Applying a systematic strongly orientation rule from Theorem 2.6 to the unoriented graph \(G\) yields a strongly connected oriented graph \(D\).
\(\bullet\) Strong Distance Calculation: This phase computes the strong distance matrix, defined as the value of the smallest strongly connected subgraph containing any two vertices. The algorithm first finds all strongly connected components (SCCs), then refines distance estimates by examining all SCCs that contain each pair of vertex.
\(\bullet\) Strong Eccentricity Calculation: For each vertex, the algorithm calculates its strong eccentricity as the maximum strong distance to any other vertex in the graph.
\(\bullet\) Minimum Diameter Determination: The minimum strong diameter is found by identifying the minimum strong eccentricity among all vertices.
\(\bullet\) Result Return: The calculated minimum strong diameter value is returned as the final result.
According to the analysis of each step of the algorithm above, we can conclude that the time complexity of the entire algorithm is \(O(X^2n^2)\), where \(X= \sum\limits_{i=1}^{k} m_i\). We have verified the accuracy of the algorithm.
This paper constructs and analyzes the strong product graph of \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\) . Our main contributions are: (1) deriving the specific value and lower and upper bounds for its minimum strong diameter under two different conditions; (2) showing that this product preserves key structural properties of its components; (3) demonstrating, through a comparison of different configurations, that a larger order of the complete multipartite factor leads to a smaller minimum strong diameter. The focus of the next chapter is on examples and experiment simulation.
Before comparing the advantages of different orders of \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\), it is necessary to calculate different orders of the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\). The traditional method of calculating the minimum strong diameter is used. It involves first determining the degree of each vertex in the graph and then comparing to find the strong diameter of each strong oriented graph. If use the traditional method to calculate the strong diameter, the problem of finding the strong diameter would be very difficult. Therefore, in order to simplify the problem. As the strong product retains the characteristics of factor graphs. Some large graph difficulties into problems of their factor graphs can be converted.
To illustrate the structure of the strong product \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\), we construct a specific example, \(K_{2,1,2} \otimes P_3\), as shown in Figure 7. This visualization clearly reveals the connectivity and subgraph composition of the product. The order of this construction is given exactly by \(|V(K_{m_1,m_2,\ldots,m_k} \otimes P_n)| = (m_1 + m_2 + \ldots + m_k) \times n\). By analyzing the structural properties of the factors and applying the bounds established in our theorems, we can constrain the minimum strong diameter of this product graph. For the case presented in Figure 7, this yields \(4 \le sdiam(K_{2,1,2} \otimes P_3) \le 4\). Based on the the specific value of \(sdiam(K_{m_1,m_2,\ldots,m_k})\) and order constraint, the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\) can be obtained, denoted by \(4\le sdiam(K_{m_1,m_2,\ldots,m_k}\otimes P_n) \le 2(n-1)\).
| Order of \(P_n\) | \(K_{m_1,m_2,\ldots,m_8}\otimes P_n\) | \(K_{m_1,m_2,\ldots,m_6}\otimes P_n\) | \(K_{m_1,m_2,\ldots,m_4}\otimes P_n\) |
|---|---|---|---|
| \(n=5\) | \(4\) | \(5\) | \(6\) |
| \(n=12\) | \(5\) | \(10\) | \(12\) |
| \(n=15\) | \(10\) | \(15\) | \(22\) |
| \(n=20\) | \(16\) | \(24\) | \(30\) |
| \(n=22\) | \(21\) | \(28\) | \(39\) |
| \(n=24\) | \(24\) | \(34\) | \(43\) |
| \(n=26\) | \(27\) | \(37\) | \(45\) |
| \(n=28\) | \(30\) | \(40\) | \(52\) |
| \(n=30\) | \(32\) | \(43\) | \(56\) |
| \(n=32\) | \(34\) | \(46\) | \(59\) |
According to calculation method of the minimum strong diameter of the strong product graph \(K_{m_1,m_2,\ldots,m_k}\otimes P_n\). Comparing the three different orders of complete bipartite graphs and paths, respectively: (1) \(sdiam(K_{m_1,m_2,\ldots,m_8}\otimes P_n)\); (2) \(sdiam(K_{m_1,m_2,\ldots,m_6}\otimes P_n)\); (3) \(sdiam(K_{m_1,m_2,\ldots,m_4}\otimes P_n)\). As shown in Table 1, the comparison data table is made, the specific value of the minimum strong diameter of \(K_{m_1,m_2,\ldots,m_8}\otimes P_n\), \(K_{m_1,m_2,\ldots,m_6}\otimes P_n\) and \(K_{m_1,m_2,\ldots,m_4}\otimes P_n\) are established. According to the the specific value of minimum strong diameter with three different cases in Table 1, as shown in Figure 8, the curve data of the minimum strong diameter of three different conditions are constructed. Then, by comparing the values of the curve data, it can be found that the minimum strong diameter of the strong product of \(K_{m_1,m_2,\ldots,m_8}\otimes P_n\) is obviously smaller than other two strong products.
Therefore, according to the specific value in Table 1 and the curve data changes of the three different minimum strong diameter. In order to intuitively discover the difference between \(K_{m_1,m_2,\ldots,m_8}\otimes P_n\) and \(K_{m_1,m_2,\ldots,m_4}\otimes P_n\). As shown in Figure 9 and Figure 10, the minimum strong diameter of two different strong product three-dimensional graphs are constructed. By comparing the minimum strong diameter of the three-dimensional graph, the strong product of \(K_{m_1,m_2,\ldots,m_8}\otimes P_n\) is closer to a simple graph. At the same time, the data change on the three-dimensional graph, it can be clearly found that the strong product of \(K_{m_1,m_2,\ldots,m_8}\otimes P_n\) three-dimensional graph has more concentrated data.
In summary, our experimental analyses demonstrate that increasing the order of the complete multipartite graph reduces the minimum strong diameter of the product graph \(K_{m_1,m_2,\ldots,m_k} \otimes P_n\). If we want to explore more accurate data, we can choose higher-order fully complete multipartite graphs, this key insight enables the optimization of product topologies.