Article in volume
Authors:
Title:
More on the rainbow disconnection in graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1185-1204
Received: 2018-10-08 , Revised: 2020-05-18 , Accepted: 2020-05-18 , Available online: 2020-06-02 , https://doi.org/10.7151/dmgt.2333
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\leq k\leq 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.
Keywords:
edge-coloring, edge-connectivity, rainbow disconnection coloring (number), Erdős-Gallai type problem, Nordhaus-Gaddum type bounds, complexity, NP-hard (complete)
References:
- 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 - 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 - T. Beşeri, Edge Coloring of a Graph (İzmir Institute of Technology, İzmir, Turkey, 2004).
- J.A. Bondy and U.S.R. Murty, Graph Theory (Grad. Texts in Math. 244 Springer-Verlag, London, 2008).
- 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 - 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 - G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85–98.
- 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 - 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 - 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 - G.A. Dirac, Circuits in critical graphs, Monatsh. Math. 59 (1955) 178–187.
https://doi.org/10.1007/BF01303792 - 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 - 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 - 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 - 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 - I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718–720.
https://doi.org/10.1137/0210055 - 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 - 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 - 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 - W. Mader, Ein Extremalproblem des Zusammenhangs von Graphen, Math. Z. 131 (1973) 223–231.
https://doi.org/10.1007/BF01187240 - E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177.
https://doi.org/10.2307/2306658 - V.G. Vizing, On an estimate of the chromatic class of a $p$-graph, Diskret. Analiz. 3 (1964) 25–30, in Russian.
Close