Secure sets and their expansion in cubic graphs

• Autorzy: Katarzyna Jesse-Józefczyk , Elżbieta Sidorowicz
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Secure set; Expansion; Cubic graphs

Kategorie tematyczne

• 05C99: None of the above, but in this section

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2014
• Tom: 12
• Numer: 11
• Strony: 1664-1673

Daty

wydano

2014-11-01

online

2014-06-29

Twórcy

autor

Katarzyna Jesse-Józefczyk

• University of Zielona Góra

autor

Elżbieta Sidorowicz

• University of Zielona Góra

Bibliografia

• [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
• [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
• [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.
• [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
• [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
• [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
• [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
• [9] Haynes T.W., Hedetniemi S.T., Henning M.A., Global defensive alliances in graphs, Electron. J. Combin., 2003, 10(1), R47.
• [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.
• [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
• [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
• [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
• [15] Moshi A.M., Matching Cutsets in Graphs, J. Graph Theory, 1989, 13, 527–536. http://dx.doi.org/10.1002/jgt.3190130502
• [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
• [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
• [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

Identyfikatory

DOI

10.2478/s11533-014-0411-4