Rupture Degree of Some Cartesian Product Graphs

Yinkui Li, Tingyi Zhu

Department of Mathematics, Qinghai Nationalities College, Xining, China.

DOI: 10.4236/ojdm.2023.131002                

Abstract

The rupture degree of a noncomplete-connected graph G is defined by
, where is the number of components of and is the order of the largest component of. In this paper, we determine the rupture degree of some Cartesian product graphs.

Keywords

The Rupture Degree, Cartesian Product, The Vulnerability

1. Introduction

Let G be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. A set $X\subset V\left(G\right)$ is a cut-set of G, if $G-X$ is disconnected. For a cut-set X of G, we by $\omega \left(G-X\right)$ and $\tau \left(G-X\right)$, respectively, denote the number of components and the order of the largest component in $G-X$. The score of X is defined as $Sc\left(X\right)=\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)$. The rupture degree of a noncomplete- connected graph G is defined by

$r\left(G\right)=\max \left\{Sc\left(X\right):X\subset V\left(G\right),\omega \left(G-X\right)>1\right\}$.

We call X a r-set of G, if $Sc\left(X\right)=r\left(G\right)$.

The rupture degree is well used to measure the vulnerability of graphs, for it can measure not only the amount of work done to damage the network, but also how badly the network is damaged. The references about this parameter see [1] [2] [3].

For a vertex set $S\subseteq V\left(G\right)$, we by $G\left[S\right]$ denote the subgraph of G that is induced by S. And by $N\left(S\right)$ denote neighbor set of S that contains vertex, not in S, but has neighbor in S.

Let $G_1,G_2,\cdots ,G_k$ be connected graphs. The Cartesian product $G_1\times G_2\times \cdots \times G_k$ is a graph that has vertex set $V\left(G_1\right)\times V\left(G_2\right)\times \cdots \times V\left(G_k\right)$ with two vertices $u=\left(u_1,u_2,\cdots ,u_k\right)$ and $v=\left(v_1,v_2,\cdots ,v_k\right)$ adjacent if for exactly one i, $u_i\ne v_i$ and $\left(u_i,v_i\right)$ is an edge in $G_i$. As usual, we by $P_n$ and $C_n$ denote the path and the cycle on n vertices, respectively. It is well known that Cartesian products are highly recommended for the design of interconnection networks [4]. In this paper, we first determine the rupture degree for some Cartesian products such as $P_m\times C_n$ and $C_m\times C_n$. Then, discuss the rupture degree of grids $P_{n_1}\times P_{n_2}\times \cdots \times P_{n_k}$, and tori $C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}$.

For terminology and notations not defined here, we refer to the book [5].

2. The Rupture Degree of $P_m\times C_n$ and $C_m\times C_n$

In this section, we determine the rupture degree of Cartesian product $P_m\times C_n$ and $C_m\times C_n$. First, give some useful lemmas, which have been proved in [2].

Lemma 2.1. If H is a spanning subgraph of G, then $r\left(H\right)\ge r\left(G\right)$.

Lemma 2.2. The rupture degree of path $P_n$ and cycle $C_n$ are

$r\left(P_n\right)=\{\begin{array}{l}\begin{array}{ll}0,\hfill & \text{if}n\text{isodd;}\hfill \end{array}\\ \begin{array}{cc}-1,& \text{if}n\text{iseven}\text{.}\end{array}\end{array}$ $r\left(C_n\right)=\{\begin{array}{ll}-2,\hfill & \text{if}n\text{isodd};\hfill \\ -1,\hfill & \text{if}n\text{iseven}\text{.}\hfill \end{array}$

Lemma 2.3. Let X be a cut-set of $G\left(=P_m\times C_n\right)$. If n is odd, then $\omega \left(G-X\right)\le \frac{mn-m}{2}$.

Proof. Suppose S is a cut set of $C_n$, then $\omega \left(C_n-S\right)\le \frac{n-1}{2}$. Notice that $m{C}_n$ is a spanning subgraph of G, we have that $\omega \left(G-X\right)\le m\omega \left(C_n-S\right)\le \frac{mn-m}{2}$ for any cut-set X of G.

Lemma 2.4. Let X be a r-set of $G\left(=C_m\times C_n\right)$ with $m,n$ are odd, then $\omega \left(G-X\right)\le \frac{\left(m-1\right)\left(n-1\right)}{2}$.

Proof. Suppose that $V\left(C_m\right)=\left\{u_1,u_2,\cdots ,u_m\right\}$ and $V\left(C_n\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$, then $V\left(G\right)=\left\{w_{ij}=\left(u_i,v_j\right)|1\le i\le m;1\le j\le n\right\}$. Let X be a r-set of G and $W_i=\left\{w_{i1},w_{i2},\cdots ,w_{in}\right\}$ for $1\le i\le n$. Clearly, the induced subgraphs $G\left[W_i\right]$ is cycle with order n, named as $C_n^i$. And for any cut set $S_i$ of $C_n^i$, we have

$\omega \left(C_n^i-S\right)=\frac{n-1}{2}$. And call $S_i$ the optimal cut-set if equality holds. Clearly, the

optimal cut-set of $C_n^i$ is either $\left\{w_{i1},w_{i3},\cdots ,w_{in}\right\}$ or $\left\{w_{i2},w_{i4},\cdots ,w_{i\left(n-1\right)}\right\}$ for

$1\le i\le n$. Consider X be a r-set of G and m is odd, there exist $C_n^i$ and $C_n^{i+1}$ such

that $\omega \left(G\left[V\left(C_n^i\cup C_n^{i+1}\right)\right]-X\right)\le \frac{n-1}{2}$ for some i. Now, let

$G_1=G\left[V\left(C_n^i\cup C_n^{i+1}\right)\right]$ and $G_2=G-G_1=P_{m-2}\times C_n$. Consider $\omega \left(G-X\right)\le \omega \left(G_1-X\right)+\omega \left(G_2-X\right)$, by Lemma 2.3, we get

$\omega \left(G-X\right)\le \frac{n-1}{2}+\frac{\left(m-2\right)\left(n-1\right)}{2}=\frac{\left(m-1\right)\left(n-1\right)}{2}$.

Lemma 2.5. Let $m\ge 2$ and $n\ge 3$ be positive integers. Then $r\left(P_m\times C_n\right)\ge r\left(P_{m+1}\times C_n\right)$.

Proof. Let $G=P_{m+1}\times C_n$, $G^{\prime }=P_m\times C_n$. Then $G-G^{\prime }$ is a cycle. Support that X is a r-set of G, then $X_1=X\cap V\left(G^{\prime }\right)$ and $X_2=X\cap V\left(G-G^{\prime }\right)$ are vertex cut set of $G^{\prime }$ and $G-G^{\prime }$, respectively. Denote ${\omega }_1=\omega \left(G^{\prime }-X_1\right)$, ${\omega }_2=\omega \left(G-G^{\prime }-X_2\right)$. Since $r\left(G^{\prime }\right)\ge {\omega }_1-\left|X_1\right|-\tau \left(G^{\prime }-X_1\right)$ and $\tau \left(G-X\right)\ge \tau \left(G^{\prime }-X_1\right)$, we have $r\left(G^{\prime }\right)\ge {\omega }_1-\left|X_1\right|-\tau \left(G-X\right)$. So $r\left(G\right)=$ $\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)\le {\omega }_1+{\omega }_2-\left|X_1\right|-\left|X_2\right|-\tau \left(G-X\right)\le r\left(G^{\prime }\right)+{\omega }_2-\left|X_2\right|$.

Notice that $G-G^{\prime }$ is a cycle and thus ${\omega }_2\le \left|X_2\right|$. Thus $r\left(G\right)\le r\left(G^{\prime }\right)$. This means $r\left(P_m\times C_n\right)\ge r\left(P_{m+1}\times C_n\right)$.

Theorem 2.6. Let $m\ge 2$ and $n\ge 3$ be positive integers. Then the rupture degree of $P_m\times C_n$ is

$r\left(P_m\times C_n\right)=\{\begin{array}{ll}-1,\hfill & \text{if}n\text{is}\text{even;}\hfill \\ \{\begin{array}{ll}-\frac{4+m}{2},\hfill & \text{if}m\text{is}\text{even;}\hfill \\ -\frac{3+m}{2},\hfill & \text{if}m\text{is}\text{odd}\text{.}\hfill \end{array}\hfill & \text{if}n\text{is}\text{odd}\text{.}\hfill \end{array}$

Proof. Suppose $V\left(P_m\right)=\left\{u_1,u_2,\cdots ,u_m\right\}$ and $V\left(C_n\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$, then $V\left(P_m\times C_n\right)=\left\{\left(u_i,v_j\right)|1\le i\le m;1\le j\le n\right\}$. For narrative purposes, we let $P_m\times C_n=G$ and distinguish three cases to complete the proof.

Case 1. n is even.

Notice that G contains a Hamilton cycle $C_{mn}$, we by Lemmas 2.1 and 2.2 get $r\left(G\right)\le -1$. On the other hand, let $X^{*}=\left\{\left(u_i,v_j\right)|i\equiv 0\left(\mathrm{mod}2\right),j=1,3,\cdots ,n-1;i\equiv 1\left(\mathrm{mod}2\right),j=2,4,\cdots ,n\right\}$ for

$1\le i\le m$. Clearly, $\omega \left(G-X^{*}\right)=m\frac{n}{2}$, $\left|X^{*}\right|=m\frac{n}{2}$ and $\tau \left(G-X^{*}\right)=1$. By the

definition of rupture degree, we have $r\left(G\right)\ge \omega \left(G-X^{*}\right)-\left|X^{*}\right|-\tau \left(G-X^{*}\right)=-1$. Thus $r\left(P_m\times C_n\right)=-1$ while n is even.

Case 2. n is odd, m is even.

First, let $X^{*}=\left\{\left(u_i,v_j\right)|i\equiv 0\left(\mathrm{mod}2\right),j=1,3,\cdots ,n;i\equiv 1\left(\mathrm{mod}2\right),j=2,4,\cdots ,n-1\right\}$ for

$1\le i\le m$. Since $\omega \left(G-X^{*}\right)=\frac{mn-m}{2}$, $\left|X^{*}\right|=\frac{mn}{2}$ and $\tau \left(G-X^{*}\right)=2$. Then $Sc\left(X^{*}\right)=\omega \left(G-X^{*}\right)-\left|X^{*}\right|-\tau \left(G-X^{*}\right)=-\frac{m+4}{2}$. Now, we by showing $Sc\left(X\right)\le -\frac{m+4}{2}$ for any cut-set X of G to get $r\left(G\right)=-\frac{m+4}{2}$. Now, distinguish some cases to discuss.

Subcase 2.1. $\left|X\right|\ge \left|X^{*}\right|=\frac{mn}{2}$.

If $\tau \left(G-X\right)=1$, by Lemma 2.3, then $\left|X\right|=mn-\omega \left(G-X\right)\ge \frac{mn+m}{2}$. Consider $m\ge 2$, thus $Sc\left(X\right)=\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)\le \frac{mn-m}{2}-\frac{mn+m}{2}-1=-\frac{2m+2}{2}\le -\frac{m+4}{2}$.

If $\tau \left(G-X\right)\ge 2$, consider $\left|X\right|\ge \frac{mn}{2}$, we have $Sc\left(X\right)=\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)\le \frac{mn-m}{2}-\frac{mn}{2}-2=-\frac{m+4}{2}$.

Subcase 2.2. $\left|X\right|<\left|X^{*}\right|=\frac{mn}{2}$.

Let $A_i=\left\{\left(u_i,v_j\right)|1\le j\le n\right\}$, $X_i=A_i\cap X$, $X_i^{*}=A_i\cap X^{*}$ for $i=1,2,\cdots ,m$ and $B_j=\left\{\left(u_i,v_j\right)|1\le i\le m\right\}$, $Y_j=B_j\cap X$, $Y_j^{*}=B_j\cap X^{*}$ for $j=1,2,\cdots ,n$. Clearly, $G\left[A_i\right]$ and $G\left[A_i\right]$ are cycles with order n and path with order m,

respectively. We discuss by $n\ge \frac{m}{2}$ and $n\le \frac{m}{2}-1$.

Subcase 2.2.1. $n\ge \frac{m}{2}$.

Notice that $G\left[A_i\right]\cup G\left[A_{i+1}\right]$ is a spanning subgraph of $G\left[A_i\cup A_{i+1}\right]$ with $1\le i\le m-1$, we can get $\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i\cup X_{i+1}\right)\le \left|X_i\cup X_{i+1}\right|-1$. In fact, if $2\le \left|X_i\cup X_{i+1}\right|<n$, then $\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i\cup X_{i+1}\right)\le \omega \left(G\left[A_i\right]-X_i\right)+\omega \left(G\left[A_{i+1}\right]-X_{i+1}\right)-1$. Thus, $\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i\cup X_{i+1}\right)\le \left|X_i\right|+\left|X_{i+1}\right|-1=\left|X_i\cup X_{i+1}\right|-1$.

If $\left|X_i\cup X_{i+1}\right|\ge n$, then $\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i\cup X_{i+1}\right)\le n-1$. Therefore, $\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i\cup X_{i+1}\right)\le \left|X_i\cup X_{i+1}\right|-1$. Combine this with the fact $\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i^{*}\cup X_{i+1}^{*}\right)=n-1$, it is clear that $\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i^{*}\cup X_{i+1}^{*}\right)-\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i\cup X_{i+1}\right)\ge n-\left|X_i\cup X_{i+1}\right|$ for $\left|X_i\cup X_{i+1}\right|\ge 2$ with $1\le i\le m-1$.

Now let $a={\displaystyle {\sum }_{\left|X_i\cup X_{i+1}\right|\ge 2}\left(n-\left|X_i\cup X_{i+1}\right|\right)}$, $M=\left\{X_i\cup X_{i+1}:\left|X_i\cup X_{i+1}\right|=0\right\}$ and $N=\left\{X_i\cup X_{i+1}:\left|X_i\cup X_{i+1}\right|=1\right\}$ for $i=1,3,\cdots ,m-1$. Consider X is a vertex cut set of G, then $\left|M\right|+\left|N\right|\le \frac{m}{2}-1$. Furthermore, since

$G\left[A_1\cup A_2\right]\cup G\left[A_3\cup A_4\right]\cup \cdots \cup G\left[A_{m-1}\cup A_m\right]$ is a spanning subgraph of G with $\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i^{*}\cup X_{i+1}^{*}\right)-\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i\cup X_{i+1}\right)\ge n-\left|X_i\cup X_{i+1}\right|$ for $\left|X_i\cup X_{i+1}\right|\ge 2$, we have $\left|X^{*}\right|=\frac{mn}{2}=\left|X\right|+\left|M\right|n+\left|N\right|\left(n-1\right)+a$.

And thus

$\begin{array}{c}\omega \left(G-X^{*}\right)=\frac{m\left(n-1\right)}{2}\\ =\underset{i}{{\displaystyle \sum }}\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i^{*}\cup X_{i+1}^{*}\right)\\ \ge \underset{i}{{\displaystyle \sum }}\omega \left(G\left[A_i\cup A_{i+1}\right]-X_i\cup X_{i+1}\right)+\left|M\right|\left(n-2\right)+\left|N\right|\left(n-2\right)+a\\ \ge \omega \left(G-X\right)+\left(\left|M\right|+\left|N\right|\right)\left(n-2\right)+a.\end{array}$

Now, we estimate the value $Sc\left(X\right)$ in details. If $\left|M\right|\ge 1$, then $\tau \left(G-X\right)\ge 2n$. We have

If $\left|M\right|=0,\left|N\right|\ge 1$, then $\tau \left(G-X\right)\ge 2n-1$. Consider $\left|N\right|\le \frac{m}{2}-1$ and $m\ge 4$. Thus we get

$\begin{array}{c}Sc\left(X\right)=\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)\\ \le \frac{m\left(n-1\right)}{2}-\left|N\right|\left(n-2\right)-a+\left|N\right|\left(n-1\right)+a-\frac{mn}{2}-2n+1\\ =-\frac{m}{2}+\left|N\right|-2n+1\le -2n\le -m\le -\frac{m+4}{2}.\end{array}$

If $\left|M\right|=0,\left|N\right|=0$, then $\left|X\right|=\frac{mn}{2}-a$. Combine $\tau \left(G-X\right)\ge 2$. We have $Sc\left(X\right)=\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)\le \frac{m\left(n-1\right)}{2}-a-\frac{mn}{2}+a-2=-\frac{m+4}{2}$.

Subcase 2.2.2. $n\le \frac{m}{2}-1$.

Notice that $G\left[B_j\cup B_{j+1}\right]$ is a ladder with order 2m and $G\left[B_1\cup B_2\right]\cup G\left[B_3\cup B_4\right]\cup \cdots \cup G\left[B_{n-2}\cup B_{n-1}\right]\cup G\left[B_n\right]$ is a spanning subgraph of G. We similarly get

$\omega \left(G\left[B_j\cup B_{j+1}\right]-Y_j^{*}\cup Y_{j+1}^{*}\right)-\omega \left(G\left[B_j\cup B_{j+1}\right]-Y_j\cup Y_{j+1}\right)\ge m-\left|Y_j\cup Y_{j+1}\right|$ while $\left|Y_j\cup Y_{j+1}\right|\ge 1$ for $j=1,3,\cdots ,n-2$. Now, let $S=\left\{Y_j\cup Y_{j+1}:\left|Y_j\cup Y_{j+1}\right|=0\right\}$ and $b={\displaystyle {\sum }_{\left|Y_j\cup Y_{j+1}\right|\ge 1}\left(m-\left|Y_j\cup Y_{j+1}\right|\right)}$ with $j=1,3,\cdots ,n-2$ and discuss $Sc\left(X\right)$ by $\left|S\right|\ge 1$ and $\left|S\right|=0$.

If $\left|S\right|\ge 1$, then $\tau \left(G-X\right)\ge 2m$. Similarly, we get $\left|X^{*}\right|=\frac{mn}{2}=\left|X\right|+\left|S\right|m+b+\frac{m}{2}-\left|Y_n\right|$ and

$\begin{array}{c}\omega \left(G-X^{*}\right)=\frac{m\left(n-1\right)}{2}\\ =\underset{j}{{\displaystyle \sum }}\omega \left(G\left[B_j\cup B_{j+1}\right]-Y_j^{*}\cup Y_{j+1}^{*}\right)\\ \ge \underset{j}{{\displaystyle \sum }}\omega \left(G\left[B_j\cup B_{j+1}\right]-Y_j\cup Y_{j+1}\right)+\left|S\right|\left(m-1\right)+b\\ \ge \omega \left(G-X\right)+\left|S\right|\left(m-1\right)+b.\end{array}$

Therefore, we get

$\begin{array}{c}Sc\left(X\right)=\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)\\ \le \frac{m\left(n-1\right)}{2}-\left[\left|S\right|\left(m-1\right)+b\right]-\left[\frac{mn}{2}-\left(\left|S\right|m+b+\frac{m}{2}-\left|Y_n\right|\right)\right]-2m\\ =\left|S\right|-\left|Y_n\right|-2m\le \frac{n-3}{2}-2m\\ \le -\frac{7m+8}{4}<-\frac{m+4}{2}.\end{array}$

If $\left|S\right|=0$, we discuss by the value of $\left|Y_n\right|$. While $\left|Y_n\right|\ge \frac{m}{2}$, consider $\left|X\right|<\frac{mn}{2}$, then $\tau \left(G-X\right)\ge 2$. Combine $\left|X^{*}\right|=\frac{mn}{2}=\left|X\right|+\frac{m}{2}-\left|Y_n\right|+b$ and $\omega \left(G-X^{*}\right)=\frac{m\left(n-1\right)}{2}\ge \omega \left(G-X\right)+b$, we have

$\begin{array}{c}Sc\left(X\right)=\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)\\ \le \frac{m\left(n-1\right)}{2}-b-\left(\frac{mn}{2}-\frac{m}{2}+\left|Y_n\right|-b\right)-2\\ =-\left|Y_n\right|-2\le -\frac{m+4}{2}.\end{array}$

while $\left|Y_n\right|\le \frac{m}{2}-1$, we would get ${\displaystyle {\sum }_{j=1,3,\cdots ,n-2}\omega \left(G\left[B_j\cup B_{j+1}\right]-Y_j\cup Y_{j+1}\right)}\ge \omega \left(G-X\right)-\left|Y_n\right|+\frac{m}{2}$. In fact, since the optimal cut set of $G\left[B_n\right]$ always contains $\frac{m}{2}$ vertices, each vertex of $Y_n^{*}\setminus Y_n$ would connect at least two components in $G-X$. Thus, we get ${\displaystyle {\sum }_{j=1,3,\cdots ,n-2}\omega \left(G\left[B_j\cup B_{j+1}\right]-Y_j\cup Y_{j+1}\right)}\ge \omega \left(G-X\right)+\frac{m}{2}-\left|Y_n\right|$. Combine this with $\left|X^{*}\right|=\frac{mn}{2}=\left|X\right|+\frac{m}{2}-\left|Y_n\right|+b$, $\tau \left(G-X\right)\ge 2$ and $\frac{m\left(n-1\right)}{2}\ge {\displaystyle {\sum }_j\omega \left(G\left[B_j\cup B_{j+1}\right]-Y_j\cup Y_{j+1}\right)}+b$, we have

$\begin{array}{c}Sc\left(X\right)=\omega \left(G-X\right)-\left|X\right|-\tau \left(G-X\right)\\ \le \underset{j=1,3,\cdots ,n-2}{{\displaystyle \sum }}\omega \left(G\left[B_j\cup B_{j+1}\right]-Y_j\cup Y_{j+1}\right)+\left|Y_n\right|-\frac{m}{2}+\frac{m}{2}\\ -\left|Y_n\right|+b-\frac{mn}{2}-2\\ \le \frac{m\left(n-1\right)}{2}-b+b-\frac{mn}{2}-2\\ =-\frac{m+4}{2}.\end{array}$

Case 3. $m,n$ are both odd.

By Lemma 2.5, we get $r\left(P_{m-1}\times C_n\right)\ge r\left(P_m\times C_n\right)$. Notice that $n-1$ is even, we get $r\left(G\right)\le r\left(P_{m-1}\times C_n\right)=-\frac{3+m}{2}$.

On the other hand, let

$X^{*}=\left\{\left(u_i,v_j\right)|i\equiv 0\left(\mathrm{mod}2\right),j=1,3,\cdots ,n;i\equiv 1\left(\mathrm{mod}2\right),j=2,4,\cdots ,n-1\right\}$ for $1\le i\le m$. Clearly, $X^{*}$ is a cut set of $P_m\times C_n$ with $\omega \left(G-X^{*}\right)=\frac{mn-m}{2}$, $\left|X^{*}\right|=\frac{mn-1}{2}$ and $\tau \left(G-X^{*}\right)=2$. This implies that $r\left(G\right)\ge \omega \left(G-X^{*}\right)-\left|X^{*}\right|-\tau \left(G-X^{*}\right)=-\frac{3+m}{2}$.

Therefore, $r\left(P_m\times C_n\right)=-\frac{3+m}{2}$ while $m,n$ are both odd. This completes the proof.

Theorem 2.7. Let $m,n$ be positive integers with $n\ge m\ge 3$. Then the rupture degree of $C_m\times C_n$ is

Proof. Suppose $V\left(C_m\right)=\left\{u_1,u_2,\cdots ,u_m\right\}$ and $V\left(C_n\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$, then $V\left(C_m\times C_n\right)=\left\{w_{ij}=\left(u_i,v_j\right)|1\le i\le m;1\le j\le n\right\}$. Similarly, we let $C_m\times C_n=G$ and $W_i=\left\{w_{ij}|1\le j\le n\right\}$, $W_j=\left\{w_{ij}|1\le i\le m\right\}$. Clearly, both ${\displaystyle {\cup }_{i}G\left[W_i\cup W_{i+1}\right]}$ and ${\displaystyle {\cup }_{j}G\left[W_j\cup W_{j+1}\right]}$ are spanning subgraph of G. Now, we distinguish three cases to complete the proof.

Case 1. Both m and n are even.

Notice that $P_m\times C_n$ is a spanning subgraph of G, by Lemma 2.1 and Theorem 2.6, we have $r\left(G\right)\le -1$. On the other hand, let

$X^{*}=\left\{\left(u_i,v_j\right)|i\equiv 0\left(\mathrm{mod}2\right),j=1,3,\cdots ,n-1;i\equiv 1\left(\mathrm{mod}2\right),j=2,4,\cdots ,n\right\}$ for $1\le i\le m$. Since $\omega \left(G-X^{*}\right)=m\frac{n}{2}$, $\left|X^{*}\right|=m\frac{n}{2}$ and $\tau \left(G-X^{*}\right)=1$. Thus $r\left(G\right)\ge \omega \left(G-X^{*}\right)-\left|X^{*}\right|-\tau \left(G-X^{*}\right)=-1$. Therefore, $r\left(G\right)=-1$.

Case 2. One of n and m is even.

Without loss generality, suppose m is even, then n is odd. We first let

$X^{*}=\left\{\left(u_i,v_j\right)|i\equiv 0\left(\mathrm{mod}2\right),j=1,3,\cdots ,n;i\equiv 1\left(\mathrm{mod}2\right),j=2,4,\cdots ,n-1\right\}$ for $1\le i\le m$. Clearly, $\omega \left(G-X^{*}\right)=\frac{mn-m}{2}$, $\left|X^{*}\right|=\frac{mn}{2}$ and $\tau \left(G-X^{*}\right)=2$. Thus $r\left(G\right)\ge \omega \left(G-X^{*}\right)-\left|X^{*}\right|-\tau \left(G-X^{*}\right)=-\frac{m+4}{2}$. Consider $P_m\times C_n$ is a spanning subgraph of G, by Lemmas 2.1 and 2.5, we have $r\left(G\right)\le -\frac{m+4}{2}$. So, we get $r\left(G\right)=-\frac{m+4}{2}$ while m is even and n is odd. Similar to the case for n is even and m is odd, here omitted.

Case 3. Both m and n are odd.

First, let

$X^{*}=\left\{\left(u_i,v_j\right)|i\equiv 0\left(\mathrm{mod}2\right),j=2,4,\cdots ,n-1;i\equiv 1\left(\mathrm{mod}2\right),j=1,3,\cdots ,n\right\}$ for $1\le i\le m$. Clearly, $X^{*}$ is a cut set of G with $\omega \left(G-X^{*}\right)=\frac{\left(m-1\right)\left(n-1\right)}{2}$, $\left|X^{*}\right|=\frac{mn+1}{2}$ and $\tau \left(G-X^{*}\right)=2$. Thus $r\left(G\right)\ge \omega \left(G-X^{*}\right)-\left|X^{*}\right|-\tau \left(G-X^{*}\right)=-\frac{4+m+n}{2}$. The following we by proving claim to show $r\left(G\right)\le -\frac{4+m+n}{2}$.

Claim. Let $m,n$ be two odd numbers with $3\le m\le n$ and S be a r-set of $G\left(=C_m\times C_n\right)$. Then $G-S=s{K}_2\cup t{K}_1$ with $s\le \frac{m+n-2}{2}$.

Proof. Let S be a r-set of G with $\tau \left(G-S\right)$ as small as possible. Suppose $G_1,G_2,\cdots ,G_k$ are components of $G-S$. We first show $\left|G_i\right|\le 2$ for $1\le i\le k$. If not, assume that $G_1,G_2,\cdots ,G_{k_1}$ with $\left|G_j\right|\ge 3$ for $1\le j\le k_1\le k$, then each $G_j$ has at least one cut vertex (unless $G_j=K_2$ or $K_1$ ). In fact, assume $G_j\left(\ne K_2,K_1\right)$ has no cut vertex, we exchange vertices in $N\left(G_j\right)$ with vertices in $V\left(G_j\right)$ to keep $\left|S\right|$ constant and find that either $\omega \left(G-S\right)-\left|S\right|-\tau \left(G-S\right)$ would be greater or $\tau \left(G-S\right)$ would be smaller, which contradicts to the choose of S. So, each $G_j\left(1\le j\le k_1\right)$ has cut vertex and suppose $w_1,w_2,\cdots ,w_{k_1}$ are cut vertices of $G_1,G_2,\cdots ,G_{k_1}$, respectively. Let $S^{\prime }=S\cup \left\{w_1,w_2,\cdots ,w_{k_1}\right\}$. Then $\tau \left(G-S^{\prime }\right)\le \tau \left(G-S\right)-2$. Thus we get

$\begin{array}{l}\omega \left(G-S^{\prime }\right)-\left|S^{\prime }\right|-\tau \left(G-S^{\prime }\right)\\ \ge \omega \left(G-S\right)+k_1-\left(\left|S\right|+k_1\right)-\left(\tau \left(G-S\right)-2\right)\\ >\omega \left(G-S\right)-\left|S\right|-\tau \left(G-S\right).\end{array}$

This contradicts to the choice of S. So $\left|G_i\right|\le 2$ for $1\le i\le k$ and then denote $G-S=s{K}_2\cup t{K}_1$. Further, it finds that there are at most one component as $K_2$ in $G\left[C_i\cup C_{i+1}\right]-S$ for $1\le i\le m-1$ and $G\left[C_j\cup C_{j+1}\right]-S$ for $1\le j\le n-1$. Otherwise, if $G\left[C_i\cup C_{i+1}\right]-S$ or $G\left[C_j\cup C_{j+1}\right]-S$ has at least two components as $K_2$, then $\tau \left(G-S\right)\ge 3$, contradiction. This implies that

$s\le \frac{m-1}{2}+\frac{n-1}{2}=\frac{m+n-2}{2}$.

By Lemma 2.4 and the above Claim, we get

$\begin{array}{c}\left|S\right|\ge mn-2\frac{m+n-2}{2}-\left(\frac{\left(m-1\right)\left(n-1\right)}{2}-\frac{\left(m+n-2\right)}{2}\right)\\ =mn-m-n+2-\frac{\left(mn-2m-2n+3\right)}{2}\\ =\frac{mn+1}{2}.\end{array}$

Thus, we get

$r\left(G\right)=\omega \left(G-S\right)-\left|S\right|-\tau \left(G-S\right)\le \frac{\left(m-1\right)\left(n-1\right)}{2}-\frac{mn+1}{2}-2=-\frac{4+m+n}{2}$.

This completes the proof.

3. The Rupture Degree of Grids and Tori

Let $n_1,n_2,\cdots ,n_k$ be positive integers. We discuss the rupture degree of grids $P_{n_1}\times P_{n_2}\times \cdots \times P_{n_k}$ with $n_i\ge 2$ and tori $C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}$ with $n_i\ge 3$.

Lemma 3.1. [2] Let $m,n$ be integers with $n\le m$. Then $r\left(K_{m,n}\right)=m-n-1$.

Lemma 3.2. [1] Let $m,n$ be integers with $1\le m\le n$. Then $r\left(K_m\times K_n\right)=m+n-mn-\lceil \frac{n}{m}\rceil$.

Theorem 3.3. For all positive integers $n_1,n_2,\cdots ,n_k$, the rupture degree of grids is

$r\left(P_{n_1}\times P_{n_2}\times \cdots \times P_{n_k}\right)=\{\begin{array}{ll}0,\hfill & \text{if}\text{all}{n}_i\text{are}\text{odd},\hfill \\ -1,\hfill & \text{if}\text{some}{n}_i\text{is}\text{even}.\hfill \end{array}$

Proof. Notices that $P_{n_1}\times P_{n_2}\times \cdots \times P_{n_k}$ contains a Hamilton path $P_{n_1{n}_2\cdots n_k}$. So by Lemmas 2.1 and 2.2, we have

$r\left(P_{n_1}\times P_{n_2}\times \cdots \times P_{n_k}\right)\le r\left(P_{n_1{n}_2\cdots n_k}\right)=\{\begin{array}{ll}0,\hfill & \text{if}\text{all}{n}_i\text{are}\text{odd},\hfill \\ -1,\hfill & \text{if}\text{some}{n}_i\text{is}\text{even}.\hfill \end{array}$

On the other hand, it is well known that $P_{n_1}\times P_{n_1}\times P_{n_2}\times \cdots \times P_{n_k}$ is a bipartite graph and thus

Then by Lemmas 2.1 and 3.1, we get

$r\left(P_{n_1}\times P_{n_2}\times \cdots \times P_{n_k}\right)\ge \{\begin{array}{ll}0,\hfill & \text{if}\text{all}{n}_i\text{are}\text{odd},\hfill \\ -1,\hfill & \text{if}\text{some}{n}_i\text{is}\text{even}.\hfill \end{array}$

This completes the proof.

Lemma 3.4. Let $N=\left\{n_1,n_2,\cdots ,n_k\right\}$ be integer number set with $k\ge 3$ and $\left|n_i\right|\ge 3$. If S and T and disjoint sets of N with $S\cup T=N$, such that

$x={\displaystyle {\prod }_{n_i\in S}{n}_i}\le y={\displaystyle {\prod }_{n_i\in T}{n}_i}$, then $x+y-xy-\lceil \frac{y}{x}\rceil$ meets maximum while $x=\min \left\{n_1,n_2,\cdots ,n_k\right\}$.

Proof. Without lose generality, suppose $\min \left\{n_1,n_2,\cdots ,n_k\right\}=n_1$ and

$n_1{n}_2\cdots n_k=xy=a$. Consider $k\ge 3$ and $y\ge x$, we have $a\ge x^2$ and $y\ge n_1^2$. Thus $a\ge n_1^{2}x$. Now, let $I=n_1+\frac{a}{n_1}-a-\lceil \frac{a}{n_1^2}\rceil$, estimate the deference of $x+y-xy-\lceil \frac{y}{x}\rceil$ and I for $x={\displaystyle {\prod }_{n_i\in S}{n}_i}>n_1$.

Clearly, if $n_1\ge 4$, we have

$\begin{array}{c}I-\left(x+y-xy-\lceil \frac{y}{x}\rceil \right)=n_1+\frac{a}{n_1}-\lceil \frac{a}{n_1^2}\rceil -\left(x+\frac{a}{x}-\lceil \frac{a}{x^2}\rceil \right)\\ =\left(n_1-x\right)+\left(x-n_1\right)\frac{a}{n_{1}x}-\lceil \frac{a}{n_1^2}\rceil +\lceil \frac{a}{x^2}\rceil \\ \ge \left(x-n_1\right)\left(\frac{a}{n_{1}x}-1\right)-\frac{a}{n_1^2}-1+\frac{a}{x^2}\\ =\left(x-n_1\right)\left(a\frac{n_{1}x-x-n_1}{n_1^2{x}^2}-1\right)-1\\ \ge \left(x-n_1\right)\left(a\frac{n_{1}x-2x}{n_1^2{x}^2}-1\right)-1\\ \ge \left(x-n_1\right)\left(n_1-3\right)-1\ge 0.\end{array}$

If $n_1=3$ and $x\ge 9$, we similarly have

$I-\left(x+y-xy-\lceil \frac{y}{x}\rceil \right)=3+\frac{a}{3}-\lceil \frac{a}{3^2}\rceil -\left(x+\frac{a}{x}-\lceil \frac{a}{x^2}\rceil \right)$

$\begin{array}{c}=\left(3-x\right)+\left(x-3\right)\frac{a}{3x}-\lceil \frac{a}{3^2}\rceil +\lceil \frac{a}{x^2}\rceil \\ \ge \left(x-3\right)\left(\frac{a}{3x}-1\right)-\frac{a}{3^2}-1+\frac{a}{x^2}\\ \ge \left(x-3\right)\left(\frac{a-3x}{3x}\right)-\frac{a}{3^2}\end{array}$

$\begin{array}{l}=\frac{1}{3}\left[\left(x-3\right)\left(y-3\right)-\frac{a}{3}\right]\\ \ge \frac{1}{3}\left(\frac{2}{3}a-6y+9\right)\\ =\frac{1}{3}\left(\frac{2x-18}{3}y+9\right)\ge 0.\end{array}$

If $n_1=3$ and $4\le x\le 8$, this means that $\left|S\right|=1$. Suppose $x=n_s$ and let $\frac{a}{3n_s}=b\ge 3$. By simple checking, we find that the value $x+y-xy-\lceil \frac{y}{x}\rceil$ meet maximum while $x=n_1$ for $N=\left\{3,3,4\right\}$, $\left\{3,4,4\right\}$ or $\left\{3,3,5\right\}$. Thus, we get

$\begin{array}{c}I-\left(x+y-xy-\lceil \frac{y}{x}\rceil \right)=3+\frac{a}{3}-\lceil \frac{a}{3^2}\rceil -\left(n_s+\frac{a}{n_s}-\lceil \frac{a}{n_s^2}\rceil \right)\\ =\left(3-n_s\right)+\left(n_s-3\right)b-\lceil \frac{a}{3^2}\rceil +\lceil \frac{a}{n_s^2}\rceil \\ \ge \left(n_s-3\right)\left(b-1\right)-\frac{a}{3^2}-1+\frac{a}{n_s^2}\\ =\left(n_s-3\right)\left(b-1\right)-\frac{b{n}_s}{3}+\frac{3b}{n_s}-1\end{array}$

$\begin{array}{l}=\left(n_s-3\right)\left(b-1\right)-\left(n_s-3\right)\left(n_s+3\right)\frac{1}{3n_s}b-1\\ =\left(n_s-3\right)\left[\left(b-1\right)-\frac{n_s+3}{3n_s}b\right]-1\\ =\left(n_s-3\right)\left[b\left(1-\frac{n_s+3}{3n_s}\right)-1\right]-1.\end{array}$

Clearly, If $n_s\ge 6$, then $\left(n_s-3\right)\left(b\left(1-\frac{n_s+3}{3n_3}\right)-1\right)-1\ge 3\left(b\times \frac{1}{2}-1\right)-1\ge 0$. If $n_s=5$, consider $b\ge 4$, then we have $\left(n_s-3\right)\left(b\left(1-\frac{n_s+3}{3n_3}\right)-1\right)-1\ge 2\left(4\times \frac{7}{15}-1\right)-1\ge 0$. If $n_s=4$, consider $b\ge 5$, then $\left(n_s-3\right)\left(b\left(1-\frac{n_s+3}{3n_3}\right)-1\right)-1\ge 5\times \frac{5}{12}-1-1\ge 0$.

This completes the proof.

By the above argument, we discuss the rupture degree of tori $C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}$. Notice that cycle $C_{n_1{n}_2\cdots n_k}$ is a spanning subgraph of $C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}$. Firstly, by Lemmas 2.1 and 2.2, we directly get the upper bound.

Theorem 3.5. For all integers $n_1,n_2,\cdots ,n_k\ge 3$, the rupture degree of tori is

$r\left(C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}\right)\le \{\begin{array}{ll}-2,\hfill & \text{if}\text{all}{n}_i\text{are}\text{odd},\hfill \\ -1,\hfill & \text{if}\text{some}{n}_i\text{is}\text{even}.\hfill \end{array}$

Theorem 3.6. Let $n_1,\cdots ,n_k$ be integers with $3\le n_1\le n_2\le \cdots \le n_k$. If some $n_i$ is odd, then the rupture degree of tori is

$r\left(C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}\right)\ge n_1+\left(n_2\cdots n_k\right)\left(1-n_1\right)-\lceil \frac{n_2\cdots n_k}{n_1}\rceil$.

Proof. Notice that $C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}$ is spanning subgraph of $K_x\times K_y$ such that $xy={\displaystyle {\prod }_{i=1}^k{n}_i}$ with $x={\displaystyle {\prod }_{n_i\in S}{n}_i}\le y={\displaystyle {\prod }_{n_i\in T}{n}_i}$. By Lemmas 2.1, 3.2 and Theorem 2.8, we have

$\begin{array}{c}r\left(C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}\right)\ge r\left(K_{n_1}\times K_{n_2\times \cdots \times n_k}\right)\\ =n_1+\left(n_2\cdots n_k\right)\left(1-n_1\right)-\lceil \frac{n_2\cdots n_k}{n_1}\rceil .\end{array}$

In particular, if all $n_i$ are even, $C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}$ is a spanning subgraph of $K_{\frac{n_1{n}_2\cdots n_k}{2},\frac{n_1{n}_2\cdots n_k}{2}}$, so by Lemmas 2.1, 3.1 and Theorem 3.5, we get

Theorem 3.7. If all $n_i$ are evens, the rupture degree of tori is $r\left(C_{n_1}\times C_{n_2}\times \cdots \times C_{n_k}\right)=-1$.

Acknowledgements

The authors would like to thank anonymous reviewers for their valuable comments and suggestions to improve the quality of the article. This work was supported by NSFC QHAFFC No. 2022-ZJ-753.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Li, F.W. and Li, X.L. (2004) Computing the Rupture Degrees of Graphs. Proceedings of 7th International Symposium on Parallel Architectures, Algorithms and Networks, Hong Kong, 10-12 May 2004, 368-373.
[2]	Li, Y.K., Zhang, S.G. and Li, X.L. (2005) Rupture Degree of Graphs. International Journal of Computer Mathematics, 82, 793-803. https://doi.org/10.1080/00207160412331336062
[3]	Li, Y.K. (2006) An Algorithm for Computing the Rupture Degree of Tree. Computer Engineering and Applications, 42, 52-54.
[4]	Barefoot, C.A., Entringer, R. and Swart, H.C. (1987) Vulnerability in Graphs—A Comparative Survey. Journal of Combinatorial Mathematics and Combinatorial Computing, 1, 13-22.
[5]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan, London; Elsevier, New York.