Connected 2-Dominating Sets and Connected 2-Dominating Polynomials in Friendship Graphs

Document Type : Research Article

Authors

Department of Mathematics, Faculty of Mathematics, Statistics, and Computer Science, Semnan University, Semnan, Iran

Abstract

Let \( G = (V, E) \) be a simple graph. A subset \( D \subseteq V \) is called a connected 2-dominating set of \( G \) if every vertex in \( V \setminus D \) is adjacent to at least two vertices of \( D \), and the induced subgraph \( G[D] \) is connected. The minimum size of such a set is referred to as the connected 2-domination number of \( G \), denoted by \( \gamma_2^c(G) \).  In this work, we investigate the enumeration of connected 2-dominating sets in graphs. For this purpose, we define a generating polynomial, called the connected 2-domination polynomial, which encodes the number of such sets of different cardinalities. Furthermore, several fundamental properties of this polynomial are studied, and explicit forms are derived for certain graph families, in particular the friendship graphs \( F_n \).

Keywords

Main Subjects

Full Text

 

Article PDF

References

[1] Bondy, J. A. and Murty, U. S. R. Graph Theory, Graduate Texts in Mathematics, 244, Springer, London, (2008).
[2] Haynes, T. W., Hedetniemi, S. T., and Slater, P. J. Fundamentals of Domination in Graphs, Marcel Dekker, New York, (1998).
[3] Cockayne, E. J., Favaron, O., Payan, C., and Thomason, A. G. Contributions to the theory of domination, independence and irredundance in graphs, Discrete Mathematics, 127(1-3), 153–161, (2005).
[4] Arshad, M., Imran, M., and Zafar, S. Domination polynomials of specific families of graphs: A survey, Utilitas Mathematica, 111, 257–280, (2020).
[5] Chebolu, P. and Chudnovsky, L. F. Connected domination in graphs, Journal of Graph Theory, 90(4), 401–416, (2019). [6] Alikhani, S. and Peng, Y. H. Dominating Sets and Domination Polynomial of Certain Graphs, submitted.
[7] Nair, P. C. P., Baby, T. A., and Mary, V. M. A. F. 2-Dominating sets and 2-Domination Polynomials of Paths, Journal of Shanghai Jiaotong University, 16, 42–51, (2020).
[8] Nair, P. C. P. and Baby, T. A. 2-Dominating sets and 2-Domination Polynomials of Cycles, Adalya Journal, 9(11), 182–194, (2020).
[9] Alikhani, S. Dominating Sets and domination Polynomials of Graphs, Ph.D. Thesis, University Putra Malaysia, (2009).
[10] Alikhani, S. and Peng, Y. Dominating sets and domination polynomial of cycles, Global Journal of Pure and Applied Mathematics, 4, 151–161, (2008).
[11] Movahedi, F., Akhbari, M. H., and Alikhani, S. The Number of 2-dominating Sets, and 2-domination Polynomial of a Graph, Lobachevskii Journal of Mathematics, 42(4), 751–759, (2021).
[12] Ghanbari, M. and Ramezani, R. Generalized k-rainbow and generalized 2-rainbow domination in graphs, Analytical and Numerical Solutions for Nonlinear Equations, 8(1), 26–30, (2023).
[13] Ghanbari, N. and Alikhani, S. Elliptic Sombor index of graphs from primary subgraphs, Analytical and Numerical Solutions for Nonlinear Equations, 8(1), 99–109, (2023).
[14] Banihashemi Dehkordi, A. and Mohammadian Semnani, S. The maximum edge eccentricity energy of a graph, Analytical and Numerical Solutions for Nonlinear Equations, 8(2), 182–190, (2023).
[15] Salehian Matikolaei, B. Distance D-graphs, graphs that arise from some linear equations, Analytical and Numerical Solutions for Nonlinear Equations, 8(1), 64–75, (2023).
[16] Fellahpour, S. H. A survey on Hamiltonian cycle in Cayley graphs, Analytical and Numerical Solutions for Nonlinear Equations, 8(1), 76–81, (2023). 
Analytical and Numerical Solutions for Nonlinear Equations
Volume 10, Issue 2
December 2025
Pages 264-270

Files

History

  • Receive Date: 10 October 2025
  • Accept Date: 26 December 2025
  • Publish Date: 30 December 2025

Share

How to cite

Statistics