The Rainbow Connection Number of The Commuting Graph of a Finite Non-abelian Group

Let $\Gamma$ be a finite nonabelian group with a nontrivial center and $Z(\Gamma)$ be the center of $\Gamma$. Since any member of $Z(\Gamma)$ commutes with all members of $\Gamma$, any member of $Z(\Gamma)$ is adjacent with all vertices in $V(CG(\Gamma))$. Choose any two members $z_{1}$ and $z_{2}$ from $Z(\Gamma)$. For every element $x\in\Gamma\setminus Z(\Gamma$), the edge $xz_{1}$ is colored with color 1 and the edge $xz_{2}$ is colored with color 2. The edge $z_{1}z_{2}$ is colored with color 3. The other edges of $CG(\Gamma)$ are colored with color 1. With this edge coloring, every two distinct elements $x,y\in\Gamma\setminus Z(\Gamma)$ are connected by the path $xz_{1}z_{2}y$ which has 3 edges with 3 distinct colors. Hence, $rc(CG(\Gamma))\leq 3$.

Now let $\Gamma$ be a finite nonabelian group with a trivial center and has at most three maximal abelian subgroups of order 2. Let $e$ be the identity element of $\Gamma$, $\mathscr{C}=\{C_{1},\dots,C_{m}\}$ be the collection of all maximal abelian subgroups of $\Gamma$ with $m\geq 3$ (since $\Gamma$ is nonabelian), and let $\mathscr{C}$ has exactly $t$ members of order 2, where $0\leq t\leq 3$. Construct a set $\bar{\mathscr{C}}=\{\bar{C}_{1},\dots,\bar{C}_{t}\}$, which is the collection of all maximal abelian subgroups of order 2 and $\hat{C}=(\Gamma\setminus\bigcup\limits_{i=1}^{t}\bar{C}_{i})\cup\{e\}$. Write $\bar{C}_{i}=\{e,\bar{c}_{i}\}$ for every $i\in\{1,\dots,t\}$ and write $\hat{C}=\{e,\hat{c}_{1},\hat{c}_{2},\dots,\hat{c}_{s}\}$ in an order such that $\hat{c}_{i}$ commutes with $\hat{c}_{i-1}$ or with $\hat{c}_{i+1}$ for every $i\in\{1,\dots,s\}$, where $s=|\Gamma|-t-1$.

If $t=0$, then $\bar{\mathscr{C}}=\emptyset$, $\hat{C}=\Gamma$, and we can color the edges of $CG(\Gamma)$ with three colors as follows:

1. (1)

   the edge $e\hat{c}_{i}$ is colored with color 1 if $i$ is odd or color 2 if $i$ is even for every $i\in\{1,2,\dots,s\}$,

2. (2)

   the other edges are colored with color 3.

With this coloring, the rainbow paths between two vertices of $CG(\Gamma)$ are as follows:

1. (1)

   $\hat{c}_{i}\hat{c}_{j}$ if $\hat{c}_{i}$ and $\hat{c}_{j}$ are adjacent, where $i,j\in\{1,2,\dots,s\}$,

2. (2)

   $\hat{c}_{i}e\hat{c}_{j}$ if $\hat{c}_{i}$ and $\hat{c}_{j}$ are not adjacent and the parities of $i$ and $j$ are different, where $i,j\in\{1,2,\dots,s\}$,

3. (3)

   if $\hat{c}_{i}$ and $\hat{c}_{j}$ are not adjacent and the parities of $i$ and $j$ are the same, where $i,j\in\{1,2,\dots,s\}$, then the rainbow path between $\hat{c}_{i}$ and $\hat{c}_{j}$ is $\hat{c}_{i}e\hat{c}_{j-1}\hat{c}_{j}$ if $\hat{c}_{j-1}$ is adjacent to $\hat{c}_{j}$ and $j\neq 1$, or $\hat{c}_{i}e\hat{c}_{j+1}\hat{c}_{j}$ if $\hat{c}_{j+1}$ is adjacent to $\hat{c}_{j}$ and $j\neq s$.

Since every two vertices of $CG(\Gamma)$ are connected by a rainbow path under this edge coloring, we have $rc(CG(\Gamma))\leq 3$.

If $1\leq t\leq 3$, the edge $e\bar{c}_{i}$ is a pendant edge of $CG(\Gamma)$ for every $i\in\{1,\dots,t\}$ and we can color the edges of $CG(\Gamma)$ with three colors as follows:

1. (1)

   the edge $e\bar{c}_{i}$ is colored with color $i$ for every $i\in\{1,\dots,t\}$,

2. (2)

   the edge $e\hat{c}_{i}$ is colored with color 1 if $i$ is odd or color 2 if $i$ is even for every $i\in\{1,2,\dots,s\}$,

3. (3)

   the other edges are colored with color 3.

The rainbow paths between two vertices of $CG(\Gamma)$ under this edge coloring are as follows.

1. (1)

   The rainbow paths between $\hat{c}_{i}$ and $\hat{c}_{j}$, where $i,j\in\{1,2,\dots,s\}$ and $i\neq j$, are the same as the paths in the case of $t=0$.

2. (2)

   For $i,j\in\{1,\dots,t\}$, where $i\neq j$, the rainbow path between $\bar{c}_{i}$ and $\bar{c}_{j}$ is $\bar{c}_{i}e\bar{c}_{j}$.

3. (3)

   For $j\in\{1,2,\dots,s\}$, the rainbow path between $\bar{c}_{1}$ and $\hat{c}_{j}$ is $\bar{c}_{1}e\hat{c}_{j}$ if $j$ is even, $\bar{c}_{1}e\hat{c}_{j-1}\hat{c}_{j}$ if $j$ is odd, $\hat{c}_{j-1}$ is adjacent to $\hat{c}_{j}$, and $j\neq 1$, or $\bar{c}_{1}e\hat{c}_{j+1}\hat{c}_{j}$ if $j$ is odd, $\hat{c}_{j+1}$ and $\hat{c}_{j}$ are adjacent, and $j\neq s$.

4. (4)

   If $t=2$ and $j\in\{1,2,\dots,s\}$, the rainbow path between $\bar{c}_{2}$ and $\hat{c}_{j}$ is $\bar{c}_{2}e\hat{c}_{j}$ if $j$ is odd, $\bar{c}_{2}e\hat{c}_{j-1}\hat{c}_{j}$ if $j$ is even and $\hat{c}_{j-1}$ is adjacent to $\hat{c}_{j}$, or $\bar{c}_{2}e\hat{c}_{j+1}\hat{c}_{j}$ if $j$ is even, $\hat{c}_{j+1}$ is adjacent to $\hat{c}_{j}$, and $j\neq s$. The rainbow paths between $\bar{c}_{1}$ and $\hat{c}_{j}$ are the same as the paths in point 3.

5. (5)

   If $t=3$ and $j\in\{1,2,\dots,s\}$, the rainbow path between $\bar{c}_{3}$ and $\hat{c}_{j}$ is $\bar{c}_{3}e\hat{c}_{j}$ . The rainbow paths between $\bar{c}_{1}$ and $\hat{c}_{j}$, and between $\bar{c}_{2}$ and $\hat{c}_{j}$, are the same as the paths in point 3 and 4, respectively.

Since every two distinct vertices of $CG(\Gamma)$ are connected by a rainbow path under this edge coloring, we get $rc(CG(\Gamma))\leq 3$. From the above explanations, we conclude that if $\Gamma$ has a nontrivial center or if $\Gamma$ is a group with a trivial center and has at most three maximal abelian subgroups of order 2, then $rc(CG(\Gamma))\leq 3$.

Now suppose that $\Gamma$ is a finite nonabelian group with a trivial center and has at least $4$ maximal abelian subgroups of order 2. Therefore, $CG(\Gamma)$ has at least $4$ pendant edges and $rc(CG(\Gamma))\geq 4$. Thus, if $rc(CG(\Gamma))\leq 3$, then $\Gamma$ has a nontrivial center or $\Gamma$ is a group with a trivial center and has at most three maximal abelian subgroups of order 2. ∎

Let $\Gamma$ be a non-Abelian finite group with $|Z(\Gamma)|\geq 2$ and having $n$ maximal Abelian subgroups where $n\geq 3$. Let $C=\{C_{1},\dots,C_{n}\}$ be the collection of all maximal Abelian subgroups of $\Gamma$. Since $\Gamma$ is non-Abelian, $CG(\Gamma)$ is not a complete graph. Therefore, $rc(CG(\Gamma))\geq 2$.

Select any element $u_{i}$ from $C_{i}\setminus Z(\Gamma)$ for each $i\in\{1,2,\dots,n\}$ and form a set $U=\{u_{1},u_{2},\dots,u_{n}\}$. If there exist two elements $u_{i}$ and $u_{j}$ such that $u_{i}=u_{j}$ for distinct $i$ and $j$ in $\{1,2,\dots,n\}$ (i.e., $u_{i}$ and $u_{j}$ are the same non-central element in an intersection of two or more maximal Abelian subgroups), then remove one of the two elements from $U$. Hence, $|U|\leq|C|$.

Let $J$ be an induced subgraph of $CG(\Gamma)$ with the vertex set $V(J)=Z(\Gamma)\cup U$. Note that every member of $Z(\Gamma)$ is adjacent to every other element in $Z(\Gamma)\cup U$ in $J$. Suppose $J$ is edge-colored with two colors. Each $u_{i}\in U$ is labeled with an ordered $|Z(\Gamma)|$-tuple, denoted by $K_{u_{i}}=(k_{u_{i}1},k_{u_{i}2},\dots,k_{u_{i}|Z(\Gamma)|})$, where $k_{u_{i}j}$ is the color of the edge $u_{i}z_{j}$, with $z_{j}$ being a member of $Z(\Gamma)$, and $j\in\{1,\dots,|Z(\Gamma)|\}$. Since only two colors are used to color the edges of $J$, we have $k_{u_{i}j}\in\{1,2\}$ for each $u_{i}\in U$ and each $j\in\{1,\dots,|Z(\Gamma)|\}$. Therefore, the number of distinct ordered $|Z(\Gamma)|$-tuples that can be used to label the elements in $U$ is $2^{|Z(\Gamma)|}$.

If $|C|\leq 2^{|Z(\Gamma)|}$, then every two distinct elements in $U$ that come from different maximal Abelian subgroups can be labeled with different $|Z(\Gamma)|$-tuples. If $u_{i}$ and $u_{j}$ are two distinct elements in $(C_{i}\cap C_{j})\setminus Z(\Gamma)$, the shortest rainbow path in $J$ connecting these two elements is the edge $u_{i}u_{j}$. For $u_{i}\in C_{i}\setminus C_{j}$ and $u_{j}\in C_{j}\setminus C_{i}$, the rainbow path of length 2 in the subgraph $J$ that connects $u_{i}$ and $u_{j}$ is $u_{i}z_{l}u_{j}$, where $z_{l}$ is an element of $Z(\Gamma)$ such that $k_{u_{i}l}\neq k_{u_{j}l}$. Since each member of $U$ is chosen arbitrarily from $C_{i}\setminus Z(\Gamma)$ for each $i\in\{1,2,\dots,n\}$, it follows that any two elements from different maximal Abelian subgroups are connected by a rainbow path. Note that any two noncommuting elements in $\Gamma$ do not belong to the same maximal Abelian subgroup. Therefore, if $|C|\leq 2^{|Z(\Gamma)|}$, the edges of the graph $CG(\Gamma)$ can be colored with two colors such that any two non-adjacent vertices are connected by a rainbow path of length 2. Consequently, $rc(CG(\Gamma))\leq 2$. Since $rc(CG(\Gamma))\geq 2$, it follows that $rc(CG(\Gamma))=2$. ∎

Suppose $\Gamma$ is a finite non-Abelian group and $H$ is a subset of $\Gamma$ with $|H|\geq 2$. Let $\Gamma$ have a collection of maximal Abelian subgroups $\mathscr{T}=\{\Theta_{1},\dots,\Theta_{m}\}$ with $m\geq 2$, satisfying $H=\Theta_{i}\cap\Theta_{j}$ for every distinct $i$ and $j$ in $\{1,\dots,m\}$, and let $X=\bigcup\limits_{i=1}^{m}\Theta_{i}$. Since $\Gamma$ is a non-Abelian group and $m\geq 2$, there are two vertices in $CG(\Gamma,X)$ that are not adjacent, which implies that $CG(\Gamma,X)$ is not a complete graph. Consequently, $rc(CG(\Gamma,X))\geq 2$. Any two distinct elements in $\Theta_{i}$ are adjacent in $CG(\Gamma,X)$ for each $i\in\{1,\dots,m\}$, so every two distinct elements in $H$ are adjacent in $CG(\Gamma,X)$. Since $\Theta_{i}\cap\Theta_{j}=H$ for every $i,j\in\{1,\dots,m\}$ with $i\neq j$, each $a\in\Theta_{i}\setminus H$ is not adjacent to any $b\in\Theta_{j}\setminus H$ in $CG(\Gamma,X)$ when $i\neq j$. Hence, the shortest paths in $CG(\Gamma,X)$ connecting $a\in\Theta_{i}\setminus H$ and $b\in\Theta_{j}\setminus H$ with $i\neq j$ are paths of the form $ah_{k}b$ where $h_{k}\in H$ and $k\in\{1,\dots,|H|\}$. These shortest paths have length 2.

Select one element $w_{i}$ from $\Theta_{i}\setminus H$ for each $i\in\{1,\dots,m\}$, then form the subset $W=\{w_{1},\dots,w_{m}\}$. Clearly, any two distinct elements in $W$ are not adjacent in $CG(\Gamma,X)$. Consider the subgraph induced by $CG(\Gamma,X)$ with the vertex set $H\cup W$. Denote this subgraph as $J$. It is evident that $J$ is not a complete graph, so $rc(J)\geq 2$. Next, two cases will be considered to determine the rainbow connection number of the graph $J$.

Case 1: For $m\leq 2^{|H|}$.

Let the edges of $J$ be colored with a 2-coloring $p$. For every two elements $h_{i}$ and $h_{j}$ in $H$, the edge $h_{i}h_{j}$ is colored with color 1. For each $w_{i}\in W$, $i\in\{1,\dots,m\}$, assign a labeled ordered tuple-$|H|$ as $K_{w_{i}}=(k_{w_{i1}},k_{w_{i2}},\dots,k_{w_{i|H|}})$, where $k_{w_{ij}}$ is the color of the edge $w_{i}h_{j}$, $h_{j}\in H$, and $j\in\{1,\dots,|H|\}$. Since the number of colors used is two, $k_{w_{ij}}\in\{1,2\}$ for each $i\in\{1,\dots,m\}$ and each $j\in\{1,\dots,|H|\}$. Thus, the number of possible ordered tuples-$|H|$ for the elements of $W$ is $2^{|H|}$. Note that $|W|=|\mathscr{T}|=m$. If $m\leq 2^{|H|}$, then every two distinct elements of $W$ can be assigned different labeled ordered tuples-$|H|$, ensuring that every two elements of $W$ are connected by a rainbow path in $J$. The rainbow path connecting each pair $w_{i}$ and $w_{j}$ in $W$ has the form $w_{i}h_{l}w_{j}$, where $h_{l}$ is an element of $H$ such that $k_{w_{il}}\neq k_{w_{jl}}$. Therefore, we have $rc(J)\leq 2$. Since $rc(J)\geq 2$, it follows that $rc(J)=2$.

Case 2: For $m>2^{|H|}$.

As in Case 1, each $w_{i}\in W$, $i\in\{1,\dots,m\}$, is assigned a labeled ordered tuple-$|H|$ as $K_{w_{i}}=(k_{w_{i1}},k_{w_{i2}},\dots,k_{w_{i|H|}})$, where $k_{w_{ij}}$ is the color of the edge $w_{i}h_{j}$, $h_{j}\in H$, and $j\in\{1,\dots,|H|\}$.

Just as in Case 1, if we color the edges of the graph $J$ with two colors, the number of possible ordered tuples-$|H|$ for the elements of $W$ is $2^{|H|}$. Since $m>2^{|H|}$, there are at least two vertices $w_{i}$ and $w_{j}$ in $W$ such that $K_{w_{i}}=K_{w_{j}}$. Since $k_{w_{il}}=k_{w_{jl}}$ for each $l\in\{1,\dots,|H|\}$, there is no rainbow path of length 2 connecting $w_{i}$ and $w_{j}$ in $J$. Any other paths in $J$ that are not the shortest paths between $w_{i}$ and $w_{j}$ have length at least 3, so coloring the edges of $J$ with two colors does not result in a rainbow path in $J$ connecting $w_{i}$ and $w_{j}$. Therefore, we have $rc(J)\geq 3$.

Now suppose that each edge $\epsilon$ of $J$ is colored with three colors as follows:

With this coloring, the rainbow paths between any two vertices in $J$ are as follows:

1. (1)

   The rainbow path between any two vertices in $H$ is the edge between those two vertices since every two vertices in $H$ are adjacent.

2. (2)

   The rainbow path between two vertices $w_{i}$ and $w_{j}$ with $i$ and $j$ in $\{1,\dots,|H|\}$ and $i\neq j$ is $w_{i}h_{i}w_{j}$.

3. (3)

   The rainbow path between two vertices $w_{i}$ and $w_{j}$ with $i$ and $j$ in $\{|H|+1,\dots,m\}$ and $i\neq j$ is $w_{i}h_{1}h_{2}w_{j}$.

4. (4)

   The rainbow path between two vertices $w_{i}$ and $w_{j}$ with $i\in\{1,\dots,|H|\}$ and $j\in\{|H|+1,\dots,m\}$ is $w_{i}h_{1}w_{j}$.

From the above description, it is clear that with the coloring $p^{*}$, any two distinct vertices in $J$ are connected by a rainbow path, so $rc(J)\leq 3$. Since $rc(J)\geq 3$, we conclude that $rc(J)=3$.

If $|\Theta_{i}|\geq 4$ for at least one $i\in\{1,\dots,m\}$, then there exists another subgraph in $CG(\Gamma,X)$ that is isomorphic to $J$. In this case, to obtain another subgraph isomorphic to $J$, select one element $w^{\prime}_{i}$ from $\Theta_{i}\setminus H$ for each $i\in\{1,\dots,m\}$, with $w^{\prime}_{i}\neq w_{i}$ for at least one $i\in\{1,\dots,m\}$. Then form the subset $W^{\prime}=\{w^{\prime}_{1},\dots,w^{\prime}_{m}\}$. Clearly, any two distinct elements in $W^{\prime}$ are not adjacent in $CG(\Gamma,X)$. The subgraph of $CG(\Gamma,X)$ induced by $H\cup W^{\prime}$, call it subgraph $J^{\prime}$, is isomorphic to $J$.

In $CG(\Gamma,X)$, there are $\prod_{i=1}^{m}|\Theta_{i}\setminus H|$ subgraphs that are isomorphic to $J$. Since these subgraphs are isomorphic to $J$, the rainbow connection number of each of these subgraphs is the same as $rc(J)$. Any two non-adjacent vertices in $CG(\Gamma,X)$ lie in the same subgraph, either $J$ or a subgraph isomorphic to $J$.

Next, the rainbow connection number $rc(J)$ will be used to determine $rc(CG(\Gamma,X))$. As with determining $rc(J)$, the determination of $rc(CG(\Gamma,X))$ will be divided into two cases.

Case 1: For $m\leq 2^{|H|}$. Color the edges of $CG(\Gamma,X)$ using the following edge-coloring scheme:

1. (1)

   The subgraph $J$, and all subgraphs isomorphic to $J$, are colored using the minimum rainbow coloring for $J$, which uses two colors.

2. (2)

   All other edges in $CG(\Gamma,X)$ are colored with color 1.

Since any two non-adjacent vertices in $CG(\Gamma,X)$ lie in the same subgraph (either the subgraph $J$ or a subgraph isomorphic to $J$), with the above edge-coloring, any two non-adjacent vertices in $CG(\Gamma,X)$ are connected by a rainbow path. Therefore, $rc(CG(\Gamma,X))\leq 2$. Since $rc(CG(\Gamma,X))\geq 2$, we conclude that $rc(CG(\Gamma,X))=2$.

Case 2: For $m>2^{|H|}$. Color the edges of $CG(\Gamma,X)$ using the following edge-coloring scheme:

1. (1)

   The subgraph $J$, and all subgraphs isomorphic to $J$, are colored using the minimum rainbow coloring for $J$, which uses three colors.

2. (2)

   All other edges in $CG(\Gamma,X)$ are colored with color 1.

Since any two non-adjacent vertices in $CG(\Gamma,X)$ lie in the same subgraph (either the subgraph $J$ or a subgraph isomorphic to $J$), with the above edge-coloring, any two non-adjacent vertices in $CG(\Gamma,X)$ are connected by a rainbow path. Thus, $rc(CG(\Gamma,X))\leq 3$. If we attempt to color the edges of $CG(\Gamma,X)$ with fewer than three colors, then there exist two non-adjacent vertices in the subgraph $J$ that are not connected by a rainbow path, implying that $rc(CG(\Gamma,X))\geq 3$. Therefore, we conclude that $rc(CG(\Gamma,X))=3$.

From the above results, several conclusions can be drawn. If $m\leq 2^{|H|}$, then $rc(CG(\Gamma,X))=2$. If $m>2^{|H|}$, then $rc(CG(\Gamma,X))=3$. Thus, we can conclude that $rc(CG(\Gamma,X))=2$ if and only if $m\leq 2^{|H|}$, and $rc(CG(\Gamma,X))=3$ if and only if $m>2^{|H|}$.

∎

Let $|Z(\Gamma)|\geq 2$, $m>2^{|H|}$, and $X=\bigcup\limits_{i=1}^{m}\Theta_{i}$. According to Theorem 3.1, $rc(CG(\Gamma))\leq 3$. Since $|Z(\Gamma)|\geq 2$, we get $|H|\geq 2$. According to Theorem 3.3, $rc(CG(\Gamma,X))=3$. It is obvious that $CG(\Gamma,X)$ is a subgraph of $CG(\Gamma)$. The length of any path $P$ in $CG(\Gamma)$, whose $E(P)$ is not the subset of $E(CG(\Gamma,X))$, that connects any two nonadjacent vertices $a\in\Theta_{i}\setminus H$ and $b\in\Theta_{j}\setminus H$ for $i\neq j$ is at least $3$. Therefore, we need an edge coloring with at least 3 colors to make $CG(\Gamma)$ rainbow-connected, and hence $rc(CG(\Gamma))\geq 3$. Since $rc(CG(\Gamma))\leq 3$, we get $rc(CG(\Gamma))=3$.