Isolation number of maximal outerplanar graphs. (English) Zbl 1420.05137
Summary: A subset \(S\) of vertices in a graph \(G\) is called an isolating set if \(V(G) \setminus N_G [S]\) is an independent set of \(G\). The isolation number \(\iota(G)\) is the minimum cardinality of an isolating set of \(G\). Let \(G\) be a maximal outerplanar graph of order \(n\) with \(n_2\) vertices of degree 2. It was previously proved that \(\iota(G) \leq \frac{n}{4}\). In this paper, we improve this bound to be \[\iota(G) \leq \begin{cases} \frac{n + n_2}{5} & \text{when}\;\; n_2 \leq \frac{n}{4}, \\ \frac{n - n_2}{3} & \text{otherwise}, \end{cases}\] and these bounds are best possible.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | Canales, S.; Castro, I.; Hernández, G.; Martins, M., Combinatorial bounds on connectivity for dominating sets in maximal outerplanar graphs, Electr. Notes Discrete Math., 54, 109-114 (2016) · Zbl 1356.05100 |
| [2] | Caro, Y.; Hansberg, A., Partial domination-the isolation number of a grapnh, FiloMath, 31, 12, 3925-3944 (2017) · Zbl 1488.05367 |
| [3] | Chvátal, V., A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B, 18, 39-41 (1975) · Zbl 0278.05028 |
| [4] | Dorfling, M.; Hattingh, J. H.; Jonck, E., Total domination in maximal outerplanar graphs II, Discrete Math., 339, 3, 1180-1188 (2016) · Zbl 1328.05140 |
| [5] | Dorfling, M.; Hattingh, J. H.; Jonck, E., Total domination in maximal outerplanar graphs, Discrete Appl. Math., 217, 3, 506-511 (2017) · Zbl 1358.05213 |
| [6] | Fisk, S., A short proof of Chvátal’s watchman theorem, J. Combin. Theory Ser. B, 24, 374 (1978) · Zbl 0376.05018 |
| [7] | M.A. Henning, P. Kaemawichanurat, Semipaired domination in maximal outerplanar graphs, J. Combin. Optim., Online First.; M.A. Henning, P. Kaemawichanurat, Semipaired domination in maximal outerplanar graphs, J. Combin. Optim., Online First. · Zbl 1395.05127 |
| [8] | Lemańska, M.; Zuazua, R.; Zylinski, P., Total dominating sets in maximal outerplanar graphs, Graphs Combin., 33, 991-998 (2017) · Zbl 1373.05144 |
| [9] | Matheson, L. R.; Tarjan, R. E., Dominating sets in planar graphs, European J. Combin., 17, 565-568 (1996) · Zbl 0862.05032 |
| [10] | O’Rourke, J., Art Gallery Theorems and Algorithms (1987), Oxford University Press: Oxford University Press New York · Zbl 0653.52001 |
| [11] | 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.
