Erdős-Gallai-type results for the rainbow disconnection number of graphs

Abstract

Let $G$ be a nontrivial connected and edge-colored graph. An edge-cut $R$ of $G$ is called a rainbow cut if no two edges of it are colored with a same color. An edge-colored graph $G$ is called rainbow disconnected if for every two distinct vertices $u$ and $v$ of $G$, there exists a $u-v$ rainbow cut separating them. For a connected graph $G$, the rainbow disconnection number of $G$, denoted by $rd(G)$, is defined as the smallest number of colors that are needed in order to make $G$ rainbow disconnected. In this paper, we will study the Erdős-Gallai-type results for $rd(G)$, and completely solve them.

7 pages. arXiv admin note: text overlap with arXiv:1810.09736

References in corpus (1)

• A note on the minimum size of $k$-rainbow connected graphs

Cited by in corpus (1)

• Proper disconnection of graphs