Geodesic
On Proper (Strong) Rainbow Connection of Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 469-479 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 size. Moreover, we completely solve a question proposed by Johnson et al. by proving that if G = K_p1… K_pn, where n≥ 1, and p_1, . . ., p_n gt;1 are integers, then prc(G) = psrc(G) = χ^′(G), where χ^′(G) denotes the chromatic index of G. Finally, we investigate some suffcient conditions for a graph G to satisfy prc(G) = rc(G), and make some slightly positive progress by using a relation between rc(G) and the girth of the graph.
Keywords: proper (strong) rainbow connection number, Cartesian product, chromatic index 
@article{DMGT_2021_41_2_a8,
     author = {Jiang, Hui and Li, Wenjing and Li, Xueliang and Magnant, Colton},
     title = {On {Proper} {(Strong)} {Rainbow} {Connection} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {469--479},
     year = {2021},
     volume = {41},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a8/}
}
TY  - JOUR
AU  - Jiang, Hui
AU  - Li, Wenjing
AU  - Li, Xueliang
AU  - Magnant, Colton
TI  - On Proper (Strong) Rainbow Connection of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 469
EP  - 479
VL  - 41
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a8/
LA  - en
ID  - DMGT_2021_41_2_a8
ER  - 
%0 Journal Article
%A Jiang, Hui
%A Li, Wenjing
%A Li, Xueliang
%A Magnant, Colton
%T On Proper (Strong) Rainbow Connection of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 469-479
%V 41
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a8/
%G en
%F DMGT_2021_41_2_a8
Jiang, Hui; Li, Wenjing; Li, Xueliang; Magnant, Colton. On Proper (Strong) Rainbow Connection of Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 469-479. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a8/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

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

[3] P. Johnson, E. Jones, K. Kumwenda, R. Matzke and S. Bau, Rainbow connectivity in some Cayley graphs, Australas. J. Combin. 71 (2018) 381–393.

[4] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1–38. doi:10.1007/s00373-012-1243-2

[5] X. Li and Y. Sun, An updated survey on rainbow connections of graphs—a dynamic survey, Theory Appl. Graphs 0(1) (2017), Art. 3. doi:10.20429/tag.2017.000103

[6] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer-Verlag, New York, 2012).