$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

Articles in Press, Accepted Manuscript
Available Online from 06 November 2023

Files

Share

How to cite

Statistics