Article in volume
Authors:
Title:
Distance-local rainbow connection number
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1027-1039
Received: 2019-10-21 , Revised: 2020-04-08 , Accepted: 2020-04-15 , Available online: 2020-05-16 , https://doi.org/10.7151/dmgt.2325
Abstract:
Under an edge coloring (not necessarily proper), a rainbow path is a path whose
edge colors are all distinct. The $d$-local rainbow connection number $lrc_d(G)$
(respectively, $d$-local strong rainbow connection number $lsrc_d(G)$) is the
smallest number of colors needed to color the edges of $G$ such that any two
vertices with distance at most $d$ can be connected by a rainbow path
(respectively, rainbow geodesic). This generalizes rainbow connection numbers,
which are the special case $d=diam(G)$. We discuss some bounds and exact values.
Moreover, we also characterize all triples of positive integers $d,a,b$ such
that there is a connected graph $G$ with $lrc_d(G)=a$ and $lsrc_d(G)=b$.
Keywords:
rainbow connection, chromatic number, line graph
References:
- R.P. Carpentier, H. Liu, M. Silva and T. Sousa, Rainbow connection for some fa-milies of hypergraphs, Discrete Math. 327 (2014) 40–50.
https://doi.org/10.1016/j.disc.2014.03.013 - G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection number of graphs, Math. Bohem. 133 (2008) 85–98.
- G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75–81.
https://doi.org/10.1002/net.20296 - G. Chartrand, F. Okamoto and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55 (2010) 360–367.
https://doi.org/10.1002/net.20339 - X. Chen and X. Li, A solution to a conjecture on the rainbow connection number, Ars Combin. 104 (2012) 193–196.
- P. Dorbec, I. Schiermeyer, E. Sidorowicz and É. Sopena, Rainbow connection in oriented graphs, Discrete Appl. Math. 179 (2014) 69–78.
https://doi.org/10.1016/j.dam.2014.07.018 - A.B. Ericksen, A matter of security, Graduating Engineer and Computer Careers (2007) 24–28.
- M. Krivelevich and R. Yuster, The rainbow connection of a graph is $($at most$ )$ reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185–191.
https://doi.org/10.1002/jgt.20418 - X. Li and Y. Sun, Rainbow Connections of Graphs (Springer, Boston, 2012).
https://doi.org/10.1007/978-1-4614-3119-0 - X. Li and Y. Sun, An updated survey of rainbow connections of graphs–-a dynamic survey, Theory Appl. Graphs 0 (2017) Article 3.
https://doi.org/10.20429/tag.2017.000103 - F. Septyanto and K. A. Sugeng, Color code techniques in rainbow connection, Electron. J. Graph Theory Appl. 6 (2018) 347–361.
https://doi.org//10.5614/ejgta.2018.6.2.14 - Y. Sun, On rainbow total-coloring of a graph, Discrete Appl. Math. 194 (2015) 171–177.
https://doi.org/10.1016/j.dam.2015.05.012
Close