Geodesic
The Vertex-Rainbow Connection Number of Some Graph Operations
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 513-530.

Voir la notice de l'article provenant de la source Library of Science

A path in an edge-colored (respectively vertex-colored) graph G is rainbow (respectively vertex-rainbow) if no two edges (respectively internal vertices) of the path are colored the same. An edge-colored (respectively vertex-colored) graph G is rainbow connected (respectively vertex-rainbow connected) if every two distinct vertices are connected by a rainbow (respectively vertex-rainbow) path. The rainbow connection number rc(G) (respectively vertex-rainbow connection number rvc(G)) of G is the smallest number of colors that are needed in order to make G rainbow connected (respectively vertex-rainbow connected). In this paper, we show that for a connected graph G and any edge e = xy ∈ E(G), rvc(G) ≤ rvc(G − e) ≤ rvc(G) + dG−e(x, y) − 1 if G − e is connected. For any two connected, non-trivial graphs G and H, rad(G□H)−1 ≤ rvc(G□H) ≤ 2rad(G□H), where G□H is the Cartesian product of G and H. For any two non-trivial graphs G and H such that G is connected, rvc(G ◦ H) = 1 if diam(G ◦ H) ≤ 2, rad(G) − 1 ≤ rvc(G ◦ H) ≤ 2rad(G) if diam(G) gt; 2, where G ◦ H is the lexicographic product of G and H. For the line graph L(G) of a graph G we show that rvc(L(G)) ≤ rc(G), which is the first known nontrivial inequality between the rainbow connection number and vertex-rainbow connection number. Moreover, the bounds reported are tight or tight up to additive constants.
Keywords: rainbow connection number, vertex-rainbow connection number, Cartesian product, lexicographic product, line graph 
@article{DMGT_2021_41_2_a11,
     author = {Li, Hengzhe and Ma, Yingbin and Li, Xueliang},
     title = {The {Vertex-Rainbow} {Connection} {Number} of {Some} {Graph} {Operations}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {513--530},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a11/}
}
TY  - JOUR
AU  - Li, Hengzhe
AU  - Ma, Yingbin
AU  - Li, Xueliang
TI  - The Vertex-Rainbow Connection Number of Some Graph Operations
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 513
EP  - 530
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a11/
LA  - en
ID  - DMGT_2021_41_2_a11
ER  - 
%0 Journal Article
%A Li, Hengzhe
%A Ma, Yingbin
%A Li, Xueliang
%T The Vertex-Rainbow Connection Number of Some Graph Operations
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 513-530
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a11/
%G en
%F DMGT_2021_41_2_a11
Li, Hengzhe; Ma, Yingbin; Li, Xueliang. The Vertex-Rainbow Connection Number of Some Graph Operations. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 513-530. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a11/

[1] M. Basavaraju, L.S. Chandran, D. Rajendraprasad and A. Ramaswamy, Rainbow connection number and radius, Graphs Combin. 30 (2014) 275–285. doi:10.1007/s00373-012-1267-7

[2] M. Basavaraju, L.S. Chandran, D. Rajendraprasad and A. Ramaswamy, Rainbow connection number of graph power and graph products, Graphs Combin. 30 (2014) 1363–1382. doi:10.1007/s00373-013-1355-3

[3] J.P. Bode and H. Harborth, The minimum size of k-rainbow connected graphs of given order, Discrete Math. 313 (2013) 1924–1928. doi:10.1016/j.disc.2012.07.023

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

[5] Y. Caro, A. Lev, Y. Roditty, Zs. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008) #R57.

[6] S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 21 (2011) 330–347. doi:10.1007/s10878-009-9250-9

[7] L.S. Chandran, A. Das, D. Rajendraprasad and N.M. Varma, Rainbow connection number and connected dominating sets, J. Graph Theory 71 (2012) 206–218. doi:10.1002/jgt.20643

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

[9] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009) 75–81. doi:10.1002/net.20296

[10] L. Chen, X. Li and H. Lian, Further hardness results on the rainbow vertex-connection number of graphs, Theoret. Comput. Sci. 481 (2013) 18–23. doi:10.1016/j.tcs.2013.02.012

[11] L. Chen, X. Li and Y. Shi, The complexity of determining the rainbow vertex-connection of a graph, Theoret. Comput. Sci. 412 (2011) 4531–4535. doi:10.1016/j.tcs.2011.04.032

[12] J. Ekstein, P. Holub, T. Kaiser, M. Koch, S. Matos Camacho, Z. Ryjáček and I. Schiermeyer, The rainbow connection number of 2 -connected graphs, Discrete Math. 313 (2013) 1884–1892. doi:10.1016/j.disc.2012.04.022

[13] T. Gologranc, G. Mekiš and I. Peterin, Rainbow connection and graph products, Graphs Combin. 30 (2014) 591–607. doi:10.1007/s00373-013-1295-y

[14] X. Huang, H. Li, X. Li and Y. Sun, Oriented diameter and rainbow connection number of a graph, Discrete Math. Theor. Comput. Sci. 16 (2014) 51–60.

[15] X. Huang, X. Li, Y. Shi, J. Yue and Y. Zhao, Rainbow connections for outerplanar graphs with diameter 2 and 3, Appl. Math. Comput. 242 (2014) 277–280. doi:10.1016/j.amc.2014.05.066

[16] I. Gutman, Distance in Thorny graphs, Publ. Inst. Math. (Beograd) (N.S.) 63 (1998) 31–36.

[17] S. Klavžar and G. Mekiš, On the rainbow connection of Cartesian products and their subgraphs, Discuss. Math. Graph Theory 32 (2012) 783–793. doi:10.7151/dmgt.1644

[18] M. Knor, L’. Niepel and L’. Šoltés, Centers in line graphs, Math. Slovaca 43 (1993) 11–20.

[19] M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185–191. doi:10.1002/jgt.20418

[20] H. Li, X. Li and S. Liu, Rainbow connection of graphs with diameter 2, Discrete Math. 312 (2012) 1453–1457. doi:10.1016/j.disc.2012.01.009

[21] H. Li, X. Li, Y. Sun and Y. Zhao, Note on minimally d-rainbow connected graphs, Graphs Combin. 30 (2014) 949–955. doi:10.1007/s00373-013-1309-9

[22] H. Li, X. Li and Y. Sun, Rainbow connection number of graphs with diameter 3, Discuss. Math. Graph Theory 37 (2017) 141–154. doi:10.7151/dmgt.1920

[23] H. Li and Y. Ma, Rainbow connection number and graph operations, Discrete Appl. Math. 230 (2017) 91–99. doi:10.1016/j.dam.2017.06.004

[24] X. Li and S. Liu, Tight upper bound of the rainbow vertex-connection number for 2-connected graphs, Discrete Appl. Math. 173 (2014) 62–69. doi:10.1016/j.dam.2014.04.002

[25] X. Li, S. Liu, L.S. Chandran, R. Mathew and D. Rajendraprasad, Rainbow connection number and connecivity, Electron. J. Combin. 19 (2012) #P20.

[26] X. Li and Y. Shi, Rainbow connection in 3-connected graphs, Graphs Combin. 29 (2013) 1471–1475. doi:10.1007/s00373-012-1204-9

[27] X. Li and Y. Sun, Note on the rainbow k-connectivity of regular complete bipartite graphs, Ars Combin. 101 (2011) 513–518.

[28] X. Li and Y. Sun, Rainbow Connections of Graphs (New York, Springer, 2012). doi:10.1007/978-1-4614-3119-0

[29] H. Liu, Â. Mestre and T. Sousa, Rainbow vertex k-connection in graphs, Discrete Appl. Math. 161 (2013) 2549–2555. doi:10.1016/j.dam.2013.04.025

[30] A. Lo, A note on the minimum size of k-rainbow-connected graphs, Discrete Math. 331 (2014) 20–21. doi:10.1016/j.disc.2014.04.024

[31] Z. Lu and Y. Ma, Graphs with vertex rainbow connection number two, Sci. China Math. 58 (2015) 1803–1810. doi:10.1007/s11425-014-4905-0

[32] Y. Mao, F. Yanling, Z. Wang and C. Ye, Rainbow vertex-connection and graph products, Int. J. Comput. Math. 93 (2016) 1078–1092. doi:10.1080/00207160.2015.1047356

[33] I. Schiermeyer, On minimally rainbow k-connected graphs, Discrete Appl. Math. 161 (2013) 702–705. doi:10.1016/j.dam.2011.05.001