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

Distance-Local Rainbow Connection Number

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1027 - 1039
Received: 21 Oct 2019
Accepted: 15 Apr 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(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 lrcd(G) = a and lsrcd(G) = b.

Keywords

MSC 2010

[1] R.P. Carpentier, H. Liu, M. Silva and T. Sousa, Rainbow connection for some families of hypergraphs, Discrete Math. 327 (2014) 40–50. https://doi.org/10.1016/j.disc.2014.03.013 Search in Google Scholar

[2] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection number of graphs, Math. Bohem. 133 (2008) 85–98. Search in Google Scholar

[3] 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 Search in Google Scholar

[4] 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 Search in Google Scholar

[5] X. Chen and X. Li, A solution to a conjecture on the rainbow connection number, Ars Combin. 104 (2012) 193–196. Search in Google Scholar

[6] 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 Search in Google Scholar

[7] A.B. Ericksen, A matter of security, Graduating Engineer and Computer Careers (2007) 24–28. Search in Google Scholar

[8] 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 Search in Google Scholar

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

[10] 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 Search in Google Scholar

[11] 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 Search in Google Scholar

[12] 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 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo