Let $G$ be a nontrivial edge-colored connected graph. An edge-cut $R$ of $G$ is called a {it rainbow edge-cut} if no two edges of $R$ are colored with the same color. For two distinct vertices $u$ and $v$ of $G$, if an edge-cut separates them, then the edge-cut is called a {it $u$-$v$-edge-cut}. An edge-colored graph $G$ is called emph{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 ({it rainbow minimum $u$-$v$-edge-cut} for short) in $G$, separating them, and this edge-coloring is called a {it strong rainbow disconnection coloring} (srd-{it coloring} for short) of $G$. For a connected graph $G$, the emph{strong rainbow disconnection number} (srd-{it number} for short) of $G$, denoted by $textnormal{srd}(G)$, is the smallest number of colors that are needed in order to make $G$ strong rainbow disconnected. In this paper, we first characterize the graphs with $m$ edges such that $textnormal{srd}(G)=k$ for each $k in {1,2,m}$, respectively, and we also show that the srd-number of a nontrivial connected graph $G$ equals the maximum srd-number among the blocks of $G$. Secondly, we study the srd-numbers for the complete $k$-partite graphs, $k$-edge-connected $k$-regular graphs and grid graphs. Finally, 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.
Download