Consider a graph whose vertices play the role of members of the opposing groups. The edge between two vertices means that these vertices may defend or attack each other. At one time, any attacker may attack only one vertex. Similarly, any defender fights for itself or helps exactly one of its neighbours. If we have a set of defenders that can repel any attack, then we say that the set is secure. Moreover, it is strong if it is also prepared for a raid of one additional foe who can strike anywhere. We show that almost any cubic graph of order n has a minimum strong secure set of cardinality less or equal to n/2 + 1. Moreover, we examine the possibility of an expansion of secure sets and strong secure sets.
@article{bwmeta1.element.doi-10_2478_s11533-014-0411-4,
author = {Katarzyna Jesse-J\'ozefczyk and El\.zbieta Sidorowicz},
title = {Secure sets and their expansion in cubic graphs},
journal = {Open Mathematics},
volume = {12},
year = {2014},
pages = {1664-1673},
zbl = {1297.05180},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-014-0411-4}
}
Katarzyna Jesse-Józefczyk; Elżbieta Sidorowicz. Secure sets and their expansion in cubic graphs. Open Mathematics, Tome 12 (2014) pp. 1664-1673. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-014-0411-4/
[1] Brigham R.C., Dutton R.D., Hedetniemi S.T., Security in graphs, Discrete Appl. Math., 2007, 155, 1708–1714. http://dx.doi.org/10.1016/j.dam.2007.03.009 | Zbl 1125.05071
[2] Brigham R.C., Dutton R.D., Haynes T.W., Hedetniemi S.T., Powerful alliances in graphs, Discrete Math., 2009, 309, 2140–2147. http://dx.doi.org/10.1016/j.disc.2006.10.026 | Zbl 1211.05101
[3] Brinkmann G., Goedgebeur J., McKay B., Generation of Cubic graphs, Discrete Math. Theor. Comput. Sci., North America, jul. 2011, 13. Available at: http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1801. | Zbl 1283.05256
[4] Brinkmann G., Goedgebeur J., Mélot H., Coolsaet K., House of Graphs: a database of interesting graphs, Discrete Appl. Math., 2013, 161, 311–314. Available at: http://hog.grinvin.org. http://dx.doi.org/10.1016/j.dam.2012.07.018 | Zbl 1292.05254
[5] Bussemaker F.C., Seidel J.J., Cubical graphs of order 2 ≤ 10, T.H. Eindhoven, 1968, Note No.10.
[6] Dutton R.D., On graph’s security number, Discrete Math., 2009, 309, 4443–4447. http://dx.doi.org/10.1016/j.disc.2009.02.005 | Zbl 1205.05166
[7] Dutton R.D., Lee R., Brigham R.C., Bounds on graph’s security number, Discrete Appl. Math., 2008, 156, 695–704. http://dx.doi.org/10.1016/j.dam.2007.08.037 | Zbl 1135.05048
[8] Dutton R., Ho Y.Y., Global secure sets of grid-like graphs, Discrete Appl. Math., 2011, 159, 490–496. http://dx.doi.org/10.1016/j.dam.2010.12.013 | Zbl 1209.05172
[9] Haynes T.W., Hedetniemi S.T., Henning M.A., Global defensive alliances in graphs, Electron. J. Combin., 2003, 10(1), R47. | Zbl 1031.05096
[10] Haynes T.W., Knisley D.J., Seier E., Zou Y., A quantitative analysis of secondary RNA structure using domination based parameters on trees, BMC Bioinformatics, 2006, 7:108. http://dx.doi.org/10.1186/1471-2105-7-108
[11] Kristiansen P., Hedetniemi S.M., Hedetniemi S.T., Alliances in graphs, J. Combin. Math. Combin. Comput., 2004, 48, 157–177. | Zbl 1051.05068
[12] Jesse-Józefczyk K., Bounds on global secure sets in cactus trees, Cent. Eur. J. Math., 2012, 10(3), 1113–1124. http://dx.doi.org/10.2478/s11533-012-0035-5 | Zbl 1239.05139
[13] Jesse-Józefczyk K., The possible cardinalities of global secure sets in cographs, Theor. Comput. Sci., 2012, 414(1), 38–46. http://dx.doi.org/10.1016/j.tcs.2011.10.004 | Zbl 1235.05106
[14] Jesse-Józefczyk K., Monotonicity and expansion of global secure sets, Discrete Math., 2012, 312, 3451–3456. http://dx.doi.org/10.1016/j.disc.2012.03.022 | Zbl 1250.05080
[15] Moshi A.M., Matching Cutsets in Graphs, J. Graph Theory, 1989, 13, 527–536. http://dx.doi.org/10.1002/jgt.3190130502 | Zbl 0725.05055
[16] Shafique K.H., Partitioning a Graph in Alliances and its Application to Data Clustering. Ph. D. Thesis, 2004.
[17] Sigarreta J.M., Rodríguez J.A., On the global offensive alliance number of a graph, Discrete Appl. Math., 2009, 157, 219–226. http://dx.doi.org/10.1016/j.dam.2008.02.007 | Zbl 1191.05072
[18] Srimani P.K., Xu Z., Distributed protocols for defensive and offensive alliances in network graphs using self-stabilization, Proceedings of the International Conference on Computing: Theory and Applications, 2007, 27–31.
[19] de Vries J., Over vlakke configuraties waarin elk punt met twee lijnen incident is. Verslagen en Mededeelingen der Koninklijke Akademie voor Wetenschappen, Afdeeling Natuurkunde, 1889, (3) 6, 382–407.
[20] de Vries J., Sur les configurations planes dont chaque point supporte deux droites. Rendiconti Circolo Mat. Palermo, 1891, 5, 221–226. http://dx.doi.org/10.1007/BF03015696 | Zbl 23.0560.01
[21] Yahiaoui S., Belhoul Y., Haddad M., Kheddouci H., Self-stabilizing algorithms for minimal global powerful alliance sets in graphs, Inf. Process. Lett., 2013, 113, 365–370. http://dx.doi.org/10.1016/j.ipl.2013.03.001 | Zbl 06329872