AUT Journal of Mathematics and Computing

AUT Journal of Mathematics and Computing

Exact double domination in the generalized Sierpiński graphs

Document Type : Original Article

Authors
Mahsa Khatibi
Ali Behtoei
Department of Mathematics, Faculty of Science, Imam Khomeini International University, Qazvin, Iran
10.22060/ajmc.2024.23345.1251
Abstract
A subset $D$ of vertices of a simple graph ‎$‎G‎$ ‎is ‎an exact double dominating set if each vertex $v$ of $G$ is dominated by exactly two vertices of $D$‎, ‎i.e. $|N_G[v]\cap D|=2$‎, ‎in ‎which ‎‎$‎N_G[v]‎$ ‎is ‎the closed neighborhood of $v$ in ‎$‎G‎$‎.‎ The generalized Sierpiński graph $S(G,t)$ is a fractal-like graph that uses $G$ as a building block and can be constructed recursively in ‎$‎t‎$ ‎steps ‎from the base graph $G$. ‎In this paper we study and determine the existence of exact double dominating sets in generalized Sierpiński graphs $S(P_n,t),$‎ ‎$S(C_n,t),$‎ ‎$S(K_{1,n},t)$ and $S(K_n,t)$‎.
Keywords
Domination
Exact double domination
Sierpiński
Generalized Sierpiński
Subjects
[1] D. W. Bange, A. E. Barkauskas, and P. J. Slater, Efficient dominating sets in graphs, in Applications of discrete mathematics (Clemson, SC, 1986), SIAM, Philadelphia, PA, 1988, pp. 189–199.
[2] N. Biggs, Perfect codes in graphs, J. Combinatorial Theory Ser. B, 15 (1973), pp. 289–296.
[3] B. Chaluvaraju, M. Chellali, and K. A. Vidya, Perfect k-domination in graphs, Australas. J. Combin., 48 (2010), pp. 175–184.
[4] M. Chellali, A. Khelladi, and F. Maffray, Exact double domination in graphs, Discuss. Math. Graph Theory, 25 (2005), pp. 291–302.
[5] A. Estrada-Moreno, E. D. Rodr´ıguez-Bazan, and J. A. Rodr´ıguez-Vel´azquez, On distances in generalized Sierpi´nski graphs, Appl. Anal. Discrete Math., 12 (2018), pp. 49–69.
[6] J. F. Fink and M. S. Jacobson, n-domination in graphs, in Graph theory with applications to algorithms and computer science (Kalamazoo, Mich., 1984), Wiley-Intersci. Publ., Wiley, New York, 1985, pp. 283–300.
[7] J. Geetha and K. Somasundaram, Total coloring of generalized Sierpi´nski graphs, Australas. J. Combin., 63 (2015), pp. 58–69.
[8] S. Gravier, M. Kovˇse, and A. Parreau, Generalized Sierpi´nski graphs, in European Conference on Com- binatorics, Graph Theory and Applications, R´enyi Institute, Budapest, Hungary, 2011.
[9] F. Harary and T. W. Haynes, Nordhaus-Gaddum inequalities for domination in graphs, Discrete Math., 155 (1996), pp. 99–105. Combinatorics (Acireale, 1992).
[10] , Double domination in graphs, Ars Combin., 55 (2000), pp. 201–213.
[11] A. M. Hinz, S. Klavˇzar, and S. S. Zemljiˇc, A survey and classification of Sierpi´nski-type graphs, Discrete Appl. Math., 217 (2017), pp. 565–600.
[12] M. Khatibi, A. Behtoei, and F. Attarzadeh, Degree sequence of the generalized Sierpi´nski graph, Contrib. Discrete Math., 15 (2020), pp. 88–97.
[13] S. Klavˇzar and U. Milutinovi´c, Graphs S(n, k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J., 47(122) (1997), pp. 95–104.
[14] F. Ramezani, E. D. Rodr´ıguez-Bazan, and J. A. Rodr´ıguez-Vel´azquez, On the Roman domination number of generalized Sierpi´nski graphs, Filomat, 31 (2017), pp. 6515–6528.
[15] J. A. Rodr´ıguez-Vel´azquez, E. D. Rodr´ıguez-Bazan, and A. Estrada-Moreno, On generalized Sierpi´nski graphs, Discuss. Math. Graph Theory, 37 (2017), pp. 547–560.
[16] J. A. Rodr´ıguez-Vel´azquez and J. Tom´as-Andreu, On the Randi´c index of polymeric networks modelled by generalized Sierpi´nski graphs, MATCH Commun. Math. Comput. Chem., 74 (2015), pp. 145–160.
AUT Journal of Mathematics and Computing
Volume 7, Issue 2
2026
Pages 151-162