Rainbow disconnection in graphs
Gary Chartrand, Stephen Devereaux, Teresa W. Haynes, Stephen T. Hedetniemi, Ping Zhang · Discussiones Mathematicae Graph Theory · 2018
Let G be a nontrivial connected, edge-colored graph.An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same.An edgecoloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of G -R.We introduce and study the rainbow disconnection number rd(G) of G, which is defined as the minimum number of colors required of a rainbow disconnection coloring of G.It is shown that the rainbow disconnection number of a nontrivial connected graph G equals the maximum rainbow disconnection number among the blocks of G.It is also shown that for a nontrivial connected graph G of order n, rd(G) = n -1 if and only if G contains at least two vertices of degree n -1.The rainbow disconnection numbers of all grids P m P n are determined.Furthermore, it is shown for integers k and n with 1 ≤ k ≤ n -1 that the minimum Full PDF DMGT Page size of a connected graph of order n having rainbow disconnection number k is n + k -2.Other results and a conjecture are also presented.