On proper (strong) rainbow connection of graphs

Hui Jiang, Wen J. Li, Xueliang Li, Colton MagnantDiscussiones 2019 · DOI

Abstract

A path in an edge-colored graph G is called a rainbow path if no two edges on the path have the same color. The graph G is called rainbow connected if between every pair of distinct vertices of G, there is a rainbow path. Recently, Johnson et al. considered this concept with the additional requirement that the coloring of G is proper. The proper rainbow connection number of G, denoted by prc(G), is the minimum number of colors needed to properly color the edges of G so that G is rainbow connected. Similarly, the proper strong rainbow connection number of G, denoted by psrc(G), is the minimum number of colors needed to properly color the edges of G such that for any two distinct vertices of G, there is a rainbow geodesic (shortest path) connecting them. In this paper, we characterize those graphs with proper rainbow connection numbers equal to the size or within 1 of the Full PDF
BibTeX
@inproceedings{jiang2019proper,
  author = {Hui Jiang and Wen J. Li and Xueliang Li and Colton Magnant},
  title = {{On proper (strong) rainbow connection of graphs}},
  booktitle = {Discussiones},
  year = {2019},
  doi = {10.7151/dmgt.2201},
}

Loading related content...

Figure