Bounds for the rainbow disconnection number of graphs

DOI10.1007/S10114-022-0642-4arXiv2003.13237MaRDI QIDQ6337643FDOQ6337643

Zhong Huang, Xu Qing Bai, Xueliang Li

Publication date: 30 March 2020

Abstract: An edge-cut $R$ of an edge-colored connected graph is called a rainbow-cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices $u$ and $v$ of the graph, 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 first give some tight upper bounds for rd$(G)$, and moreover, we completely characterize the graphs which meet the upper bound of the Nordhaus-Gaddum type results obtained early by us. Secondly, we propose a conjecture that $lambd{a}^{+}(G)leqextnormalrd(G)leqlambd{a}^{+}(G)+1$, where $lambd{a}^{+}(G)$ is the upper edge-connectivity, and prove the conjecture for many classes of graphs, to support it. Finally, we give the relationship between rd$(G)$ of a graph $G$ and the rainbow vertex-disconnection number rvd$(L(G))$ of the line graph $L(G)$ of $G$.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

This page was built for publication: Bounds for the rainbow disconnection number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337643)