On the rainbow connection number of the connected inverse graph of a finite group

Articles in Press

Document Type : Indonesia-Japan Conference on Discrete and Computational Geometry, Graphs, and Games

Authors

1 Doctoral Program in Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

2 School of Computing, Telkom University, Bandung, Indonesia

3 Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

Abstract

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 study the rainbow connection number of the connected inverse graph of a finite group Γ, denoted by rc(IG(Γ)), and its relationship to the structure of Γ. We improve the upper bound for rc(IG(Γ)), where Γ is a group of even order. We also show that for a finite group Γ with a connected IG(Γ), all self-invertible elements of Γ is a product of r non-self-invertible elements of Γ for some r≤rc(IG(Γ)). In particular, for a finite group Γ, if rc(IG(Γ))=2, then all self-invertible elements of Γ is a product of two non-self-invertible elements of Γ. The rainbow connection numbers of some inverse graphs of direct products of finite groups are also observed.

Keywords

Main Subjects

References

[1] M.R. Alfuraidan and Y.F. Zakariya, Inverse graphs associated with finite groups, Electron. J. Graph Theory Appl. 5 (2017), no. 1, 142–154. https://doi.org/10.5614/ejgta.2017.5.1.14
[2] S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 21 (2011), no. 3, 330–347. https://doi.org/10.1007/s10878-009-9250-9
[3] G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008), no. 1, 85–98. http://doi.org/10.21136/MB.2008.133947
[4] R. Diestel, Graph Theory, Springer, 2005.
[5] D.S. Dummit and R.M. Foote, Abstract Algebra, Wiley, 2003.
[6] O. Ejima, K.O. Aremu, and A. Audu, Energy of inverse graphs of dihedral and symmetric groups, J. Egyptian Math. Soc. 28 (2020), no. 1, Article number: 43.  https://doi.org/10.1186/s42787-020-00101-8
[7] D. Fitriani and A.N.M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE Int. J. Graphs Comb. 13 (2016), no. 1, 90–99.  https://doi.org/10.1016/j.akcej.2016.03.004
[8] D. Fitriani, A.N.M. Salman, and Z.Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory Appl. 10 (2022), no. 2, 461–473.  https://doi.org/10.5614/ejgta.2022.10.2.9
[9] H. Li, X. Li, and S. Liu, The (strong) rainbow connection numbers of Cayley graphs on Abelian groups, Comput. Math. Appl. 62 (2011), no. 11, 4082–4088.  https://doi.org/10.1016/j.camwa.2011.09.056
[10] H. Li, X. Li, and Y. Sun, Rainbow connection number of graphs with diameter 3, Discuss. Math. Graph Theory 37 (2017), no. 1, 141–154.  https://doi.org/10.7151/dmgt.1920
[11] X. Li and Y. Sun, Rainbow connection numbers of line graphs., Ars Combin. 100 (2011), 449–463.
[12] X. Li and Y. Sun, Rainbow Connections of Graphs, Springer New York, 2012.
[13] Y. Ma and Z. Lu, Rainbow connection numbers of Cayley graphs, J. Comb. Optim. 34 (2017), no. 1, 182–193.  https://doi.org/10.1007/s10878-016-0052-6
[14] K. Mageshwaran, G. Kalaimurugan, B. Hammachukiattikul, V. Govindan, and I.N. Cangul, On L(h,k)-labeling index of inverse graphs associated with finite cyclic groups, J. Math. 2021 (2021), Article ID: 5583433.  https://doi.org/10.1155/2021/5583433
[15] M. Murni, A.E. Hadi, I. Febry, and A. Abdussakir, Anti-adjacency and Laplacian spectra of inverse graph of group of integers modulo n, IOP Conf. Ser.: Mater. Sci. Eng. 807 (2020), Article ID: 012033. https://doi.org/10.1088/1757-899X/807/1/012033
[16] R.F. Umbara, A.N.M. Salman, and P.E. Putri, On the inverse graph of a finite group and its rainbow connection number, Electron. J. Graph Theory Appl. 11 (2023), no. 1, 135–147.  https://doi.org/10.5614/ejgta.2023.11.1.11
[17] R.F. Umbara, A.N.M. Salman, and P.E. Putri, Rainbow connection numbers of the inverse graphs of some finite abelian
groups, AIP Conf. Proc. 2480 (2023), no. 1, Article ID: 030003.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 04 October 2024

Files

Share

How to cite

Statistics