Distance-local rainbow connection number

Given an edge-colored graph, a rainbow path is a path whose edges are all colored by distinct colors. A geodesic is a path of minimum length between two vertices. A (strong) rainbow edge coloring of a graph \(G\) is an edge coloring where any two vertices of \(G\) are joined by a rainbow path (geodesic). The (strong) rainbow connection number of \(G\) is the smallest number of colors in a (strong) rainbow edge coloring of \(G\). This notion was introduced by \textit{G. Chartrand} et al. [Math. Bohem. 133, No. 1, 85--98 (2008; Zbl 1199.05106)]. As pointed out in the paper, rainbow connectivity has been generalized in many ways. In this paper, the authors consider a local variant of rainbow connectivity as follows. A (strong) \(d\)-local rainbow coloring of \(G\) is an edge coloring such that there is a rainbow path (geodesic) between any two vertices at distance at most \(d\) in \(G\), and the (strong) \(d\)-local rainbow connection number of \(G\) is the smallest number of colors in such an edge coloring of \(G\). The authors prove some basic properties of this edge coloring invariant and investigate it for basic families of graphs such as trees and cycles. Moreover, they characterize for which integers \(a\), \(b\) there is a connected graph with \(d\)-local rainbow connection number \(a\) and strong \(d\)-local rainbow connection number \(b\).

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Distance-local rainbow connection number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2158184)