On the semitotal dominating sets of graphs

Document Type : Research Paper

Authors

Department of Mathematical Sciences, Yazd University, Yazd, Iran

Abstract

A set $D$ of vertices in an isolate-free graph $G$ is a semitotal dominating set of $G$ if $D$ is a dominating set of $G$ and every vertex in $D$ is within distance $2$ from another vertex of $D$. The semitotal domination number of $G$ is the minimum cardinality of a semitotal dominating set of $G$ and is denoted by $\gamma_{t2}(G)$. In this paper after computation of semitotal domination number of specific graphs, we count the number of this kind of dominating sets of arbitrary size in some graphs.

Keywords

Main Subjects

References

1. S. Akbari, S. Alikhani and Y.H. Peng, Characterization of graphs using domination polynomial, Europ. J. Combin., 31 (2010), 1714-1724.
2. S. Alikhani, M.H. Akhbari, C. Eslahchi, R. Hasni, On the number of outer connected dominating sets of graphs, Utilitas Math. 91 (2013), 99-107.
3. S. Alikhani, S., Jahari and M. Mehryar, Counting the number of weakly connected dominating sets of graphs, Malaysian J. Math. Sci. (3) 10 (2016), 299-308.
4. S. Alikhani, J.I. Brown and S. Jahari, On the domination polynomials of friendship graphs, Filomat, (1) 30 (2016), 169-178.
5. S. Alikhani and Y.H. Peng, Introduction to domination polynomial of a graph, Ars Combin. 114 (2014), 257-266.
6. D. Bauer, F. Harary, J. Nieminen and C. Su el, Domination alternation sets in graphs, Discrete Math., 47 (1983), 153-161.
7. W. Goddard, M.A. Henning, and C.A. McPillan, Semitotal domination in graphs, Util. Math. 94 (2014), 67-81.
8. T. W. Haynes, S.T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, Marcel Dekker, NewYork, 1998 .
9. M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, New York, 2013.
10. M.A. Henning and A.J. Marcon, On matching and semitotal domination in graphs, Discrete Math. 324 (2014), 13-18.
11. M.A. Henning and A.J. Marcon, Vertices contained in all or in no minimum semitotal dominating set of a tree, Discuss. Math. Graph Theory, 36 (2016), 71-93.
12. M.A. Henning, S. Pal and D. Pradhan, The semitotal domination problem in block graphs, Discuss. Math. Graph Theory, 42 (2022) 231-248.
Journal of Algebra and Related Topics
Volume 12, Issue 2
January 2025
Pages 37-46

Files

Share

How to cite

Statistics