On the secure domination numbers of maximal outerplanar graphs. (English) Zbl 1377.05135
Summary: A subset \(S\) of vertices in a graph \(G\) is a secure dominating set of \(G\) if \(S\) is a dominating set of \(G\) and, for each vertex \(u / \in S\), there is a vertex \(v \in S\) such that \(u v\) is an edge and \((S \setminus \{v \}) \cup \{u \}\) is also a dominating set of \(G\). We show that if \(G\) is a maximal outerplane graph of \(n\) vertices, then \(G\) has a secure dominating set of size at most \(\lceil 3 n / 7 \rceil\). Moreover, if a maximal outerplane graph \(G\) has no internal triangles, it has a secure dominating set of size at most \(\lceil n / 3 \rceil\). Finally, we show that any secure dominating set of a maximal outerplane graph without internal triangles has more than \(n / 4\) vertices.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Burger, A. P.; de Villiers, A. P.; van Vuuren, J. H., Two algorithms for secure graph domination, J. Combin. Math. Combin. Comput., 85, 321-339 (2013) · Zbl 1274.05349 |
| [2] | Burger, A. P.; de Villiers, A. P.; van Vuuren, J. H., A linear algorithm for secure domination in trees, Discrete Appl. Math., 171, 10, 15-47 (2014) · Zbl 1288.05189 |
| [3] | Burger, A. P.; de Villiers, A. P.; van Vuuren, J. H., On minimum secure dominating sets of graphs, Quaest. Math., 39, 2, 189-202 (2016) · Zbl 1419.05164 |
| [4] | Burger, A. P.; Henning, M. A.; van Vuuren, J. H., Vertex covers and secure domination in graphs, Quaest. Math., 31, 2, 163-171 (2008) · Zbl 1154.05048 |
| [5] | Campos, C. N.; Wakabayashi, Y., On dominating sets of maximal outerplanar graphs, Discrete Appl. Math., 161, 330-335 (2013) · Zbl 1254.05136 |
| [6] | Castillano, E. C.; Ugbinada, R. A.L., Secure domination in the joins of graphs, Appl. Math. Sci., 8, 105, 5203-5211 (2014) |
| [7] | Cockayne, E. J.; Grobler, P. J.P.; Gründlingh, W. R.; Munganga, J.; van Vuuren, J. H., Protection of a graph, Util. Math., 67, 19-32 (2008) · Zbl 1081.05083 |
| [8] | Dorfling, M.; Hattingh, J. H.; Jonck, E., Total domination in maximal outerplanar graphs II, Discrete Math., 339, 1180-1188 (2016) · Zbl 1328.05140 |
| [9] | Dorfling, M.; Hattingh, J. H.; Jonck, E., Total domination in maximal outerplanar graphs, Discrete App. Math., 217, 506-511 (2017) · Zbl 1358.05213 |
| [10] | Grobler, P. J.P.; Mynhardt, C. M., Secure domination critical graphs, Discrete Math., 19, 6, 5820-5827 (2009) · Zbl 1189.05126 |
| [11] | Hopcroft, J. E.; Tarjan, R. E., Dividing a graph into triconnected components, SIAM J. Comput., 2, 135-158 (1973) · Zbl 0281.05111 |
| [12] | Klostermeyer, W. F.; Mynhardt, C. M., Secure domination and secure total domination in graphs, Discuss. Math. Graph Theory, 28, 267-284 (2008) · Zbl 1156.05043 |
| [13] | Li, Z.; Shao, Z.; Xu, J., On secure domination in trees, Quaest. Math., 40, 1, 1-12 (2017) · Zbl 1423.05125 |
| [14] | Li, Z.; Zhu, E.; Shao, Z.; Xu, J., On dominating sets of maximal outerplanar and planar graphs, Discrete Appl. Math., 198, 164-169 (2016) · Zbl 1327.05263 |
| [15] | Merouane, H. B.; Chellali, M., On secure domination in graphs, Inform. Process. Lett., 115, 786-790 (2015) · Zbl 1329.05223 |
| [16] | Pushpam, P. R.L.; Suseendran, C., Secure restrained domination in graphs, Math. Comput. Sci., 9, 2, 239-247 (2015) · Zbl 1317.05141 |
| [17] | Rashmi, S. D.; Arumugam, S.; Bhutani, K. R.; Gartland, P., Perfect secure domination in graphs, Categ. Gen. Algebr. Struct. Appl., 6, 1-16 (2017), URL http://www.cgasa.ir/article_44926.html |
| [18] | Tokunaga, S., Dominating sets of maximal outerplanar graphs, Discrete Appl. Math., 161, 3097-3099 (2013) · Zbl 1287.05109 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
