$k$-secure sets and $k$-security number of a graph

Document Type : Original paper

Authors

Department of Mathematics, Mangalore University, Mangalagangothri, Mangalore, India

Abstract

Let $G=(V, E)$ be a simple connected graph. A nonempty set $S\subseteq V$ is a secure set if every attack on $S$ is defendable. In this paper, $k$-secure sets are introduced as a generalization of secure sets. For any integer $k\geq 0$, a nonempty subset $S$ of $V$ is a $k$-secure set if, for each attack on $S$, there is a defense of $S$ such that for every $v\in S$, the defending set of $v$ contains at least $k$ more elements than that of the attacking set of $v$, whenever the vertex $v$ has neighbors outside $S$. The cardinality of a minimum $k$-secure set in $G$ is the $k$-security number of $G$. Some properties of $k$-secure sets are discussed and a characterization of $k$-secure sets is obtained. Also, 1-security numbers of certain classes of graphs are determined.

Keywords

Main Subjects

References

[1] R.C. Brigham, R.D. Dutton, and S.T. Hedetniemi, Security in graphs, Discrete Appl. Math. 155 (2007), no. 13, 1708–1714. https://doi.org/10.1016/j.dam.2007.03.009
[2] G. Chartrand, L. Lesniak, and P. Zhang, Graphs & Digraphs, vol. 39, CRC press, 2010.
[3] R.D. Dutton, On a graph’s security number, Discrete Math. 309 (2009), no. 13, 4443–4447. https://doi.org/10.1016/j.disc.2009.02.005
[4] R.D. Dutton, R. Lee, and R.C. Brigham, Bounds on a graph’s security number, Discrete Appl. Math. 156 (2008), no. 5, 695–704.  https://doi.org/10.1016/j.dam.2007.08.037
[5] H. Fernau, J.A. RodrÍguez, and J.M. Sigarreta, Offensive $r$-alliances in graphs, Discrete Appl. Math. 157 (2009), no. 1, 177–182.  https://doi.org/10.1016/j.dam.2008.06.001
[6] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 26–30.
[7] P.R. Halmos and H.E. Vaughan, The marriage problem, Amer. J. Math. 72 (1950), 214–215.
[8] C. Hegde and B. Sooryanarayana, Strong alliances in graphs, Commun. Comb. Optim. 4 (2019), no. 1, 1–13. https://doi.org/10.22049/cco.2018.25921.1056
[9] C. Hegde, B. Sooryanarayana, and S. Sequeira, On the upper security number of a graph, Commun. Optim. Theory 2020 (2020), Article ID: 12.  http://doi.org/10.23952/cot.2020.12
[10] G. Isaak, P. Johnson, and C. Petrie, Integer and fractional security in graphs, Discrete Appl. Math. 160 (2012), no. 13-14, 2060–2062.  https://doi.org/10.1016/j.dam.2012.04.018
[11] K. Karthik, C. Hegde, and B. Sooryanarayana, $k$-distance secure sets in graphs, Mater. Today Proc. (2023), https://doi.org/10.1016/j.matpr.2023.05.382
[12] P. Kristiansen, S.M. Hedetniemi, and S.T. Hedetniemi, Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177.
[13] C. Petrie, Security, $(f, i)$-security, and ultra-security in graphs, Ph.D. thesis, Auburn University, 2012.
[14] R. Rado, A theorem on general measure functions, Proc. London Math. Soc. s2-44 (1938), no. 1, 61–91. https://doi.org/10.1112/plms/s2-44.1.61
[15] J.A. RodrÍguez-Velázquez, I.G. Yero, and J.M. Sigarreta, Defensive $k$-alliances in graphs, Applied Math. Lett. 22 (2009), no. 1, 96–100.  https://doi.org/10.1016/j.aml.2008.02.012
[16] K.H. Shafique and R.D. Dutton, Maximum alliance-free and minimum alliance-cover sets, Congr. Numer. 162 (2003), 139–146.
[17] D.B. West, Introduction to Graph Theory, vol. 2, Prentice hall, Upper Saddle River, 2001.
Communications in Combinatorics and Optimization
Volume 10, Issue 2
June 2025
Pages 245-255

Files

Share

How to cite

Statistics