Strong domination number of some operations on a graph

Document Type : Original paper


1 Department of Mathematics, Yazd University, 89195-741, Yazd, Iran

2 Department of Informatics, University of Bergen, Bergen, Norway


Let $G=(V(G),E(G))$ be a simple graph. A set $D\subseteq V(G)$ is a strong dominating set of $G$, if for every vertex $x\in V(G)\setminus D$ there is a vertex $y\in D$ with $xy\in E(G)$ and $\deg(x)\leq \deg(y)$. The strong domination number $\gamma_{st}(G)$ is defined as the minimum cardinality of a strong dominating set.  In this paper, we examine the effects on $\gamma_{st}(G)$ when $G$ is modified by operations on edge (or edges) of $G$.


Main Subjects

[1] S. Akbari, S. Alikhani, and Y.H. Peng, Characterization of graphs using domination polynomials, Eur. J. Comb. 31 (2010), no. 7, 1714–1724.
[2] S. Alikhani, N. Ghanbari, and S. Soltani, Total dominator chromatic number of k-subdivision of graphs, The Art Discret. Appl. Math. (2023), #P1.10.–9770.1495.2a1
[3] S. Alikhani and Y.H. Peng, Introduction to domination polynomial of a graph, Ars Combin. 114 (2014), 257–266.
[4] C.S. Babu and A.A. Diwan, Subdivisions of graphs: A generalization of paths and cycles, Discrete Math. 308 (2008), no. 19, 4479–4486.
[5] R. Boutrig and M. Chellali, A note on a relation between the weak and strong domination numbers of a graph, Opuscula Math. 32 (2012), no. 2, 235–238.
[6] N. Ghanbari, Secure domination number of k-subdivision of graphs, arXiv preprint arXiv:2110.09190 (2021).
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, NewYork, USA, 1998.
[8] D. Rautenbach, Bounds on the strong domination number, Discrete Math. 215 (2000), no. 1-3, 201–212.–365X(99)00248–4
[9] E. Sampathkumar and L.P. Latha, Strong weak domination and domination balance in a graph, Discrete Math. 161 (1996), no. 1-3, 235–242.–365X(95)00231–K
[10] S.K. Vaidya and S.H. Karkar, On strong domination number of graphs, Applications Appl. Math. 12 (2017), no. 1, 604–612.
[11] S.K. Vaidya and R.N. Mehta, Strong domination number of some cycle related graphs, Int. J. Math. 3 (2017), 72–80.
[12] H. Zaherifar, S. Alikhani, and N. Ghanbari, On the strong dominating sets of graphs, J. Alg. Sys. 11 (2023), no. 1, 65–76.