Strong rainbow disconnection in graphs
share
Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a 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 u-v-edge-cut. 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, and this edge-coloring is called a strong rainbow disconnection coloring (srd-coloring for short) of G. For a connected graph G, the strong rainbow disconnection number (srd-number for short) of G, denoted by 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 srd(G)=k for each k ∈{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 srd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if 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.
READ FULL TEXT