ON THE STRONG DOMINATING SETS OF GRAPHS

Document Type : Original Manuscript

Authors

1 Department of Mathematical Sciences, Yazd University, P.O. Box 89195-741, Yazd, Iran.

2 Department of Informatics, University of Bergen, P.O. Box 7803, 5020 Bergen, Norway.

Abstract

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 calculate $\gamma_{st}(G)$ for specific graphs and study the number of strong dominating sets of some graphs.

Keywords

References

1. S. Akbari, S. Alikhani, Y. H. Peng, Characterization of graphs using domination polynomial, Europ. J. Combin., 31 (2010), 1714–1724.
2. S. Alikhani, J. I. Brown, S. Jahari, On the domination polynomials of friendship graphs, Filomat, 30(1) (2016), 169–178.
3. S. Alikhani, Y. H. Peng, Dominating sets and domination polynomials of certain graphs, II, Opuscula Math., 30(1) (2010), 37–51.
4. S. Alikhani, Y. H. Peng, Dominating sets and domination polynomials of paths, Int. J. Math. Math. Sci., (2009), Article ID: 542040.
5. S. Alikhani, Y.H. Peng, Introduction to domination polynomial of a graph, Ars Combin., 114 (2014), 257–266.
6. J. L. Arocha, B. Llano, The number of dominating k-sets of paths, cycles and wheels, Available at https://arxiv.org/abs/1601.01268.
7. R. Boutrig, M. Chellali, A note on a relation between the weak and strong domination numbers of a graph, Opuscula Math., 32 (2012), 235–238.
8. N. Ghanbari, More on co-even domination number, Available at https://arxiv.org/abs/2111.11817.
9. N. Ghanbari, S. Alikhani, On the number of isolate dominating sets of certain graphs, Available at https://arxiv.org/abs/2101.04397.
10. T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, Marcel Dekker, NewYork, 1998 .
11. T. Kotek, J. Preen, F. Simon, P. Tittmann, M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, Elec. J. Combin. 19(3) (2012), 27 pp.
12. D. Rautenbach, Bounds on the strong domination number graphs, Discrete Math., 215 (2000), 201–212.
13. E. Sampathkumar, L. Pushpa Latha, Strong weak domination and domination balance in a graph, Discrete Math., 161(1) (1996), 235–242. 
Journal of Algebraic Systems
Volume 11, Issue 1
September 2023
Pages 65-76

Files

Share

How to cite

Statistics