The rainbow k-connectivity of the non-commutative graph of a finite group

Luis A. Dupont, Raquiel López, Miriam Rodríguez


The non-commuting graph Γ(G) of a non-abelian group G is defined as follows. The vertex set V(Γ(G)) of ℾ(G) is G \ Z(G) where Z(G) denotes the center of G and two vertices x and y are adjacent if and only if xyyx. We prove that the rainbow k-connectivity of Γ(G) is equal to ⌈k/2⌉ + 2, for 3 ≤ k ≤ |Z(G)|.


non-commuting graph, non-abelian group, rainbow connectivity, rainbow path

Full Text:




A. Abdollahi, S. Akbari, and H. R. Maimani, Non-commuting graph of a group, J. Algebra 298 (2) (2006), 468–492.

G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity of a graph, Networks 54 (2009), 75–81.

M. R. Darafsheh, Groups with the same non-commuting graph, Discrete Appl. Math. 157 (2009), 833–837.

B. Demoen, N. Phuong-Lan, Graphs with coloring redundant edges, Electron. J. Graph The- ory Appl. 4 (2) (2016), 223–230.

H. Deng, S. Balachandran, S. Elumalai, T. Mansour, Harary index of bipartite graphs Elec- tron. J. Graph Theory Appl. 7 (2) (2019), 365–372.

B. H. Neumann, A problem of Paul Erdos on groups, J. Aust. Math. Soc. 21(Series A) (1976), 467–472.

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, Volume 24, Springer-Verlag, Heidelberg, 2003.

F. Septyanto, K.A. Sugeng, Color code techniques in rainbow connection, Electron. J. Graph Theory Appl. 6 (2) (2018), 347–361.

Y. Wei, X. Ma and K. Wang, Rainbow connectivity of the non-commuting graph of a finite group, J. Algebra Appl. 15 (6) (2016), 1–8.

H. Whitney, Congruent graphs and the connectivity of graphs, American Journal of Matem- atics 54 (1) (1932), 150–168.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats