On the inverse graph of a finite group and its rainbow connection number

Rian Febrian Umbara, A.N.M. Salman, Pritta Etriana Putri

Abstract


A rainbow path in an edge-colored graph G is a path that every two edges have different colors. The minimum number of colors needed to color the edges of G such that every two distinct vertices are connected by a rainbow path is called the rainbow connection number of G. Let (Γ, *) be a finite group with TΓ = {t ∈ Γ|t ≠ t−1}. The inverse graph of Γ, denoted by IG(Γ), is a graph whose vertex set is Γ and two distinct vertices, u and v, are adjacent if u * v ∈ TΓ or v * u ∈ TΓ. In this paper, we determine the necessary and sufficient conditions for the inverse graph of a finite group to be connected. We show that the inverse graph of a finite group is connected if and only if the group has a set of generators whose all elements are non-self-invertible. We also determine the rainbow connection numbers of the inverse graphs of finite groups.

Keywords


finite group, inverse graph, rainbow connection number

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2023.11.1.11

References

G. Aalipour, S. Akbari, P.J. Cameron, R. Nikandish, and F. Shaveisi, On the structure of the power graph and the enhanced power graph of a group, Electron. J. Combin., 24 (2017), P3.16.

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

S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Transactions on Computers, 38 (1989), 555–566.

M.R. Alfuraidan and Y.F. Zakariya, Inverse graphs associated with finite groups, Electron. J. Graph Theory Appl., 5 (1) (2017), 142–154.

F. Ali and Y. Li, The connectivity and the spectral radius of commuting graphs on certain finite groups, Linear and Multilinear Algebra, 69 (2021), 281–285.

S. Bau, P. Johnson, E. Jones, K. Kumwenda, and R. Matzke, Rainbow connectivity in some Cayley graphs, Australas. J. Combin., 71 (2018), 381–393.

P. Cayley, Desiderata and suggestions: No. 2. The Theory of groups: graphical representation, Amer. J. Math., 1 (1878), 174–176.

I. Chakrabarty, S. Ghosh, and M.K. Sen, Undirected power graphs of semigroups, Semigroup Forum, 78 (2009), 410–426.

G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohem., 133 (2008), 85–98.

R. Diestel, Graph theory, Springer-Verlag, New York, NY, USA, 2005.

D.S. Dummit and R.M. Foote, Abstract algebra (3rd Edition), John Wiley & Sons, Inc., New Jersey, NJ, USA, 2004.

L.A. Dupont, D.G. Mendoza, and M. Rodríguez, The rainbow connection number of the enhanced power graph of a finite group, Electron. J. Graph Theory Appl. 11 (1) (2023), 237–246.

D. Fitriani and A.N.M. Salman, Rainbow connection number of amalgamation of some graphs AKCE Int. J. Graphs Combin., 13 (2022), 461–473.

D. Fitriani, A.N.M. Salman, and Z.Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory Appl., 10 (2) (2022), 461–473.

H. Li, X. Li, and S. Liu, The (strong) rainbow connection numbers of Cayley graphs on abelian groups, Computers and Mathematics with Applications, 62 (2011), 4082–4088.

X. Li and Y. Sun, Rainbow connection numbers of line graphs, Ars Combin., 100 (2011), 449–463.

Z. Lu and Y. Ma, Rainbow 2-connection numbers of Cayley graphs, Inform. Process. Lett., 115 (2015), 486–491.

X. Ma, M. Feng, and K. Wang, The rainbow connection number of the power graph of a finite group, Graphs Combin., 32 (2016), 1495–1504.

Y. Ma and Z. Lu, Rainbow connection numbers of Cayley graphs, J. Comb. Optim., 34 (2017), 182–193.

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


Refbacks

  • 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