Rainbow connectivity of the non-commuting graph of a finite group

Abstract

Let $G$ be a finite non-abelian group. The non-commuting graph ${\Gamma }_G$ of $G$ has the vertex set $G\setminus Z(G)$ and two distinct vertices $x$ and $y$ are adjacent if $xy\ne yx$, where $Z(G)$ is the center of $G$. We prove that the rainbow $2$-connectivity of ${\Gamma }_G$ is $2$. In particular, the rainbow connection number of ${\Gamma }_G$ is $2$. Moreover, for any positive integer $k$, we prove that there exist infinitely many non-abelian groups $G$ such that the rainbow $k$-connectivity of ${\Gamma }_G$ is $2$.

8 pages