The rainbow k-connectivity of the non-commutative graph of a finite group
Abstract
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 xy ≠ yx. We prove that the rainbow k-connectivity of Γ(G) is equal to ⌈k/2⌉ + 2, for 3 ≤ k ≤ |Z(G)|.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.7
References
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.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.