More on the Rainbow Disconnection in Graphs
Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G,...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2333 |
| _version_ | 1797717970509627392 |
|---|---|
| author | Bai Xuqing Chang Renying Huang Zhong Li Xueliang |
| author_facet | Bai Xuqing Chang Renying Huang Zhong Li Xueliang |
| author_sort | Bai Xuqing |
| collection | DOAJ |
| description | Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two 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 first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ k ≤ n − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(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 rainbow disconnected. |
| first_indexed | 2024-03-12T08:44:10Z |
| format | Article |
| id | doaj.art-b314de9f827049d099d26a49dbd13ab0 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:10Z |
| publishDate | 2022-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-b314de9f827049d099d26a49dbd13ab02023-09-02T16:32:48ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-11-014241185120410.7151/dmgt.2333More on the Rainbow Disconnection in GraphsBai Xuqing0Chang Renying1Huang Zhong2Li Xueliang3Center for Combinatorics and LPMC, Nankai University, Tianjin300071, ChinaCenter for Combinatorics and LPMC, Nankai University, Tianjin300071, ChinaCenter for Combinatorics and LPMC, Nankai University, Tianjin300071, ChinaCenter for Combinatorics and LPMC, Nankai University, Tianjin300071, ChinaLet G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two 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 first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ k ≤ n − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(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 rainbow disconnected.https://doi.org/10.7151/dmgt.2333edge-coloringedge-connectivityrainbow disconnection coloring (number)erdős-gallai type problemnordhaus-gaddum type boundscomplexitynp-hard (complete)05c1505c4005c3568q1768q2568r10 |
| spellingShingle | Bai Xuqing Chang Renying Huang Zhong Li Xueliang More on the Rainbow Disconnection in Graphs Discussiones Mathematicae Graph Theory edge-coloring edge-connectivity rainbow disconnection coloring (number) erdős-gallai type problem nordhaus-gaddum type bounds complexity np-hard (complete) 05c15 05c40 05c35 68q17 68q25 68r10 |
| title | More on the Rainbow Disconnection in Graphs |
| title_full | More on the Rainbow Disconnection in Graphs |
| title_fullStr | More on the Rainbow Disconnection in Graphs |
| title_full_unstemmed | More on the Rainbow Disconnection in Graphs |
| title_short | More on the Rainbow Disconnection in Graphs |
| title_sort | more on the rainbow disconnection in graphs |
| topic | edge-coloring edge-connectivity rainbow disconnection coloring (number) erdős-gallai type problem nordhaus-gaddum type bounds complexity np-hard (complete) 05c15 05c40 05c35 68q17 68q25 68r10 |
| url | https://doi.org/10.7151/dmgt.2333 |
| work_keys_str_mv | AT baixuqing moreontherainbowdisconnectioningraphs AT changrenying moreontherainbowdisconnectioningraphs AT huangzhong moreontherainbowdisconnectioningraphs AT lixueliang moreontherainbowdisconnectioningraphs |