Secure Domination Number in Kneser Graph

Document Type : Original Scientific Paper

Authors

1 ‎Department of Mathematics, ‎University of Zanjan, ‎Zanjan‎, ‎I‎. ‎R‎. ‎Iran

2 ‎Department of Mathematical Sciences, ‎Yazd University, 89195-741‎, ‎Yazd‎, ‎I‎. ‎R‎. ‎Iran

10.22052/mir.2026.258107.1562

Abstract

‎A vertex subset $S \subseteq V(G)$ is defined as a secure dominating set if‎, ‎for any vertex u outside of S‎, ‎there is a neighbor $v \in S$ such that the set $(S \setminus \{v\}) \cup \{u\}$ remains a dominating set for the graph $G$‎. ‎The minimum cardinality of such a set is termed the secure domination number and is denoted by $\gamma_s(G)$‎. ‎In the present study‎, ‎we establish specific bounds for the secure domination number of Kneser graphs K(n‎, ‎k)‎. ‎We further prove that for the condition $n \ge k^2‎ + ‎2k$‎, ‎the value of $\gamma_s(K(n‎, ‎k))$ is precisely k‎ + ‎2‎.

Keywords

Main Subjects

References

[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press, New York, 1976.
[2] A. Bahmani, M. Emami and O. Naserain, Dominating sets for uniform subset graphs, Linear Multilinear Algebra 72 (2024) 283-295, https://doi.org/10.1080/03081087.2022.2158295.
[3] E. J. Cockayne, P. J. P. Grobler, W. R. Gründlingh, J. Munganga and J. H. van Vuuren, Protection of a graph, Util. Math. 67 (2005) 19-32.
[4] E. J. Cockayne, Irredundance, secure domination and maximum degree in trees, Discrete Math. 307 (2007) 12-17, https://doi.org/10.1016/j.disc.2006.05.037.
[5] W. F. Klostermeyer and C. M. Mynhardt, Secure domination and secure total domination in graphs, Discuss. Math. Graph Theory 28 (2008) 267-284, https://doi.org/10.7151/dmgt.1405.
[6] A. P. Burger, A. P. de Villiers and J. H. van Vuuren, On minimum secure dominating sets of graphs, Quaest. Math. 39 (2016) 189-202, https://doi.org/10.2989/16073606.2015.1068238.
[7] H. B. Merouane and M. Chellali, On secure domination in graphs, Inf. Process. Lett. 115 (2015) 786-790, https://doi.org/10.1016/j.ipl.2015.05.006.
[8] I. Anderson, Combinatorial Designs and Tournaments, The Clarendon Press, Oxford University Press, New York, 1997.
[9] I. Gorodezky, Dominating sets in Kneser graphs, Master’s Thesis, University of Waterloo, 2007, http://uwspace.uwaterloo.ca/bitstream/10012/3190/1/thes
[10] J. Ivanco and B. Zelinka, Domination in Kneser graphs, Math. Bohem. 118 (1993) 147-152.
[11] P. R. J. Östergård, Z. Shao and X. Xu, Bounds on the domination number of Kneser graphs, Ars Math. Contemp. 9 (2015) 187-195.
[12] A. Bahmani and M. Emami, Total roman domination on Kneser graphs, Trans. Comb. 15 (2026) 69-76, https://doi.org/10.22108/TOC.2025.140647.2148.
Mathematics Interdisciplinary Research
Volume 11, Issue 3
In progress
September 2026
Pages 243-251

Files

Share

How to cite

Statistics