ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


H. Li, X. Li and Y. Ma


The vertex-rainbow connection number of some graph operations


Discussiones Mathematicae Graph Theory

Received: 2018-07-04, Revised: 2019-01-22, Accepted: 2019-01-22,


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\in E(G)$, $rvc(G)\leq rvc(G-e)\leq rvc(G)+d_{G-e}(x,y)-1$ if $G-e$ is connected. For any two connected, non-trivial graphs $G$ and $H$, $rad(G\square H)-1\leq rvc(G\square H)\leq 2rad(G\square H)$, where $G\square 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\circ H)=1$ if $diam(G\circ H)\leq 2$, $rad(G)-1\leq rvc(G\circ H)\leq 2rad(G)$ if $diam(G)>2$, where $G\circ 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))\leq 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.


rainbow connection number, vertex-rainbow connection num- ber, Cartesian product, lexicographic product, line graph