Dominating Sets and Connectivity Preservation in Power Graphs of Symmetric and Cyclic Groups
DOI:
https://doi.org/10.59632/leibniz.v6i01.746Keywords:
power graph, dominating set, symmetric group, cyclic group, connectivityAbstract
The power graph P(G) is a simple graph associated with a group G that represents power relations among its elements. Although power graphs have been widely studied in connection with domination and connectivity, the effect of removing dominating sets, particularly those excluding the identity element, on graph connectivity has not been examined in detail. This study aims to characterize dominating sets in power graphs of finite groups and to investigate whether connectivity is preserved after their removal, with emphasis on symmetric groups and cyclic groups. This research employs a theoretical and analytical approach based on group theory and algebraic graph theory. The results show that, for symmetric groups Sn, there exists a dominating set excluding the identity element such that the power graph remains connected after its removal. Furthermore, for cyclic groups Cn, any generator forms a minimum dominating set, and the power graph remains connected after its removal.
Downloads
References
Aalipour, G., Akbari, S., Cameron, P. J., Nikandish, R., & Shaveisi, F. (2017). On the structure of the power graph and the enhanced power graph of a group. Electronic Journal of Combinatorics, 24(3), 1–22. https://doi.org/10.37236/6497
Abawajy, J., Kelarev, A., & Chowdhury, M. (2013). Power graphs: A survey. Electronic Journal of Graph Theory and Applications, 1(2), 125–147. https://doi.org/10.5614/ejgta.2013.1.2.6
Asmarani, E. Y., Syarifudin, A. G., Wardhana, I. G. A. W., & Switrayni, N. W. (2022). The Power Graph of a Dihedral Group. Eigen Mathematics Journal, 4(2), 80–85. https://doi.org/10.29303/emj.v4i2.117
Cameron, P. J., & Ghosh, S. (2011). The power graph of a finite group. In Discrete Mathematics (Vol. 311, Issue 13, pp. 1220–1222). Elsevier BV. https://doi.org/10.1016/j.disc.2010.02.011
Chakrabarty, I., Ghosh, S., & Sen, M. K. (2009). Undirected power graphs of semigroups. Semigroup Forum, 78(3), 410–426. https://doi.org/10.1007/s00233-008-9132-y
Chattopadhyay, S. (2019). Vertex connectivity of the power graph of a finite cyclic group. Discrete Applied Mathematics, 266, 259–271. https://doi.org/10.1016/j.dam.2018.06.001
Chattopadhyay, S. (2020). Erratum: Vertex connectivity of the power graph of a finite cyclic group II. Journal of Algebra and Its Applications, 19(2). https://doi.org/10.1142/S0219498820920012
Davvaz, B. (2021). A First Course in Group Theory. In A First Course in Group Theory. https://doi.org/10.1007/978-981-16-6365-9
Doostabadi, A., & Erfanian, A. (2013). Some Results on Power Graph of Groups. August, 547–550.
Doostabadi, A., & Ghouchan, M. F. D. (2015). On the Connectivity of Proper Power Graphs of Finite Groups. Communications in Algebra, 43(10), 4305–4319. https://doi.org/10.1080/00927872.2014.945093
Hamzeh, A. (2021). On the Automorphisms Group of Finite Power Graphs. Facta Universitatis, Series: Mathematics and Informatics, 36(1), 119. https://doi.org/10.22190/fumi200322010h
Haynes, T. W., Hedetniemi, S. T., & Henning, M. A. (2023). Domination in Graphs: Core Concepts. In Springer Monographs in Mathematics. https://doi.org/10.1007/978-3-031-09496-5
Haynes, T. W., Hedetniemi, S. T., & Slater, P. J. (1998). Fundamentals of Domination in Graph. Marcel Dekker, Inc.
Kelarev, A. V., & Quinn, S. J. (2002). Directed graphs and combinatorial properties of semigroups. Journal of Algebra, 251(1), 16–26. https://doi.org/10.1006/jabr.2001.9128
Malarvizhi, D., & Revathi, V. (2017). A Review on Graphs with Unique Minimum Dominating Sets. International Journal of Mathematics Trends and Technology (IJMTT), 44(1), 32–37. https://doi.org/10.14445/22315373/ijmtt-v44p505
Manju, M. (2025). A Survey on Properties of Some Power Graphs. International Journal For Multidisciplinary Research, 7(4), 1–6. https://doi.org/10.36948/ijfmr.2025.v07i04.52115
Marcus, D. A. (2020). Graph Theory (Vol 53). American Mathematical Society.
Mehranian, Z., Gholami, A., & Ashrafo, A. . . (2016). A Note On The Power Graph of a Finite Group. International Journal of Group Theory, 5(1), 1–10. https://doi.org/10.1007/s11587-020-00520-w
Panda, R. P., & Krishna, K. V. (2018). On connectedness of power graphs of finite groups. Journal of Algebra and Its Applications, 17(10), 1–20. https://doi.org/10.1142/S0219498818501840
Parveen, Manisha, & Kumar, J. (2024). On the minimal (edge) connectivity of graphs and its applications to power graphs of finite groups. 1–6. http://arxiv.org/abs/2408.10606
Pourghobadi, K., & Jafari, S. H. (2018). The diameter of power graphs of symmetric groups. Journal of Algebra and Its Applications, 17(12), 1–11. https://doi.org/10.1142/S0219498818502341
S. Shukla, V. T. (2020). Domination and It’S Type in Graph Theory. Journal of Emerging Technologies and Innovative Research, 7(3), 1549–1557. http://www.jetir.org/papers/JETIR2003225.pdf
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Ika Metiza Maris, Rawdah Adawiyah Tarmizi, Nor Hafizah Md Husin
This work is licensed under a Creative Commons Attribution 4.0 International License.
