Distance-Local Rainbow Connection Number

Fendy Septyanto, Kiki A. Sugeng

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
JournalDiscussiones Mathematicae - Graph Theory
DOIs
Publication statusAccepted/In press - 2020

Keywords

  • chromatic number
  • line graph
  • rainbow connection

Fingerprint

Dive into the research topics of 'Distance-Local Rainbow Connection Number'. Together they form a unique fingerprint.

Cite this