Fault Diameter of Strong Product Graph of Two Paths

Abstract

Strong product is an efficient method to construct large networks from small networks. Fault diameter is an important parameter to measure the fault tolerance and effectiveness of interconnection networks. In this paper, we first determine the vertex fault diameter of the strong product graph of two paths by constructing the internally vertex-disjoint paths between any two vertices in the graph, then we determine the edge fault diameter of the strong product graph of two paths by constructing the edge-disjoint paths between any two vertices in the graph. In addition, we propose an improved mesh network, whose model composed of strong product graph of two paths and has many excellent characteristics.

Supported by the National Natural Science Foundation of China (11551002), and Natural Science Foundation of Qinghai Province (2019-ZJ-7093).

1 Introduction

All graphs considered in this paper are simple and undirected graphs with neither loops nor multiple edges. Let G be a graph with vertex set V(G) and edge set E(G), we use v(G) to denote the order of G. Let R be a path in G, the length of the path R is $v(R)-1$ and denoted by L(R). If G is a path, we denote it by P. Let x and y be any two vertices in G, we use (x, y) denotes the edge connects x and y. The length of the shortest path between x and y in G is called the distance between x and y, which is denoted by d(G; x, y). Then the diameter of G is the maximum length of all distances between any two vertices in G, denoted by d(G). The connectivity of G is the minimum cardinality of all vertex subsets in G which are deleted from G to obtain a unconnected or a trivial graph, denoted by $\kappa (G)$. Similarly, the edge connectivity of G is the minimum cardinality of all edge subsets in G which are deleted from G to obtain a unconnected or a trivial graph, denoted by $\lambda (G)$. We use $\delta (G)$ denote the minimum degree of G. A graph G is called maximally connected graph, if $\kappa (G)=\delta (G)$. We can get that a path P is a maximally connected graph with $\kappa (P)=\lambda (P)=\delta (P)=1$. In addition, the definitions of strong product, vertex fault diameter and edge fault diameter are given below.

Definition 1

Let $G_1=(V(G_1),E(G_1))$, $G_2=(V(G_2),E(G_2))$, the strong product of $G_1$ and $G_2$ is denoted by $G_1\boxtimes G_2$ and the vertex set is $V(G_1)\times V(G_2)$. Any two distinct vertices $x_1y_1$ and $x_2y_2$ in $G_1\boxtimes G_2$ are adjacent, if and only if $x_1=x_2$ and $(y_1,y_2)\in E(G_2)$, or $y_1=y_2$ and $(x_1,x_2)\in E(G_1)$, or $(x_1,x_2)\in E(G_1)$ and $(y_1,y_2)\in E(G_2)$.

In this paper, we mainly consider such a class of strong product graph $P_m\boxtimes P_n$, where $P_m\boxtimes P_n$ denotes the strong product graph of a path with order $m\ge 2$ and a path with order $n\ge 2$. The strong product graph $P_3\boxtimes P_7$ is shown on Fig. 1.

Fig. 1.

The strong product graph $P_3\boxtimes P_7$.

Definition 2

Let G be a w-connected graph, and the faulty vertex set of G is denoted by F with $\left| F \right| <w$. The $(w-1)$-vertex fault diameter of a graph G is defined as

$$D_w(G)=max\{d(G-F):F\subset V(G),\left| F\right| <w\}.$$

In the worst case, we can get $|F|=w-1$. Therefore, for any w-connected graph G, the relation between diameter and vertex fault diameter holds

$$d(G)=D_1(G)\le D_2(G)\le \cdots \le D_{w-1}(G)\le D_w(G).$$

Definition 3

Let G be a t-edge connected graph, and the faulty edge set of G is denoted by F with $\left| F \right| <t$. The $(t-1)$-edge fault diameter of a graph G is defined as

$$D^{'}_t(G)=max\{d(G-F):F\subset E(G),\left| F\right| <t\}.$$

In the worst case, we can get $|F|=t-1$. Therefore, for any t-edge connected graph, the relation between diameter and edge fault diameter holds

$$d(G)=D^{'}_1(G)\le D^{'}_2(G)\le \cdots \le D^{'}_{t-1}(G)\le D^{'}_t(G).$$

The concept of strong product was first proposed in [1]. It is an efficient product method of constructing large graphs from small graphs, and the constructed strong product graphs retain many properties of subgraphs. Among them, there are many important results in the research on the connectivity and edge connectivity of strong product graphs. The lower bound of the connectivity of strong product graphs was first given in [2]. Then in [3], the edge connectivity of strong product graphs of two nontrivial connected graphs was determined, and the connectivity of strong product graphs of two maximally incomplete connected graphs was given. Later, the connectivity of strong product graphs was determined in [4]. There are also some recent results about product graphs in [5,6,7].

The topological structure of interconnection network is a graph, with its processors represented by vertices and links represented by edges. Especially, the diameter is used to indicate the transmission delay of interconnection network. In the network, if vertices or edges work for a long time, they will inevitably be faulty. After they are faulty, the information transmission of the network will be affected. Therefore, the network must have high fault tolerance and high effectiveness to reduce this impact as much as possible. The fault diameter is an important parameter to measure these properties, which includes vertex fault diameter and edge fault diameter. However, it is extremely difficult to determine the fault diameter in the actual network, so the compact upper bounds of the fault diameter of a general graph are given in [8, 9]. But for some well-known networks, the fault diameter can be determined. The vertex fault diameters of kautz network and debrujin network are given in [10, 11], the vertex fault diameters of pyramid network and star graph are determined in [12, 13], and the edge fault diameter of hypercube network is given in [14]. There are also some recent results in [15, 16].

Although many important results of the fault diameter of Cartesian product graphs are given in [17,18,19], for the fault diameter of strong product graphs, there are no relevant results. In this paper, we will start with a special class of strong product graph and give the determined vertex fault diameter and edge fault diameter. The vertex fault diameter of the strong product graph of two paths is first determined by constructing the internally vertex-disjoint paths between any two vertices in the graph, then we determine the edge fault diameter of the strong product graph of two paths by constructing the edge-disjoint paths between any two vertices in the graph. In addition, we propose an improved network model composed of the strong product graph of two paths, and compare it with the mesh network widely used in parallel computing systems.

2 Main Results

In order to prove the following results, we first specify the representation of the paths. Let $G=P_m\boxtimes P_n$, $x_hy_g$ and $x_py_q$ are any two vertices in G, where $x_h,x_p\in V(P_m)$ and $y_g,y_q\in V(P_n)$. The path $R_1$ from vertex $x_h$ to vertex $x_p$ in $P_m$ and its edge set is $E(R_1)=\{(x_i,x_{i+1}): i=h,\cdots ,p-1\}$, which can be expressed as $R_1: x_h\rightarrow \cdots \rightarrow x_p$. The path $R_2$ from vertex $y_g$ to vertex $y_q$ in $P_n$ and its edge set is $E(P_n)=\{(y_j,y_{j+1}): j=g,\cdots ,q-1 \}$, which can be expressed as $R_2: y_g\rightarrow \cdots \rightarrow y_q$. If $x_h=x_p$, then the path $x_hR_2$ connects vertex $x_hy_g$ and vertex $x_hy_q$ in G and its edge set is $E(x_hR_2)=\{(x_h,y_j): j=g,\cdots ,q-1\}$, which we express here as $x_hy_g\rightarrow \cdots \rightarrow x_hy_q$. Similarly, if $y_g=y_q$, then the path $R_1y_g$ connects vertex $x_hy_g$ and vertex $x_py_g$ in G and its edge set is $E(R_1y_g)=\{(x_i,y_g): i=h,\cdots ,p-1\}$, which we express here as $x_hy_g\rightarrow \cdots \rightarrow x_py_g$. If $x_h\ne x_p$ and $y_g\ne y_q$, then the path $R_3$ connects vertex $x_hy_g$ and vertex $x_py_q$ in G and its edge set is $E(R_3)=\{(x_i,y_j): i=h,\cdots ,p-1, j=g,\cdots ,q-1\}$, which we express here as $x_hy_g\rightarrow \cdots \rightarrow x_py_q$. For convenience of expression, the path $R_i$ can also be directly denoted by the label (i). For undefined symbols and terms, refer to [20].

The connectivity and diameter are the basic parameters necessary to discuss the vertex fault diameter of interconnection networks, we must first give the connectivity and diameter of the strong product graph of two paths. The following lemmas provide a solution.

Lemma 1

([3]). Let $G_1$ and $G_2$ be two maximally incomplete connected graphs with orders $n_1,n_2\ge 2$, respectively. Then

$$\kappa (G_1\boxtimes G_2)=min\{\delta _1n_2,\delta _2n_1,\delta _1+\delta _2+\delta _1 \delta _2\}.$$

A path is a maximally connected graph. In particular, when the order is greater than 2, the path is a maximally incomplete connected graph.

Lemma 2

Let $P_m$ and $P_n$ be two paths with orders $m,n\ge 2$, respectively. Then

$$\kappa (P_m\boxtimes P_n)={\left\{ \begin{array}{ll} 2, &{}if ~m=2,~n>2~or~ m>2,~n=2,\\ 3, &{}otherwise.\\ \end{array}\right. }$$

Proof

Let $G=P_m\boxtimes P_n$ with $V(P_m)=\{x_1,\cdots ,x_m\}$ and $V(P_n)=\{y_1,\cdots ,y_n\}$, $x_hy_g$ and $x_py_q$ are any two vertices in G, where $x_h,x_p\in V(P_m)$ and $y_g,y_q\in V(P_n)$. We discuss the following three cases.

Case 1

$m\ge 3$, $n\ge 3$. Since $P_m$ and $P_n$ are maximally incomplete connected graph, by Lemma 1, we have $\kappa (P_m\boxtimes P_n)=min\{m,n,3\}=3.$

Case 2

$m=2$, $n=2$. Since $P_2$ is a complete graph with order 2, we can get that $\kappa (P_2\boxtimes P_2)=\kappa (K_2\boxtimes K_2)=\kappa (K_4)=3.$

Case 3

$m=2$, $n>2$ or $m>2$, $n=2$. Without loss of generality, we assume that $m>2$ and $n=2$, then $V(P_2)=\{y_g,y_q\}$. If we remove the vertex $x_{h+1}y_g$ and the vertex $x_{h+1}y_q$ from G, then we can get $G-\{x_{h+1}y_g,x_{h+1}y_q\}$ is not connected. Therefore, there have $\kappa (P_m\boxtimes P_2)\le 2$. We consider the internally vertex-disjoint paths between any two vertices $x_hy_g$ and $x_py_q$ in G. According to the positional relationship between the two vertices, it can be divided into the following three subcases.

Subcase 1

$x_h=x_p$. we can get that there are two internally vertex-disjoint paths $R_1$ and $R_2$ from $x_hy_g$ to $x_hy_q$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_hy_q. \end{aligned}$$

(1)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_g\rightarrow x_hy_q. \end{aligned}$$

(2)

Subcase 2

$y_g=y_q$. we can get that there are two internally vertex-disjoint paths $R_3$ and $R_4$ from $x_hy_g$ to $x_py_g$ in G.

$$\begin{aligned} x_hy_g\rightarrow \cdots \rightarrow x_py_g. \end{aligned}$$

(3)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_q\rightarrow \cdots \rightarrow x_{p-1}y_q\rightarrow x_py_g. \end{aligned}$$

(4)

Subcase 3

$x_h\ne x_p$ and $y_g\ne y_q$. we can get that there are two internally vertex-disjoint paths $R_5$ and $R_6$ from $x_hy_g$ to $x_py_q$ in G.

$$\begin{aligned} x_hy_g\rightarrow \cdots \rightarrow x_{p-1}y_g\rightarrow x_py_q. \end{aligned}$$

(5)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_q\rightarrow \cdots \rightarrow x_py_q. \end{aligned}$$

(6)

There are always two internally vertex-disjoint paths from $x_hy_g$ to $x_py_q$ in G. Therefore, there have $\kappa (P_m\boxtimes P_2)\ge 2$. We can get $\kappa (P_m\boxtimes P_2)=2$.    $\square$

Lemma 3

([20]). Let $x_hy_g$ and $x_py_q$ be any two vertices in strong product graph $G_1\boxtimes G_2$, where $x_h,x_p\in V(G_1)$ and $y_g,y_q\in V(G_2)$. Then

$$d(G_1\boxtimes G_2;x_hy_g,x_py_q)=max\{d(G_1;x_h,x_p),d(G_2;y_g,y_q)\}.$$

Lemma 4

Let $P_m$ and $P_n$ be two paths with orders $m,n\ge 2$, respectively. Then

$$d(P_m\boxtimes P_n)=max\{m,n\}-1.$$

Proof

Let $G=P_m\boxtimes P_n$ with $V(P_m)=\{x_1,\cdots ,x_m\}$ and $V(P_n)=\{y_1,\cdots ,y_n\}$, $x_hy_g$ and $x_py_q$ are any two vertices in G, where $x_h,x_p\in V(P_m)$ and $y_g,y_q\in V(P_n)$. By Lemma 3, we have

$$d(G;x_hy_g,x_py_q)=max\{d(P_m;x_h,x_p),d(P_n;y_g,y_q)\}$$

$$~~~~~=max\{|p-h|,|q-g|\}$$

$$~~~\le max\{m-1,n-1\}$$

$$=max\{m,n\}-1.$$

From the above formula, we can get that the distance between any two vertices in G is no more than $max\{m,n\}-1$. Therefore, we get the diameter of G is $max\{m,n\}-1$.    $\square$

Under the previous lemmas, we prove the following result by constructing the internally vertex-disjoint paths between any two vertices in the strong product graph of two paths.

Theorem 1

Let $P_m$ and $P_n$ be two paths with orders $m,n\ge 2$, respectively. Then for any $1\le w \le 3$, we have

$$D_w(P_m\boxtimes P_n)={\left\{ \begin{array}{ll} max\{m,n\}-1, &{}for ~w=1,\\ max\{m,n\}-1, &{}for ~w=2 ~and ~m\ne n ~or ~m=n=2,\\ max\{m,n\}, &{}for ~w=2 ~and ~m=n>2,\\ max\{m,n\}, &{}for ~w=3 ~and ~m\ne n ~or~ m=n>3,\\ 1, &{}for ~w=3 ~and ~m=n=2,\\ 4, &{}for ~w=3 ~and ~m=n=3.\\ \end{array}\right. }$$

Proof

Let $G=P_m\boxtimes P_n$ with $V(P_m)=\{x_1,\cdots ,x_m\}$ and $V(P_n)=\{y_1,\cdots ,y_n\}$, $x_hy_g$ and $x_py_q$ are any two vertices in G, where $x_h,x_p\in V(P_m)$ and $y_g,y_q\in V(P_n)$. Let F be the faulty vertex set of G with $|F|<w$.

By Lemma 2, we can get the connectivity of G. If only one of m and n is 2, $\kappa (G)=2$, otherwise $\kappa (G)=3$. By Lemma 4, we can get the diameter of G is $max\{m,n\}-1$. For $w=1$, there is no faulty vertex in F, we have $D_1(G)=d(G)=max\{m,n\}-1$. Consider only $w>1$, there are four cases that need to be discussed.

Case 1

$m=2,~n>2~ or~ m>2,~n=2$. For any $1\le w\le 2$, we have $G-F$ is connected. Without loss of generality, we assume that $m>2$ and $n=2$. The diameter of G is $m-1\ge 2$. By the Case 3 of Lemma 2, there are also three subcases.

Subcase 1

$x_h=x_p$. There are two internally vertex-disjoint paths $R_1$ and $R_2$ from $x_hy_g$ to $x_hy_q$ in G, we can get $L(R_1)=1<L(R_2)=2\le m-1=d(G)$. For $w=2$, $|F|=1$. Even in the worst case, we have $d(G-F;x_hy_g,x_hy_q)\le d(G)$.

Subcase 2

$y_g=y_q$. There are two shortest paths $R_3$ and $R_4$ whose interior vertices are disjoint from $x_hy_g$ to $x_py_g$ in G, we can get $L(R_3)=L(R_4)=p-h\le m-1=d(G)$. For $w=2$, $|F|=1$. Even in the worst case, we have $d(G-F;x_hy_g,x_py_g)\le d(G)$.

Subcase 3

$x_h\ne x_p$ and $y_g\ne y_q$. There are two shortest paths $R_5$ and $R_6$ whose interior vertices are disjoint from $x_hy_g$ to $x_py_q$ in G, we can get $L(R_5)=L(R_6)=p-h\le m-1=d(G)$. For $w=2$, $|F|=1$. Even in the worst case, we have $d(G-F;x_hy_g,x_py_q)\le d(G)$.

In this case, we can conclude that $D_2(G)\le d(G)$. For $1\le w\le 2$, since $D_2(G)\ge d(G)$, we have $D_w(G)=d(G)$.

Case 2

$m=2$, $n=2$. For any $1\le w \le 3$, we have $G-F$ is connected. Since $P_2\boxtimes P_2=K_4$, the diameter of G is 1. For $1\le w\le 3$, $|F|=2$. Even in the worst case, the two vertices $x_hy_g$ and $x_py_q$ in G are still adjacent. Therefore, we can get $d(G-F;x_hy_g,x_py_q)=1=d(G)$, such that $D_w(G)=d(G)$.

Case 3

$m>3$, $n>3$. For any $1\le w \le 3$, we have $G-F$ is connected. The diameter of G is $max\{m,n\}-1$. According to the positional relationship between the two any vertices $x_hy_g$ and $x_py_q$ in G, we discuss the following two subcases.

Subcase 1

$x_h=x_p$ or $y_g=y_q$. Without loss of generality, we assume that $y_g=y_q$. According to the value range of g, there are two subcases.

Subsubcase 1

$g=1$ or $g=n$. Without loss of generality, we assume that $g=1$. Consider $p-h\ne 2$, we construct the internally vertex-disjoint paths which pass through all three neighbors of the vertex $x_hy_g$. For $w=2$, $|F|=1$. There are two shortest paths $R_{7}$ and $R_{8}$ whose interior vertices are disjoint from $x_hy_g$ to $x_py_g$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_g\rightarrow \cdots \rightarrow x_{p-1}y_g\rightarrow x_py_g,~~~~~ \end{aligned}$$

(7)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g+1}\rightarrow \cdots \rightarrow x_{p-1}y_{g+1}\rightarrow x_py_g, \end{aligned}$$

(8)

with $L(R_{7})=L(R_{8})=p-h\le m-1\le max\{m,n\}-1=d(G)$. Even in the worst case, we have $d(G-F;x_hy_g,x_py_g)\le d(G)$. For $w=3$, $|F|=2$. There are three internally vertex-disjoint paths $R_{7}$, $R_{9}$ and $R_{10}$ from $x_hy_g$ to $x_py_g$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_hy_{g+1}\rightarrow x_{h+1}y_{g+2}\rightarrow \cdots \rightarrow x_{p-2}y_{g+2}\rightarrow x_{p-1}y_{g+1}\rightarrow x_py_g,~ \end{aligned}$$

(9)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g+1}\rightarrow \cdots \rightarrow x_{p-2}y_{g+1}\rightarrow x_{p-1}y_{g+2} \rightarrow x_py_{g+1}\rightarrow x_py_g, \end{aligned}$$

(10)

with $L(R_{9})=L(R_{10})=p-h+1\le m\le max\{m,n\}=d(G)+1$. Even in the worst case, we have $d(G-F;x_hy_g,x_py_g)\le d(G)+1$. There is also one special case where the previous method of constructing paths is not applicable. Consider $p-h=2$, we construct three new internally vertex-disjoint paths $R_{11}$, $R_{12}$ and $R_{13}$ from $x_hy_g$ to $x_py_g$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_g\rightarrow x_py_g,~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \end{aligned}$$

(11)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g+1}\rightarrow x_py_g,~~~~~~~~~~~~~~~~~~~~~~~~~~~ \end{aligned}$$

(12)

$$\begin{aligned} x_hy_g\rightarrow x_hy_{g+1}\rightarrow x_{h+1}y_{g+2}\rightarrow x_py_{g+1}\rightarrow x_py_g, \end{aligned}$$

(13)

with $L(R_{11})=L(R_{12})=2$ and $L(R_{13})=4$. Since $m>3$ and $n>3$, $d(G)=max\{m,n\}-1\ge 3$. So we have $L(R_{11})=L(R_{12})<L(R_{13})\le d(G)+1$. For $w=2$, $|F|=1$, we can get $d(G-F;x_hy_g,x_py_g)<d(G)$. For $w=3$, $|F|=2$. Even in the worest case, we can get $d(G-F;x_hy_g,x_py_g)\le d(G)+1$.

Subsubcase 2

$1<g<n$. There are three shortest paths $R_{7}$, $R_{14}$ and $R_{15}$ whose interior vertices are disjoint from $x_hy_g$ to $x_py_g$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g+1}\rightarrow \cdots \rightarrow x_{p-1}y_{g+1}\rightarrow x_py_g, \end{aligned}$$

(14)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g-1}\rightarrow \cdots \rightarrow x_{p-1}y_{g-1}\rightarrow x_py_g, \end{aligned}$$

(15)

with $L(R_{7})=L(R_{14})=L(R_{15})=p-h\le m-1\le max\{m,n\}-1=d(G)$. For $1\le w\le 3$, $|F|=2$, we have $d(G-F;x_hy_g,x_py_g)\le d(G)$.

Subcase 2

$x_h\ne x_p$ and $y_g\ne y_q$. According to whether the distances of any two vertices $x_hy_g$ and $x_py_q$ on two factor graphs are equal, we can divide into the following two subcases.

Subsubcase 1

$p-h=q-g$. There are three internally vertex-disjoint paths $R_{16}$, $R_{17}$ and $R_{18}$ from $x_hy_g$ to $x_py_q$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g+1}\rightarrow \cdots \rightarrow x_{p-1}y_{q-1}\rightarrow x_py_q, \end{aligned}$$

(16)

$$\begin{aligned} x_hy_g\rightarrow x_hy_{g+1}\rightarrow \cdots \rightarrow x_{p-1}y_q\rightarrow x_py_q,~~~~~~ \end{aligned}$$

(17)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_g\rightarrow \cdots \rightarrow x_py_{q-1}\rightarrow x_py_q,~~~~~~ \end{aligned}$$

(18)

with $L(R_{16})=p-h\le m-1\le max\{m,n\}-1=d(G)$ and $L(R_{17})=L(R_{18})=p-h+1\le m\le max\{m,n\}=d(G)+1$. For $w=2$, $|F|=1$. Even in the worst case, we have $d(G-F;x_hy_g,x_py_q)\le d(G)+1$. For $w=3$, $|F|=2$. Similarly, we can also get $d(G-F;x_hy_g,x_py_q)\le d(G)+1$.

Subsubcase 2

$p-h\ne q-g$. Without loss of generality, we assume that $p-h>q-g$. Consider $q=n$, the vertex $x_py_q$ has no neighbors above, we can only construct the internally vertex-disjoint paths which pass through the neighbors at the same level or below $x_py_q$ in G. For $w=2$, $|F|=1$. There are two shortest paths $R_{19}$ and $R_{20}$ whose interior vertices are disjoint from $x_hy_g$ to $x_py_q$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_g\rightarrow \cdots \rightarrow x_{p-q+g}y_g\rightarrow \cdots \rightarrow x_{p-1}y_{q-1}\rightarrow x_py_q, \end{aligned}$$

(19)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g+1}\rightarrow \cdots \rightarrow x_{h+q-g}y_q\rightarrow \cdots \rightarrow x_{p-1}y_q\rightarrow x_py_q, \end{aligned}$$

(20)

with $L(R_{19})=L(R_{20})=p-h\le m-1\le max\{m,n\}-1=d(G)$. Even in the worst case, we have $d(G-F;x_hy_g,x_py_q)\le d(G)$. For $w=3$, $|F|=2$. There are three internally vertex-disjoint paths $R_{21}$, $R_{22}$ and $R_{23}$ from $x_hy_g$ to $x_py_q$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g+1}\rightarrow \cdots \rightarrow x_{h+q-g-1}y_{q-1}\rightarrow \cdots \rightarrow x_{p-1}y_{q-1}\rightarrow x_py_q, \end{aligned}$$

(21)

$$\begin{aligned} x_hy_g\rightarrow x_hy_{g+1}\rightarrow \cdots \rightarrow x_{h+q-g-1}y_q\rightarrow \cdots \rightarrow x_{p-1}y_q\rightarrow x_py_q,~~~~~~~~~ \end{aligned}$$

(22)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_g\rightarrow \cdots \rightarrow x_{p-q+g+1}y_g\rightarrow \cdots \rightarrow x_py_{q-1}\rightarrow x_py_q,~~~~~~~~~ \end{aligned}$$

(23)

with $L(R_{21})=p-h\le m-1\le max\{m,n\}-1=d(G)$ and $L(R_{22})=L(R_{23})=p-h+1\le m\le max\{m,n\}=d(G)+1$. Even in the worst case, we have $d(G-F;x_hy_g,x_py_q)\le d(G)+1$.

Consider $g<q<n$, we construct the internally vertex-disjoint paths which can pass through the neighbors above $x_py_q$. Different from the previous construction, we replace the neighbor $x_py_{q-1}$ of $x_py_q$ with $x_{p-1}y_{q+1}$. There are three internally vertex-disjoint paths $R_{19}$, $R_{20}$ and $R_{24}$ from $x_hy_g$ to $x_py_q$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_hy_{g+1}\rightarrow \cdots \rightarrow x_{h+q-g}y_{q+1}\rightarrow \cdots \rightarrow x_{p-1}y_{q+1}\rightarrow x_py_q, \end{aligned}$$

(24)

with $L(R_{19})=L(R_{20})=p-h\le m-1\le max\{m,n\}-1=d(G)$ and $L(R_{24})=p-h+1\le m\le max\{m,n\}=d(G)+1$. For $w=2$, $|F|=1$. Even in the worst case, we have $d(G-F;x_hy_g,x_py_q)\le d(G)$. For $w=3$, $|F|=2$. In the worst case, we have $d(G-F;x_hy_g,x_py_q)\le d(G)+1$.

In this case, we can conclude two results through analysis. If $m=n$, we can get $D_2(G)\le d(G)+1$ and $D_3(G)\le d(G)+1$. If $m\ne n$, we can get $D_2(G)\le d(G)$ and $D_3(G)\le d(G)+1$. Consider their lower bounds, we give a specific set of faulty vertices. If $m=n$, let $F=\{x_{h+1}y_{g+1}\}$, we can get $D_2(G)\ge d(G)+1$. Let $F=\{x_{h+1}y_{g+1},x_hy_{g+1}\}$, we can get $D_3(G)\ge d(G)+1$. Therefore, we have $D_2(G)=D_3(G)=d(G)+1$. If $m\ne n$, let $F=\{x_{h+1}y_g,x_{h+1}y_{g+1}\}$, we can get $D_3(G)\ge d(G)+1$. Therefore, we have $D_2(G)=d(G)$ and $D_3(G)=d(G)+1$.

Case 4

$m=3$, $n=3$. For any $1\le w \le 3$, we have $G-F$ is connected. The diameter of G is 2. For $w=2$, $|F|=1$, the result is the same as Case 3. For $w=3$, $|F|=2$. The construction method is the same as Case 3, we also can get that there are three internally vertex-disjoint paths of length at most 4 between any two vertices in G. So we have $D_3(G)\le d(G)+2$ in this case. Consider the lower bound, let $F=\{x_2y_1,x_2y_2\}$, we can get $d(G-F;x_1y_1,x_3y_1)=4=d(G)+2$, such that $D_3(G)\ge d(G)+2$. Therefore, we have $D_3(G)=d(G)+2=4$.    $\square$

The edge connectivity is the basic parameter necessary to discuss the edge fault diameter of interconnection networks, we give the edge connectivity of the strong product graph of two paths by the following lemma and corollary.

Lemma 5

([3]). Let $G_1$ and $G_2$ be two nontrivial connected graphs with orders $n_1,n_2\ge 2$, edges $c_1,c_2$, the minimum degrees $\delta _1,\delta _2$ and the edge-connectivity $\lambda _1,\lambda _2$, respectively. Then

$$\lambda (G_1\boxtimes G_2)=min\{\lambda _1(n_2+2c_2),\lambda _2(n_1+2c_1),\delta _1+\delta _2+\delta _1\delta _2\}.$$

If $G_1$ and $G_2$ are two paths, we have $c_i=n_i-1$ and $\delta _i=\lambda _i=1$ for $i=1,2$, the following corollary can be directly determined.

Corollary 1

Let $P_m$ and $P_n$ be two paths with orders $m,n\ge 2$, respectively. Then

$$\lambda (P_m\boxtimes P_n)=3.$$

Under the determined edge connectivity, we prove the following result by constructing edge-disjoint paths between any two vertices in strong product graph of two paths.

Theorem 2

Let $P_m$ and $P_n$ be two paths with orders $m,n\ge 2$, respectively. Then for any $1\le t \le 3$, we have

$$D^{'}_t(P_m\boxtimes P_n)={\left\{ \begin{array}{ll} max\{m,n\}-1, &{}for ~t=1,\\ max\{m,n\}-1, &{}for ~t=2 ~and ~m\ne n,\\ max\{m,n\}, &{}for ~t=2 ~and ~m=n,\\ max\{m,n\}, &{}for ~t=3.\\ \end{array}\right. }$$

Proof

Let $G=P_m\boxtimes P_n$ with $V(P_m)=\{x_1,\cdots ,x_m\}$ and $V(P_n)=\{y_1,\cdots ,y_n\}$, $x_hy_g$ and $x_py_q$ are any two vertices in G, where $x_h,x_p\in V(P_m)$ and $y_g,y_q\in V(P_n)$. Let F be the faulty edge set of G with $|F|<t$.

By Corollary 1, we can get the edge connectivity of G is 3. By Lemma 4, we can get the diameter of G is $max\{m,n\}-1$. For $w=1$, there is no faulty edge in F, we have $D^{'}_1(G)=d(G)=max\{m,n\}-1$. We can discuss the following three cases.

Case 1

$m=2$, $n=2$. For any $1\le t \le 3$, we have $G-F$ is connected. Since $P_2\boxtimes P_2=K_4$, we can get the diameter of G is 1 in this case. For a complete graph of order k, there are $k-1$ edge-disjoint paths of length at most 2 between any two vertices. Among them, one edge connects the two vertices, and there are $k-2$ paths of length 2 with the remaining $k-2$ neighbors as intermediate vertices. Through this, we can get that there are three edge-disjoint paths between any two vertices in G. Among them, one path of length 1 and two paths of length 2. For $2\le t\le 3$, $|F|=2$. Even in the worest case, there is at least one path of length 2 connects the two vertices in $G-F$, we can get $D^{'}_t(G)\le 2=d(G)+1$. Consider the lower bound, if we remove the edge which connects the two vertices, we can get $D^{'}_2(G)\ge 2=d(G)+1$. Therefore, we have $D^{'}_t(G)=2=d(G)+1$.

Case 2

$m\ne n$ or $m=n>3$. It is easy to know that the internally vertex-disjoint paths are also edge-disjoint, and the reverse is not true.

If $m\ne n$, by Theorem 1, we can also get $D^{'}_2(G)\le d(G)$ and $D^{'}_3(G)\le d(G)+1$. Let $F=\{(x_hy_g,x_{h+1}y_g),(x_hy_g,x_{h+1}y_{g+1})\}$, we can get $D^{'}_3(G)\ge d(G)+1$. Therefore, we have $D^{'}_2(G)=d(G)$ and $D^{'}_3(G)=d(G)+1$.

If $m=n>3$, by Theorem 1, we can also get $D^{'}_2(G)\le d(G)+1$ and $D^{'}_3(G)\le d(G)+1$. For $t=2$, $|F|=1$, let $F=\{(x_hy_g,x_{h+1}y_{g+1})\}$. If remove this edge, we can get the lower bound $D^{'}_2(G)\ge d(G)+1$. For $t=3$, $|F|=2$, let $F=\{(x_hy_g,x_{h+1}y_{g+1}),(x_hy_g,x_hy_{g+1})\}$. If remove the two edges, we can get the lower bound $D^{'}_3(G)\ge d(G)+1$. Therefore, we have $D^{'}_2(G)=D^{'}_3(G)=d(G)+1$.

Case 3

$m=3$, $n=3$. For $t=2$, $|F|=1$, the result is the same as Case 2. For $w=3$, $|F|=2$. Consider the worst case of $y_g=y_q$ and $p-h=2$. we construct three edge-disjoint paths $R_{11}$, $R_{25}$ and $R_{26}$ from $x_hy_g$ to $x_py_g$ in G.

$$\begin{aligned} x_hy_g\rightarrow x_hy_{g+1}\rightarrow x_{h+1}y_{g+1}\rightarrow x_py_g, \end{aligned}$$

(25)

$$\begin{aligned} x_hy_g\rightarrow x_{h+1}y_{g+1}\rightarrow x_py_{g+1}\rightarrow x_py_g, \end{aligned}$$

(26)

with $L(R_{11})=2$ and $L(R_{25})=L(R_{26})=3$. Since the diameter of G is 2, we can get $L(R_{11})<L(R_{25})=L(R_{26})=3=d(G)+1$. For $2\le t\le 3$, $|F|=2$. Even in the worst case, we have $D^{'}_t(G)\le d(G)+1$. By Case 2, the lower bound is $D^{'}_2(G)\ge d(G)+1$ and $D^{'}_3(G)\ge d(G)+1$. Therefore, we can also get $D^{'}_2(G)=D^{'}_3(G)=d(G)+1$.   $\square$

3 Model Comparison

The mesh network is a kind of static interconnection network, in which processors communicate directly through point-to-point connection [21]. It is widely used in system on chip, high-performance parallel and distributed systems [22]. The topology model of the mesh network is a Cartesian product graph of two paths, which is denoted by $G(m,n)=P_m\Box P_n$. In [21], we can get the connectivity and edge connectivity of the mesh network are 2. The diameter of the mesh network is $m+n-2$. For $w=2$, $|F|=1$. There are two internally vertex-disjoint paths of length at most d(G) between any two vertices in the mesh network. Therefore, we have $D_2(G(m,n))=D^{'}_2(G(m,n))=d(G)=m+n-2$. The maximum diameters of the mesh network G(4, 4) with one faulty vertex and one faulty edge are shown on Fig. 2.

Fig. 2.

The network G(4, 4) with one faulty vertex and one faulty edge.

Based on the mesh network, we give an improved mesh network. Its topology model is the strong product graph of two paths, which is denoted by $S(m,n)=P_m\boxtimes P_n$. In the previous results, we can get the connectivity of the improved mesh network is 2 or 3 and the edge connectivity of the improved mesh network is 3. The diameter of the improved mesh network is $max\{m,n\}-1$. In order to compare the mesh network equally, we just consider the worst case of $m=n$ and $w=2$. Therefore, we have $D_2(S(m,n))=D^{'}_2(S(m,n))=d(G)+1=max\{m,n\}$. The maximum diameters of the improved mesh network S(4, 4) with one faulty vertex and one faulty edge are shown on Fig. 3.

Fig. 3.

The network S(4, 4) with one faulty vertex and one faulty edge.

According to Fig. 2 and Fig. 3, we can directly get that the two networks have the same number of vertices, but the improved mesh network has more edges than the mesh network. This means that the link cost is higher when building the improved mesh network than when building the mesh network. Since $\kappa (G(m,n))\le \kappa (S(m,n))$ and $\lambda (G(m,n))<\lambda (S(m,n))$, the improved mesh network also has higher fault tolerance than the mesh network, which can allow more vertices or edges to fail and still ensure the normal operation of the network. From the previous results, we can get $d(S(m,n))<d(G(m,n))$, the improved mesh network has a smaller transmission delay than the mesh network. This means that in the process of data transmission, the improved mesh network has higher effectiveness than the mesh network.

Compare the transmission delay of the two networks in the case of vertex failure, from the previous results, we can get $D_2(S(m,n))\le D_2(G(m,n))$. In this case, the transmission delay of the improved mesh network is smaller than that of the mesh network. This means that when the two networks have vertex failure, the improved mesh network still maintains a higher effectiveness than the mesh network. Compare the transmission delay of the two networks in the case of edge failure, we can also get $D^{'}_2(S(m,n))\le D^{'}_2(G(m,n))$. Similarly, this means that when the two networks have edge failure, the improved mesh network still maintains a higer effectiveness than the mesh network. We define the difference between the vertex fault diameters of the mesh network and the improved mesh network as $\varDelta _1 =D_2(G(m,n))-D_2(S(m,n))$, and the difference between the edge fault diameters of the mesh network and the improved mesh network as $\varDelta _2 =D^{'}_2(G(m,n))-D^{'}_2(S(m,n))$. Then we can get

$$\varDelta _1 =\varDelta _2=m+n-2-max\{m,n\}=min\{m,n\}-2.$$

Through formula, we can find that with the expansion of the two networks scale, the two differences are also increasing, the advantage of information transmission effectiveness of the improved mesh network is more obvious than that of the mesh network.

Compared with the mesh network, the improved mesh network also has its own application characteristics. In the topology model of the improved mesh network, all edges are required to be independent of each other, there is no case that one edge fails and affects the information transmission of other edges. Therefore, the edge intersection is not allowed in the hardware design of the improved mesh network. Moreover, we can also find that there are two kinds of edges in the topology model of the improved mesh network. If the two endpoints of an edge have a pair of equal coordinates and a pair of coordinates whose values differ by 1, it is called a common edge. If the two endpoints of an edge have two pairs of coordinates whose values differ by 1, it is called a bevel edge. Obviously, the bevel edge is longer than the common edge. From this, the construction cost of bevel edge is higher, if it wants to keep the synchronization of sending and receiving information between adjacent vertices in a longer transmission distance than the common edge. In order to better handle edges with different costs, we define an edge as a unit, let the unit cost of common edge be $a_1$ and the unit cost of bevel edge be $a_2$, where $a_1<a_2$. In the topology model of the improved mesh network, the number of common edges is $m(n-1)+n(m-1)$ and the number of bevel edges is $2(m-1)(n-1)$. When building a large-scale improved mesh network S(m, n), the link cost function $C_l$ is

$$C_l=(2mn-m-n)a_1+2(m-1)(n-1)a_2.$$

Through the link cost function $C_l$, for an improved mesh network of a given size, no matter how large, the link cost is easy to obtain. However, there are still some limitations on the application of the improved mesh network. The improved mesh network requires that the processor can process data in up to 8 links at the same time. Compared with the parallel processing ability of data in up to 4 links of the mesh network, the improved mesh network requires higher processor performance, this also increases processor cost. For the number of edges $\epsilon$, there is also an upper limit.

$$\epsilon \le 4mn-3m-3n+2.$$

In this range of the number of edges, the advantages of the improved mesh network can be fully exerted.

When the size of the topology model of the improved mesh network is very large, the corresponding link cost is very high. However, with the expansion of the scale, the improved mesh network will have greater advantages in normal transmission efficiency, fault transmission efficiency, fault tolerance and reliability. So even for large-scale structures, the topology model of the improved mesh network is also applicable, especially for large-scale parallel computer systems.

4 Conclusions

With the development of supercomputers and parallel computing systems, high requirements are put forward for the fault tolerance capability and the information transmission capability under fault of network models. In this paper, the vertex fault diameter and edge fault diameter of strong product graph of two paths are given. Through the results, we find that the strong product graph of two paths have small vertex fault diameter and small edge fault diameter. Then we propose an improved mesh network, whose model is the strong product graph of two paths and has high fault tolerance and high effectiveness, this provides a new method for designing the topological structure of large-scale interconnection networks.