Discussiones Mathematicae Graph Theory (Nov 2022)

Distance-Local Rainbow Connection Number

  • Septyanto Fendy,
  • Sugeng Kiki A.

DOI
https://doi.org/10.7151/dmgt.2325
Journal volume & issue
Vol. 42, no. 4
pp. 1027 – 1039

Abstract

Read online

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