Independent 2-domination polynomials in complete bipartite graphs
Hamed Mahmoodzadehhamedmahmudzade@semnan.ac.irDepartment of MathematicsFaculty of Mathematics, Statistics, and Computer ScienceSemnan UniversitySemnan, 35131-19111, Iran0009-0002-7264-3796View full profile → , *Saied Mohammadian SemnaniCorresponding authors_mohammadian@semnan.ac.irDepartment of MathematicsFaculty of Mathematics, Statistics, and Computer ScienceSemnan UniversitySemnan, 35131-19111, Iran0000-0001-6755-4911View full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 May 2025
- Published Online:
- 06 Oct 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-2166
- Pages:
- 1–11
Abstract
This paper investigates the independent 2-domination polynomial of complete bipartite graphs Km, n. We establish closed formulas for this polynomial and describe all independent 2-dominating sets in such graphs. The findings illustrate how the bipartite structure determines the enumeration of these sets and provide further insight into domination-type polynomials in special graph families.
Keywords
Subject Classifications
References
[1] F. Riaz and K. M. Ali, “Applications of graph theory in computer science,” in Proc. Third Int. Conf. Computational Intelligence, Communication Systems and Networks, IEEE (2011).
[2] J. A. Dayap, L. F. Casinillo, B. S. Anand, J. S. Estorosos, and R. B. Villeta, “Domination in graph theory: A bibliometric analysis of research trends, collaboration and citation networks,” arXiv preprint arXiv:2503.08690 (2025).
[3] W. Goddard and M. A. Henning, “Independent domination in graphs: A survey and recent results,” Discrete Mathematics, vol. 313, no. 7, pp. 839–854 (2013).
[4] R. E. Leonida and R. C. Allosa, “Independent 2-domination in graphs,” Applied Mathematical Sciences, vol. 12, no. 12, pp. 581–585 (2018).
[5] J. Raczek, “Polynomial algorithm for minimal (1, 2)-dominating set in networks,” Electronics, vol. 11, no. 3, p. 300 (2022).
[6] S. Prabhu, A. K. Arulmozhi, and M. Arulperumjothi, “Certain domination parameters and their resolving versions of fractal cubic networks,” Fractal and Fractional, vol. 8, no. 12, p. 747 (2024).
[7] P. C. Priyanka Nair, T. Anitha Baby, and V. M. Arul Flower Mary, “2-dominating sets and 2-domination polynomials of paths,” Journal of Shanghai Jiaotong University, vol. 16, pp. 42–51 (2020).
[8] P. C. Priyanka Nair and T. Anitha Baby, “2-dominating sets and 2-domination polynomials of cycles,” Adalya Journal, vol. 9, no. 11, pp. 182–194 (2020).
[9] S. Alikhani, Dominating Sets and Domination Polynomials of Graphs, Ph.D. dissertation, Universiti Putra Malaysia (Mar. 2009).
[10] S. Alikhani and Y. Peng, “Dominating sets and domination polynomial of cycles,” Global Journal of Pure and Applied Mathematics, vol. 4, pp. 151–161 (2008).
[11] F. Movahedi, M. H. Akhbari, and S. Alikhani, “The number of 2-dominating sets and 2-domination polynomial of a graph,” Lobachevskii Journal of Mathematics, vol. 42, no. 4, pp. 751–759 (2021).
[12] S. Alikhani and Y. H. Peng, “Dominating sets and domination polynomial of certain graphs,” submitted for publication.
[13] N. Jafari and S. Alikhani, “On the roots of total domination polynomial of graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 23, no. 4, pp. 795–807 (2019).
[14] D. A. Mojdeh and A. S. Emadi, “Hop domination polynomial of graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 23, no. 4, pp. 825–840 (2019).
[15] P. S. K. Reddy and P. S. Hemavathi, “Generalization of bipartite graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 23, no. 3, pp. 787–793 (2020).
[16] S. A. Swadi and A. A. Najim, “The generalized k-connectivity of equally complete bipartite graphs and their line graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 27, no. 5, pp. 1567–1573 (2024).
[17] S. Alikhani and Y. H. Peng, “Introduction to domination polynomial of a graph,” Ars Combinatoria, vol. 114, pp. 257–266 (2014).
[18] S. Alikhani and F. Jafari, “On the unimodality of independence polynomial of certain classes of graphs,” Transactions on Combinatorics, vol. 2, no. 3, pp. 33–41 (2013).
[19] M. Dod, “The independent domination polynomial,” to appear. [Online]. Available: http://arxiv.org/1602.08250.
[20] F. M. Dong, K. M. Koh, and K. L. Teo, Chromatic Polynomials and Chromaticity of Graphs. Singapore: World Scientific Publishing Co. Pte. Ltd. (2005).
[21] V. E. Levit and E. Mandrescu, “A family of graphs whose independence polynomials are both palindromic and unimodal,” Carpathian Journal of Mathematics, vol. 23, no. 1–2, pp. 108–116 (2007).
[22] A. Klobučar, “Independent sets and independent dominating sets in the strong product of paths and cycles,” Mathematical Communications, vol. 10, no. 1, pp. 23–30 (2005).
[23] W. Goddard and M. A. Henning, “Independent domination in graphs: A survey and recent results,” Discrete Mathematics, vol. 313, pp. 839–854 (2013).
[24] M. Cortes, “Independence domination numbers of complete grid graphs,” Master’s thesis (1991).
[25] S. Jahari and S. Alikhani, “On the independent domination polynomial of a graph,” Discrete Applied Mathematics, vol. 289, pp. 416–426 (2021).
[26] E. M. Garzón, J. A. Martínez, J. J. Moreno, and M. L. Puertas, “On the 2-domination number of cylinders with small cycles,” Fundamenta Informaticae, vol. 184, no. 1, pp. 1–20 (2022).
[27] D. Bakhshesh, M. Farshi, and M. R. Hooshmandasl, “2-domination number of generalized Petersen graphs,” Proceedings of the Indian Academy of Sciences – Mathematical Sciences, vol. 128, pp. 615–624 (2018).
[28] F. Miao, W. Fan, M. Chellali, R. Khoeilar, S. M. Sheikholeslami, and M. Soroudi, “On two open problems on double vertex-edge domination in graphs,” Mathematics, vol. 7, no. 9, p. 805 (2019).
[29] J. A. Bondy and U. S. R. Murty, Graph Theory. New York, NY, USA: Springer (2008).
