Extensions of the Art Gallery Theorem

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]G−N[S], the graph obtained by deleting the closed neighborhood of S, contains no vertices. In the proof of the Art Gallery Theorem, Chvátal showed that the minimum size, called the domination number of G and denoted by γ(G)γ(G), is at most n/3 if G is a mop. Here we consider a modification by allowing G−N[S]G−N[S] to have a maximum degree of at most k. Let ιk(G)ιk(G) denote the size of a smallest set S for which this is achieved. If n≤2k+3n≤2k+3, then trivially ιk(G)≤1ιk(G)≤1. Let G be a mop on n≥max{5,2k+3}n≥max{5,2k+3} vertices, n2n2 of which are of degree 2. Upper bounds on ιk(G)ιk(G) have been obtained for k=0k=0 and k=1k=1, namely ι0(G)≤min{n4,n+n25,n−n23}ι0(G)≤min{n4,n+n25,n−n23} and ι1(G)≤min{n5,n+n26,n−n23}ι1(G)≤min{n5,n+n26,n−n23}. We prove that ιk(G)≤min{nk+4,n+n2k+5,n−n2k+2}ιk(G)≤min{nk+4,n+n2k+5,n−n2k+2} for any k≥0k≥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+2k+2 consecutive corners must be visible to at least one guard, then the number of guards needed is at most n/(k+4)n/(k+4). We also prove that γ(G)≤n−n22γ(G)≤n−n22 unless n=2n2n=2n2, n2n2 is odd, and γ(G)=n−n2+12γ(G)=n−n2+12. Together with the inequality γ(G)≤n+n24γ(G)≤n+n24, obtained by Campos and Wakabayashi and independently by Tokunaga, this improves Chvátal’s bound. The bounds are sharp.