Strong rainbow disconnection in graphs¹¹1Supported by NSFC No.11871034 and 11531011.

All graphs considered in this paper are simple, finite and undirected. Let $G=(V(G),E(G))$ be a nontrivial connected graph with vertex-set $V(G)$ and edge-set $E(G)$. For $v\in V(G)$, let $d_{G}(v)$ and $N_{G}(v)$ denote the $degree$ and the $neighborhood$ of $v$ in $G$ (or simply $d(v)$ and $N(v)$, respectively, when the graph $G$ is clear from the context). We use $\Delta(G)$ to denote the maximum degree of $G$. For any notation or terminology not defined here, we follow those used in [5].

Let $G$ be a graph with an edge-coloring $c$: $E(G)\rightarrow[k]=\{1,2,\cdots,k\}$, $k\in\mathbb{N}$, where adjacent edges may be colored the same. When adjacent edges of $G$ receive different colors under $c$, the edge-coloring $c$ is called proper. The chromatic index of $G$, denoted by $\chi^{\prime}(G)$, is the minimum number of colors needed in a proper edge-coloring of $G$. By a famous theorem of Vizing [14], one has that

for every nonempty graph $G$. If $\chi^{\prime}(G)=\Delta(G)$, then $G$ is said to be in Class $1$; if $\chi^{\prime}(G)=\Delta(G)+1$, then $G$ is said to be in Class $2$.

As we know that there are two ways to study the connectivity of a graph, one way is by using paths and the other is by using cuts. The rainbow connection using paths has been studied extensively; see for examples, papers [7, 11, 13] and book [12] and the references therein. So, it is natural to consider the rainbow edge-cuts for the colored connectivity in edged-colored graphs. In [6], Chartrand et al. first studied the rainbow edge-cut by introducing the concept of rainbow disconnection of graphs. In [4] we call all of them global colorings of graphs since they relate global structural property: connectivity of graphs.

An edge-cut of a connected graph $G$ is a set $F$ of edges such that $G-F$ is disconnected. The minimum number of edges in an edge-cut of $G$ is the edge-connectivity of $G$, denoted by $\lambda(G)$. For two distinct vertices $u$ and $v$ of $G$, let $\lambda_{G}(u,v)$ (or simply $\lambda(u,v)$ when the graph $G$ is clear from the context) denote the minimum number of edges in an edge-cut $F$ such that $u$ and $v$ lie in different components of $G-F$, and this kind of edge-cut $F$ is called a minimum $u$-$v$-edge-cut. A $u$-$v$-path is a path with ends $u$ and $v$. The following proposition presents an alternate interpretation of $\lambda(u,v)$ (see [8], [9]).

An edge-cut $R$ of an edge-colored connected graph $G$ is called a rainbow edge-cut if no two edges in $R$ are colored with the same color. Let $u$ and $v$ be two distinct vertices of $G$. A rainbow $u$-$v$-edge-cut is a rainbow edge-cut $R$ of $G$ such that $u$ and $v$ belong to different components of $G-R$. An edge-colored graph $G$ is called rainbow disconnected if for every two distinct vertices $u$ and $v$ of $G$, there exists a rainbow $u$-$v$-edge-cut in $G$, separating them. In this case, the edge-coloring is called a rainbow disconnection coloring (rd-coloring for short) of $G$. The rainbow disconnection number (or rd-number for short) of $G$, denoted by $\textnormal{rd}(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow disconnected. A rd-coloring with $\textnormal{rd}(G)$ colors is called an $optimal$ rd-coloring of $G$.

Remember that in the above Menger’s famous result of Proposition 1.1, only minimum edge-cuts play a role, however, in the definition of rd-colorings we only requested the existence of a $u$-$v$-edge-cut between a pair of vertices $u$ and $v$, which could be any edge-cut (large or small are both OK). This may cause the failure of a colored version of such a nice Min-Max result of Proposition 1.1. In order to overcome this problem, we will introduce the concept of strong rainbow disconnection in graphs, with a hope to set up the colored version of the so-called Max-Flow Min-Cut Theorem.

An edge-colored graph $G$ is called strong rainbow disconnected if for every two distinct vertices $u$ and $v$ of $G$, there exists a both rainbow and minimum $u$-$v$-edge-cut (rainbow minimum $u$-$v$-edge-cut for short) in $G$, separating them. In this case, the edge-coloring is called a strong rainbow disconnection coloring (srd-coloring for short) of $G$. For a connected graph $G$, we similarly define the strong rainbow disconnection number(srd-number for short) of $G$, denoted by $\textnormal{srd}(G)$, as the smallest number of colors that are needed in order to make $G$ strong rainbow disconnected. An $\textnormal{srd}(G)$-coloring with $\textnormal{srd}(G)$ colors is called an $optimal$ srd-coloring of $G$.

The remainder of this paper will be organized as follows. In Section 2, we first obtain some basic results for the srd-numbers of graphs. In Section 3, we study the srd-numbers for some well-known classes of special graphs. In Section 4, we show that for a connected graph $G$, to compute $\textnormal{srd}(G)$ is NP-hard. In particular, we show that it is already NP-complete to decide if $\textnormal{srd}(G)=3$ for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph $G$ it is NP-complete to decide whether $G$ is strong rainbow disconnected.

Let $G$ be a connected graph. Recall that for a pair of distinct vertices $x$ and $y$ of $G$, we say that an edge-cut $\partial(X)$ separates $x$ and $y$ if $x\in X$ and $y\in V\setminus X$. We denote by $C_{G}(x,y)$ the minimum cardinality of such an edge-cut in $G$. Let $X$ be a vertex subset of $G$, and let $\overline{X}=V(G)\setminus X$. Then the graph $G/X$ is obtained from $G$ by shrinking $X$ to a single vertex. A trivial edge-cut is one associated with a single vertex. A block of a graph is a maximal connected subgraph of $G$ containing no cut-vertices. The block decomposition of $G$ is the set of blocks of $G$. From definitions, the following inequalities are obvious.

Our first question is that the new parameter srd-number is really something new, different from rd-number ? However, we have not found any connected graph $G$ with $\textnormal{srd}(G)\neq\textnormal{rd}(G)$. So, we pose the following conjecture.

In the rest of the paper we will show that for many classes of graphs the conjecture is true.

In this section, we characterize all those nontrivial connected graphs with $m$ edges such that $\textnormal{srd}(G)=k$ for each $k\in\{1,2,m\}$, respectively. We first characterize the graphs with $\textnormal{srd}(G)=m$. The following are two lemmas which we will be used.

It follows from Lemma 2.3 that we have the following result.

Case 1. There exists at least one pair of vertices having nontrivial minimum edge-cut.

Let $C_{G}(x,y)$ be a nontrivial minimum $u$-$v$-edge-cut of $G$, where $x,y\in V(G)$, and let $\partial(X)=\min\{C_{G}(x,y)|x,y\in V(G)\}$. Suppose that $\partial(X)$ is a nontrivial minimum $x_{0}$-$y_{0}$-edge-cut in graph $G$, where $x_{0}\in X$, and let $\partial(Y)$ be a minimum $u$-$v$-edge-cut in $G$, where $u,v\in X$ and $y_{0}\in Y$. By Lemma 2.3, we get that every minimum $u$-$v$-edge-cut in $G/\overline{X}$ is a minimum $u$-$v$-edge-cut in $G$. Now we give an edge-coloring $c$ for $G$ by assigning different colors for each edge of $G[X]$ using colors from $[e(G[X])]$ and assigning different colors for each edge of $G[\overline{X}]$ using colors from $[e(G[\overline{X}])]$, respectively, and assigning $|\partial(X)|$ new colors for $\partial(X)$. Note that the set $E_{w}$ of edges incident with $w$ is rainbow for each vertex $w$ of $G$, and $|c|=\max\{e(G[X]),e(G[\overline{X}])\}+|\partial(X)|\leq e(G)-1$ since $e(G[X]),e(G[\overline{X}])\geq 1$.

We can verify that the coloring $c$ is an srd-coloring of $G$. Let $p$ and $q$ be two vertices of $G$. If $p$ and $q$ have a nontrivial minimum edge-cut $C_{G}(p,q)$ in $G$, then $|C_{G}(p,q)|\geq|\partial(X)|$. Suppose that $p\in X$ and $q\in\overline{X}$. Without loss of generality, let $d(p)\leq d(q)$. If $d(p)<|\partial(X)|$, then the set $E_{p}$ of edges incident with $p$ is a rainbow minimum $p$-$q$-edge-cut in $G$ under the coloring $c$; if $|\partial(X)|\leq d(p)\leq d(q)$, then the $\partial(X)$ is a rainbow minimum $p$-$q$-edge-cut in $G$ under the coloring $c$. If $p,q\in X$ ($\overline{X}$), then the minimum $p$-$q$-edge-cut in $G/\overline{X}$ ($G/X$) is a rainbow minimum $p$-$q$-edge-cut in $G$ since the colors of the edges in graph $G/\overline{X}$ ($G/X$) are different from each other under the restriction of coloring $c$.

Case 2. For any two vertices of $G$, there are only trivial minimum edge-cut.

If $G$ is a tree, then $\textnormal{srd}(G)=1$. Obviously, $\textnormal{srd}(G)\leq e(G)-1$ since $G$ is a connected graph with $n\geq 3$. Otherwise, we give a proper edge-coloring for $G$ using $n-1$ colors. Since $G$ is not a tree, we have $n-1\leq e(G)-1$. For any two vertices $p$, $q$ of $G$, without loss of generality, let $d(p)\leq d(q)$, the set $E_{p}$ of edges incident with $p$ is a rainbow minimum $p$-$q$-edge-cut in $G$. $\Box$

By Lemma 2.4, we immediately obtain the following result.

Next, we further characterize the graphs $G$ with $\textnormal{srd}(G)=1$ and $2$, respectively. We first restate two results as lemmas which characterize the graphs with $\textnormal{rd}(G)=1$ and $2$, respectively.

Furthermore, we obtain the following two results.

Conversely, suppose $\textnormal{rd}(G)=2$. Then each block of $G$ is either a $K_{2}$ or a cycle and at least one block of $G$ is a cycle. We can give a 2-edge-coloring $c$ for $G$ as follows. Choose one edge from each cycle to give color $1$. The remaining edges are assigned color $2$. One can easily verify that the coloring $c$ is strong rainbow disconnected. Combined with Proposition 2.1, we have $\textnormal{srd}(G)=2$. $\Box$

By Lemmas 2.6 and 2.7, and Theorems 2.8 and 2.9, we immediately get the following corollary.

Furthermore, we get $\textnormal{srd}(G)=\textnormal{srd}(B)$, where $\textnormal{srd}(B)$ is maximum among all blocks of $G$. It implies that the study of srd-numbers can be restricted to 2-connected graphs.

Let $c_{i}$ be an optimal srd-coloring of $B_{i}$. We define the edge-coloring $c$: $E(G)\rightarrow[k]$ of $G$ by $c(e)=c_{i}(e)$ if $e\in E(B_{i})$. Let $u$ and $v$ be two vertices of $G$. If $u,v\in B_{i}$ $(i\in[t])$, let $C_{G}(u,v)=C^{r}_{B_{i}}(u,v)$, where $C^{r}_{B_{i}}(u,v)$ is the rainbow minimum $u$-$v$-edge-cut in $B_{i}$. Obviously, $C_{G}(u,v)$ is rainbow under the coloring $c_{i}$. Moreover, it is minimum $u$-$v$-edge-cut in $G$. Otherwise, assume that $R$ is a smaller $u$-$v$-edge-cut in $G$. Then $R\cap E(B_{i})$ is also a $u$-$v$-edge-cut in $B_{i}$, which contradicts to the definition of $C^{r}_{B_{i}}(u,v)$ since $|R\cap E(B_{i})|<|C_{B_{i}}(u,v)|$. Hence, the $C_{G}(u,v)$ is a rainbow minimum $u$-$v$-edge-cut in $G$. Suppose that $u\in B_{i}$ and $v\in B_{j}$, where $i<j$ and $i,j\in[t]$. Let $B_{i}x_{i}B_{i+1}x_{i+1}\ldots x_{j-1}B_{j}$ be a unique $B_{i}$-$B_{j}$-path in the block-tree of $G$, and let $x_{i}$ be the cut-vertex between blocks $B_{i}$ and $B_{i+1}$. If $u=x_{i}$ and $v=x_{j-1}$, let $C_{G}(u,v)=\min\{C^{r}_{B_{i+1}}(x_{i},x_{i+1}),\ldots,C^{r}_{B_{j-1}}(x_{j-2},x_{j-1})\}$. If $u=x_{i}$ and $v\neq x_{j-1}$, let $C_{G}(u,v)=\min\{C^{r}_{B_{i+1}}(x_{i},x_{i+1}),\ldots,C^{r}_{B_{j-1}}(x_{j-2},x_{j-1}),C^{r}_{B_{j}}(x_{j-1},v)\}$. If $u\neq x_{i}$ and $v=x_{j-1}$, let $C_{G}(u,v)=\min\{C^{r}_{B_{i}}(u,x_{i}),C^{r}_{B_{i+1}}(x_{i},x_{i+1}),\ldots,C^{r}_{B_{j-1}}(x_{j-2},x_{j-1})\}$. If $u\neq x_{i}$ and $v\neq x_{j-1}$, let $C_{G}(u,v)=\min\{C^{r}_{B_{i}}(u,x_{i}),C^{r}_{B_{i+1}}(x_{i},x_{i+1}),\ldots,C^{r}_{B_{j}}(x_{j-1},v)\}$. By the connectivity of $G$, we know that $\lambda_{G}(u,v)=|C_{G}(u,v)|$, and $C_{G}(u,v)$ is rainbow. Then $C_{G}(u,v)$ is a rainbow minimum $u$-$v$-edge-cut in $G$. Hence, $\textnormal{srd}(G)\leq k$, and so $\textnormal{srd}(G)=k$. $\Box$

In this section, we investigate the srd-numbers of complete graphs, complete multipartite graphs, regular graphs and grid graphs. Again, we will see that the srd-number behaves the same as the rd-number. At first, we restate several results as lemmas which will be used in the sequel.

First, we get the srd-number for complete graphs.

Then, we give the srd-number for complete multipartite graphs.

Case 1. $n_{1}=1$.

First, we have $V_{1}=\{v_{1,1}\}$ and $d(v_{1,1})=n-1$. Let $H=G-\{v_{1,1}\}$. Then $\Delta(H)=n-n_{2}-1$. Then, we construct a proper edge-coloring $c_{0}$ of $H$ using colors from $[\Delta(H)+1]$. For each vertex $x\in V(H)$, since $d_{H}(x)\leq\Delta(H)$, there is an $a_{x}\in[\Delta(H)+1]$ such that $a_{x}$ is not assigned to any edge incident with $x$ in $H$. Since $E(G)=E(H)\cup\{v_{1,1}x\mid x\in N_{G}(v_{1,1})\}$, we now extend the edge-coloring $c_{0}$ of $H$ to an edge-coloring $c$ of $G$ by assigning $c(v_{1,1}x)=a_{x}$ for every vertex $x\in N_{G}(v_{1,1})$. Note that the set $E_{x}$ of edges incident with $x$ is a rainbow set for each vertex $x\in V(G)\setminus v_{1,1}$ in $G$. Suppose $p$ and $q$ are two vertices of $G$. If $p\in V_{i}$ and $q\in V_{j}$ $(1\leq i<j\leq t)$, then the set $E_{q}$ of edges incident with $q$ is a rainbow minimum $p$-$q$-edge-cut in $G$ since $\lambda_{G}(p,q)=n-n_{j}$. If $p,q\in V_{i}$, then the set $E_{q}$ of edges incident with $q$ is a rainbow minimum $p$-$q$-edge-cut in $G$ since $\lambda_{G}(p,q)=n-n_{i}$. Hence, we obtain $\textnormal{srd}(G)\leq\Delta(H)+1=n-n_{2}$.

Case 2. $n_{1}\geq 2$.

Pick a vertex $u$ of $V_{1}$ and let $F=G-u$. Then $\Delta(F)=n-n_{1}$ since $n_{1}\geq 2$ and $F_{\Delta}=G[V_{1}-u]$. It follows from Lemma 3.1 that $F$ is in Class $1$, and so $\chi^{\prime}(F)=n-n_{1}$. Furthermore, for each vertex $x\in N_{G}(u)$, we know $d_{F}(x)\leq\Delta(F)-1=n-n_{1}-1$. Similar to the argument of Case 1, we can construct an edge-coloring $c$ for $G$ such that the set $E_{x}$ of edges incident with $x$ is a rainbow set for each vertex $x\in V(G)\setminus u$ using $n-n_{1}$ colors. Suppose $p$ and $q$ are two vertices of $G$. If $p\in V_{i}$ and $q\in V_{j}$ $(1\leq i<j\leq t)$, then the set $E_{q}$ of edges incident with $q$ is a rainbow minimum $p$-$q$-edge-cut in $G$ since $\lambda_{G}(p,q)=n-n_{j}$. If $p,q\in V_{i}$ $(i\in[t])$, say $q\neq u$, then the set $E_{q}$ of edges incident with $q$ is a rainbow minimum $p$-$q$-edge-cut in $G$ since $\lambda_{G}(p,q)=n-n_{i}$. Hence, $\textnormal{srd}(G)\leq n-n_{1}$. $\Box$

For regular graphs, we only study the srd-number of $k$-edge-connected $k$-regular graphs. Moreover, we obtain that $\textnormal{srd}(G)=k$ if and only if $\chi^{\prime}(G)=k$ for a $k$-edge-connected $k$-regular graph $G$, where $k$ is odd.

By Lemma 3.8 and Theorem 3.10, we immediately get the following corollary.

The Cartesian product $G\Box H$ of two vertex-disjoint graphs $G$ and $H$ is the graph with vertex-set $V(G)\times V(H)$, where $(u,v)$ is adjacent to $(x,y)$ in $G\Box H$ if and only if either $u=x$ and $vy\in E(H)$ or $ux\in E(G)$ and $v=y$. We consider the $m\times n$ grid graph $G_{m,n}=P_{m}\Box P_{n}$, which consists of $m$ horizontal paths $P_{n}$ and $n$ vertical paths $P_{m}$. Now we determine the srd-number for grid graphs.

(i) We get $\textnormal{srd}(G_{1,n})=\textnormal{srd}(P_{n})=1$ by Corollary 2.10.

For the rest of the proof, the vertices of $G_{m,n}$ are regarded as a matrix. Let $x_{i,j}$ be the vertex in row $i$ and column $j$, where $1\leq i\leq m$ and $1\leq j\leq n$.

(ii) We give the same edge-coloring $c$ for $G_{2,n}$ ($n\geq 3$) using colors from the elements of $Z_{3}$ of the integer modulo 3 as in Lemma 3.5 (ii). Define the edge-coloring $c$ for $G_{2,n}$: $c\rightarrow Z_{3}$, and we now restate it as follows.

$\bullet$ $c(x_{i,j}x_{i,j+1})=i+j+1$ for $1\leq i\leq 2$ and $1\leq j\leq n-1$;

$\bullet$ $c(x_{1,j}x_{2,j})=j$ for $1\leq j\leq n-1$.

One can verify that the coloring $c$ is an srd-coloring for $G_{2,n}$. Let $u$ and $v$ be two vertices of $G_{2,n}$. If $u$ and $v$ are in different columns, then two parallel edges between $u$ and $v$ joining vertices in the same two columns form a rainbow minimum $u$-$v$-edge-cut in $G_{2,n}$ since $\lambda(u,v)=2$. Suppose $u$ and $v$ are in the same column. Because the set $E_{u}$ of edges incident with $u$ is rainbow and $\lambda(u,v)=d(u)=d(v)$, the set $E_{u}$ of edges incident with $u$ is a rainbow minimum $u$-$v$-edge-cut in $G_{2,n}$.

(iii) Give the same edge-coloring $c$ as for the graph $G_{3,n}$ ($n\geq 3$) in Lemma 3.5 (iii). Again we use the elements of $Z_{3}$ as the colors here. Define the edge-coloring $c$ for $G_{3,n}$: $c\rightarrow Z_{3}$ as follows.

$\bullet$ $c(x_{i,j}x_{i,j+1})=i+j+1$ for $1\leq i\leq 3$ and $1\leq j\leq n-1$;

$\bullet$ $c(x_{1,j}x_{2,j})=j$ for $1\leq j\leq n-1$;

$\bullet$ $c(x_{2,j}x_{3,j})=j+2$ for $1\leq j\leq n-1$.

Now we show that the coloring $c$ is an srd-coloring of $G_{3,n}$. Observe that the set $E_{x}$ of edges incident with $x$ is rainbow for each vertex $x$ with $d(x)\leq 3$ in $G_{3,n}$ under the coloring $c$. Let $u$ and $v$ be two vertices of $G_{3,n}$. If $u$ and $v$ have at most one vertex with degree $4$, without loss of generality, $2\leq d(u)\leq d(v)\leq 4$, then the set $E_{u}$ of edges incident with $u$ is a rainbow minimum $u$-$v$-edge-cut in $G_{3,n}$ since $\lambda(u,v)=d(u)$. If $d(u)=d(v)=4$, then three parallel edges between $u$ and $v$ joining vertices in the same two columns form a rainbow minimum $u$-$v$-edge-cut in $G_{3,n}$ since $\lambda(u,v)=3$.

(iv) For the graph $G_{m,n}$ ($4\leq m\leq n$), because $G_{m,n}$ is bipartite and $\Delta(G_{m,n})=4$, there exists a proper edge-coloring $c$ using 4 colors. Now we show that the $c$ is an srd-coloring of $G_{m,n}$. Let $u$ and $v$ be two vertices of $G_{m,n}$. Suppose $d(u)\leq d(v)$. Then the set $E_{u}$ of edges incident with $u$ is a rainbow minimum $u$-$v$-edge-cut in $G_{m,n}$ ($4\leq m\leq n$) since $\lambda(u,v)=d(u)$. $\Box$

First, we show that our problem is in NP for any fixed integer $k$.