×

Extensions of the Art Gallery Theorem. (English) Zbl 1511.05176

Summary: Several domination results have been obtained for maximal outerplanar graphs (mops). The classical domination problem is to minimize the size of a set \(S\) of vertices of an \(n\)-vertex graph \(G\) such that \(G - N[S]\), the graph obtained by deleting the closed neighborhood of \(S\), contains no vertices. In the proof of the Art Gallery Theorem, V. Chvátal [J. Comb. Theory, Ser. B 18, 39–41 (1975; Zbl 0278.05028)] showed that the minimum size, called the domination number of \(G\) and denoted by \(\gamma (G)\), is at most \(n/3\) if \(G\) is a mop. Here we consider a modification by allowing \(G - N[S]\) to have a maximum degree of at most \(k\). Let \(\iota_k (G)\) denote the size of a smallest set \(S\) for which this is achieved. If \(n \leq 2k+3\), then trivially \(\iota_k (G) \leq 1\). Let \(G\) be a mop on \(n \geq \max \{ 5,2k+3\}\) vertices, \(n_2\) of which are of degree 2. Upper bounds on \(\iota_k (G)\) have been obtained for \(k = 0\) and \(k = 1\), namely \(\iota_0 (G) \leq \min \{\frac{n}{4},\frac{n+n_2}{5},\frac{n-n_2}{3}\}\) and \(\iota_1 (G) \leq \min \{\frac{n}{5},\frac{n+n_2}{6},\frac{n-n_2}{3}\}\). We prove that \(\iota_k (G) \leq \min \{\frac{n}{k+4},\frac{n+n_2}{k+5},\frac{n-n_2}{k+2}\}\) for any \(k \geq 0\). For the original setting of the Art Gallery Theorem, the argument presented yields that if an art gallery has exactly \(n\) corners and at least one of every \(k + 2\) consecutive corners must be visible to at least one guard, then the number of guards needed is at most \(n/(k+4)\). We also prove that \(\gamma (G) \leq \frac{n-n_2}{2}\) unless \(n = 2n_2\), \(n_2\) is odd, and \(\gamma (G) = \frac{n-n_2 + 1}{2}\). Together with the inequality \(\gamma (G) \leq \frac{n+n_2}{4}\), obtained by C. N. Campos and Y. Wakabayashi [Discrete Appl. Math. 161, No. 3, 330–335 (2013; Zbl 1254.05136)] and independently by S.-i. Tokunaga [ibid. 161, No. 18, 3097–3099 (2013; Zbl 1287.05109)], this improves Chvátal’s bound. The bounds are sharp.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C07 Vertex degrees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory

References:

[1] Aigner, M.; Ziegler, G., Proofs from THE BOOK (2018), Berlin/Heidelberg: Springer, Berlin/Heidelberg · Zbl 1392.00001 · doi:10.1007/978-3-662-57265-8
[2] P. Borg. Isolation of connected graphs, arXiv:2110.03773 [math.CO].
[3] Borg, P., Isolation of cycles, Graphs Combin., 36, 631-637 (2020) · Zbl 1439.05117 · doi:10.1007/s00373-020-02143-2
[4] P. Borg, K. Fenech and P. Kaemawichanurat, Isolation of \(k\)-cliques, Discrete Math.343 (2020), paper 111879. · Zbl 1440.05157
[5] P. Borg, K. Fenech and P. Kaemawichanurat, Isolation of \(k\)-cliques II, Discrete Math.345 (2022), paper 112641. · Zbl 1489.05109
[6] Borg, P.; Kaemawichanurat, P., Partial domination of maximal outerplanar graphs, Discrete Appl. Math., 283, 306-314 (2020) · Zbl 1442.05149 · doi:10.1016/j.dam.2020.01.005
[7] Caro, Y.; Hansberg, A., Partial domination - the isolation number of a graph, FiloMath, 31, 12, 3925-3944 (2017) · Zbl 1488.05367 · doi:10.2298/FIL1712925C
[8] Campos, CN; Wakabayashi, Y., On dominating sets of maximal outerplanar graphs, Discrete Appl. Math., 161, 330-335 (2013) · Zbl 1254.05136 · doi:10.1016/j.dam.2012.08.023
[9] Canales, S.; Castro, I.; Hernández, G.; Martins, M., Combinatorial bounds on connectivity for dominating sets in maximal outerplanar graphs, Electron. Notes, Discrete Math., 54, 109-114 (2016) · Zbl 1356.05100
[10] Chvátal, V., A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B, 18, 39-41 (1975) · Zbl 0278.05028 · doi:10.1016/0095-8956(75)90061-1
[11] E.J. Cockayne, Domination of undirected graphs - A survey, Lecture Notes in Mathematics, Volume 642, Springer, 1978, 141-147. · Zbl 0384.05052
[12] Cockayne, EJ; Hedetniemi, ST, Towards a theory of domination in graphs, Networks, 7, 247-261 (1977) · Zbl 0384.05051 · doi:10.1002/net.3230070305
[13] Dorfling, M.; Hattingh, JH; Jonck, E., Total domination in maximal outerplanar graphs II, Discrete Math., 339, 1180-1188 (2016) · Zbl 1328.05140 · doi:10.1016/j.disc.2015.11.003
[14] Dorfling, M.; Hattingh, JH; Jonck, E., Total domination in maximal outerplanar graphs, Discrete Appl. Math., 217, 506-511 (2017) · Zbl 1358.05213 · doi:10.1016/j.dam.2016.10.020
[15] Favaron, O.; Kaemawichanurat, P., Inequalities between the \(K_k\)-isolation number and the independent \(K_k\)-isolation number of a graph, Discrete Appl. Math., 289, 93-97 (2021) · Zbl 1454.05084 · doi:10.1016/j.dam.2020.09.011
[16] Fisk, S., A short proof of Chvátal’s watchman theorem, J. Combin. Theory Ser. B, 24, 374 (1978) · Zbl 0376.05018 · doi:10.1016/0095-8956(78)90059-X
[17] Haynes, TW; Hedetniemi, ST; Slater, PJ, Fundamentals of Domination in Graphs (1998), New York: Marcel Dekker Inc, New York · Zbl 0890.05002
[18] Haynes, TW; Hedetniemi, ST; Slater, PJ, Domination in Graphs: Advanced Topics (1998), New York: Marcel Dekker Inc, New York · Zbl 0883.00011
[19] S.T. Hedetniemi and R.C. Laskar (Editors), Topics on Domination, Discrete Math.86 (1990). · Zbl 0728.05056
[20] Hedetniemi, ST; Laskar, RC, Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math., 86, 257-277 (1990) · Zbl 0733.05076 · doi:10.1016/0012-365X(90)90365-O
[21] Henning, MA; Kaemawichanurat, P., Semipaired domination in maximal outerplanar graphs, J. Comb. Optim., 38, 911-926 (2019) · Zbl 1435.05155 · doi:10.1007/s10878-019-00427-9
[22] Lemańska, M.; Zuazua, R.; Zylinski, P., Total dominating sets in maximal outerplanar graphs, Graphs Combin., 33, 991-998 (2017) · Zbl 1373.05144 · doi:10.1007/s00373-017-1802-7
[23] Matheson, LR; Tarjan, RE, Dominating sets in planar graphs, European J. Combin., 17, 565-568 (1996) · Zbl 0862.05032 · doi:10.1006/eujc.1996.0048
[24] O’Rourke, J., Galleries need fewer mobile guards: a variation to Chvátal’s theorem, Geom. Dedicata, 14, 273-283 (1983) · Zbl 0516.05018
[25] O’Rourke, J., Art gallery theorems and algorithms (1987), New York: Oxford University Press, New York · Zbl 0653.52001
[26] Tokunaga, S., Dominating sets of maximal outerplanar graphs, Discrete Appl. Math., 161, 3097-3099 (2013) · Zbl 1287.05109 · doi:10.1016/j.dam.2013.06.025
[27] Tokunaga, S.; Jiarasuksakun, T.; Kaemawichanurat, P., Isolation number of maximal outerplanar graphs, Discrete Appl. Math., 267, 215-218 (2019) · Zbl 1420.05137 · doi:10.1016/j.dam.2019.06.011
[28] Yan, J., Isolation of the diamond graph, Bull. Malays. Math. Sci. Soc., 45, 1169-1181 (2022) · Zbl 1487.05201 · doi:10.1007/s40840-022-01248-6
[29] H. Yu and B. Wu, Admissible property of graphs in terms of radius, Graphs Combin.38 (2022), paper 6. · Zbl 1479.05290
[30] Zhang, G.; Wu, B., \(K_{1,2}\)-isolation in graphs, Discrete Appl. Math., 304, 365-374 (2021) · Zbl 1473.05235 · doi:10.1016/j.dam.2021.08.013
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.