论文标题
艺术画廊定理的扩展
Extensions of the Art Gallery Theorem
论文作者
论文摘要
最大外平图（MOP）获得了几个统治结果。经典的统治问题是最大程度地减少$ n $ -vertex图$ g $的一组$ s $顶点的大小，以使$ g -n [s] $，通过删除$ s $的封闭社区获得的图所获得的图，不包含顶点。在Art Gallery定理的证明中，Chvátal表明，如果$ g $是拖把，则最小尺寸，称为$ g $的统治数，用$γ（g）$表示，最多是$ n/3 $。在这里，我们考虑通过允许$ g -n [s] $的最高度为$ k $来修改。令$ 〜k（g）$表示为实现这一目标的最小套装$ s $的大小。如果$ n \ le 2k+3 $，则琐碎的$ 〜K（g）\ leq 1 $。令$ g $为$ n \ ge \ ge \ max \ {5,2k+3 \} $ vertices，$ n_2 $的拖把，其中$ n_2 $是$ 2 $。 $ k = 0 $和$ k = 1 $，即$ k = 1 $，即$〜$ i_ {0}（G） $ 〜1（g）\ le \ min \ {\ frac {n} {5}，\ frac {n+n_2} {6} {6}，\ frac {n-n_2} {3} {3} \} $。我们证明$〜{k}（g）\ le \ min \ {\ frac {n} {k+4}，\ frac {n+n_2} {k+5}，\ frac {n-n-n_2} {k+2} {k+2}} $ for nothoy $ k \ ge 0 $ 0 $。对于艺术画廊定理的原始设置，提出的争论表明，如果美术馆完全具有$ n $ corner，并且至少连续至少有一个$ k + 2 $的角落中的至少有一个，那么至少一个警卫必须可见，那么所需的警卫人数最多是$ n/（k + 4）$。我们还证明$γ（g）\ le \ frac {n -n_2} {2} $，除非$ n = 2n_2 $，$ n_2 $是奇数的，而$γ（g）= \ frac {n -n_2 + 1} {2} {2} {2} $。连同不平等$γ（g）\ le \ frac {n+n_2} {4} $，由Campos和Wakabayashi获得，由Tokunaga独立地获得，这改善了Chvátal的界限。边界很锋利。
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, Chvátal showed that the minimum size, called the domination number of $G$ and denoted by $γ(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 $ι_k(G)$ denote the size of a smallest set $S$ for which this is achieved. If $n \le 2k+3$, then trivially $ι_k(G) \leq 1$. Let $G$ be a mop on $n \ge \max\{5,2k+3\}$ vertices, $n_2$ of which are of degree $2$. Upper bounds on $ι_k(G)$ have been obtained for $k = 0$ and $k = 1$, namely $ι_{0}(G) \le \min\{\frac{n}{4},\frac{n+n_2}{5},\frac{n-n_2}{3}\}$ and $ι_1(G) \le \min\{\frac{n}{5},\frac{n+n_2}{6},\frac{n-n_2}{3}\}$. We prove that $ι_{k}(G) \le \min\{\frac{n}{k+4},\frac{n+n_2}{k+5},\frac{n-n_2}{k+2}\}$ for any $k \ge 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 $γ(G) \le \frac{n - n_2}{2}$ unless $n = 2n_2$, $n_2$ is odd, and $γ(G) = \frac{n - n_2 + 1}{2}$. Together with the inequality $γ(G) \le \frac{n+n_2}{4}$, obtained by Campos and Wakabayashi and independently by Tokunaga, this improves Chvátal's bound. The bounds are sharp.
