论文标题
狮子和污染，三角形网格和脸颊常数
Lions and contamination, triangular grids, and Cheeger constants
论文作者
论文摘要
假设图的每个顶点最初是由污染占据的，除了狮子占据的那些顶点。当狮子在图上徘徊时，他们清除了他们访问的每个顶点的污染。但是，污染同时扩散到狮子未占据的任何相邻顶点。为了清除污染图，需要多少个狮子？我们在图表的cheeger常数方面给出了所需的狮子数量的下限。此外，Brass等人在方形网格图上详细研究了狮子和污染问题。和Berger等人，我们将此分析扩展到三角网格图的设置。
Suppose each vertex of a graph is originally occupied by contamination, except for those vertices occupied by lions. As the lions wander on the graph, they clear the contamination from each vertex they visit. However, the contamination simultaneously spreads to any adjacent vertex not occupied by a lion. How many lions are required in order to clear the graph of contamination? We give a lower bound on the number of lions needed in terms of the Cheeger constant of the graph. Furthermore, the lion and contamination problem has been studied in detail on square grid graphs by Brass et al. and Berger et al., and we extend this analysis to the setting of triangular grid graphs.
