1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

More on the Rainbow Disconnection in Graphs

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1185 - 1204
Received: 08 Oct 2018
Accepted: 18 May 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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 ≤ kn − 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.

Keywords

MSC 2010

[1] S. Akbari, D. Cariolaro, M. Chavooshi, M. Ghanbari and S. Zare, Some criteria for a graph to be Class 1, Discrete Math. 312 (2012) 2593–2598. https://doi.org/10.1016/j.disc.2011.09.035 Search in Google Scholar

[2] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466–546. https://doi.org/10.1016/j.dam.2011.12.018 Search in Google Scholar

[3] T. Beşeri, Edge Coloring of a Graph (İzmir Institute of Technology, İzmir, Turkey, 2004). Search in Google Scholar

[4] J.A. Bondy and U.S.R. Murty, Graph Theory (Grad. Texts in Math. 244 Springer-Verlag, London, 2008).10.1007/978-1-84628-970-5 Search in Google Scholar

[5] S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connectivity, J. Comb. Optim. 21 (2011) 330–347. https://doi.org/10.1007/s10878-009-9250-9 Search in Google Scholar

[6] 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. https://doi.org/10.7151/dmgt.2061 Search in Google Scholar

[7] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85–98.10.21136/MB.2008.133947 Search in Google Scholar

[8] L. Chen, X. Li and H. Lian, Nordhaus-Gaddum type theorem for rainbow connection number of graphs, Graphs Combin. 29 (2013) 1235–1247. https://doi.org/10.1007/s00373-012-1183-x Search in Google Scholar

[9] A.G. Chetwynd and A.J.W. Hilton, Regular graphs of high degree are 1-factorizable, Proc. Lond. Math. Soc. (3) 50 (1985) 193–206. https://doi.org/10.1112/plms/s3-50.2.193 Search in Google Scholar

[10] G.A. Dirac, A property of 4-chromatic graphs and remarks on critical graphs, J. Lond. Math. Soc. 27 (1952) 85–92. https://doi.org/10.1112/jlms/s1-27.1.85 Search in Google Scholar

[11] G.A. Dirac, Circuits in critical graphs, Monatsh. Math. 59 (1955) 178–187. https://doi.org/10.1007/BF01303792 Search in Google Scholar

[12] P. Elias, A. Feinstein and C.E. Shannon, A note on the maximum flow through a network, IEE Trans. Inform. Theory, IT 2 (1956) 117–119. https://doi.org/10.1109/TIT.1956.1056816 Search in Google Scholar

[13] L.R. Ford Jr. and D.R. Fulkerson, Maximal flow through a network, Canad. J. Math. 8 (1956) 399–404. https://doi.org/10.4153/CJM-1956-045-5 Search in Google Scholar

[14] F. Harary and T.W. Haynes, Nordhaus-Gaddum inequalities for domination in graphs, Discrete Math. 155 (1996) 99–105. https://doi.org/10.1016/0012-365X(94)00373-Q Search in Google Scholar

[15] A. Hellwig and L. Volkmann, The connectivity of a graph and its complement, Discrete Appl. Math. 156 (2008) 3325–3328. https://doi.org/10.1016/j.dam.2008.05.012 Search in Google Scholar

[16] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718–720. https://doi.org/10.1137/0210055 Search in Google Scholar

[17] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1–38. https://doi.org/10.1007/s00373-012-1243-2 Search in Google Scholar

[18] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs Math. Springer, New York, 2012). https://doi.org/10.1007/978-1-4614-3119-0 Search in Google Scholar

[19] X. Li and Y. Sun, An updated survey on rainbow connections of graphs—a dynamic survey, Theory Appl. Graphs 0 (2017) Art. 3. https://doi.org/10.20429/tag.2017.000103 Search in Google Scholar

[20] W. Mader, Ein Extremalproblem des Zusammenhangs von Graphen, Math. Z. 131 (1973) 223–231. https://doi.org/10.1007/BF01187240 Search in Google Scholar

[21] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177. https://doi.org/10.2307/2306658 Search in Google Scholar

[22] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25–30, in Russian. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo