Secure sets and their expansion in cubic graphs

Katarzyna Jesse-Józefczyk; Elżbieta Sidorowicz

Open Mathematics (2014)

  • Volume: 12, Issue: 11, page 1664-1673
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Katarzyna Jesse-Józefczyk, and Elżbieta Sidorowicz. "Secure sets and their expansion in cubic graphs." Open Mathematics 12.11 (2014): 1664-1673. <http://eudml.org/doc/269563>.

@article{KatarzynaJesse2014,
abstract = {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.},
author = {Katarzyna Jesse-Józefczyk, Elżbieta Sidorowicz},
journal = {Open Mathematics},
keywords = {Secure set; Expansion; Cubic graphs; secure set; expansion; cubic graphs},
language = {eng},
number = {11},
pages = {1664-1673},
title = {Secure sets and their expansion in cubic graphs},
url = {http://eudml.org/doc/269563},
volume = {12},
year = {2014},
}

TY - JOUR
AU - Katarzyna Jesse-Józefczyk
AU - Elżbieta Sidorowicz
TI - Secure sets and their expansion in cubic graphs
JO - Open Mathematics
PY - 2014
VL - 12
IS - 11
SP - 1664
EP - 1673
AB - 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.
LA - eng
KW - Secure set; Expansion; Cubic graphs; secure set; expansion; cubic graphs
UR - http://eudml.org/doc/269563
ER -

References

top
  1. [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 Zbl1125.05071
  2. [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 Zbl1211.05101
  3. [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. Zbl1283.05256
  4. [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 Zbl1292.05254
  5. [5] Bussemaker F.C., Seidel J.J., Cubical graphs of order 2 ≤ 10, T.H. Eindhoven, 1968, Note No.10. 
  6. [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 Zbl1205.05166
  7. [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 Zbl1135.05048
  8. [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 Zbl1209.05172
  9. [9] Haynes T.W., Hedetniemi S.T., Henning M.A., Global defensive alliances in graphs, Electron. J. Combin., 2003, 10(1), R47. Zbl1031.05096
  10. [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. [11] Kristiansen P., Hedetniemi S.M., Hedetniemi S.T., Alliances in graphs, J. Combin. Math. Combin. Comput., 2004, 48, 157–177. Zbl1051.05068
  12. [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 Zbl1239.05139
  13. [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 Zbl1235.05106
  14. [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 Zbl1250.05080
  15. [15] Moshi A.M., Matching Cutsets in Graphs, J. Graph Theory, 1989, 13, 527–536. http://dx.doi.org/10.1002/jgt.3190130502 Zbl0725.05055
  16. [16] Shafique K.H., Partitioning a Graph in Alliances and its Application to Data Clustering. Ph. D. Thesis, 2004. 
  17. [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 Zbl1191.05072
  18. [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. [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. [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 Zbl23.0560.01
  21. [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 Zbl06329872

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.