COP Numbers of Periodic Graphs
摘要
A periodic graph \(\mathcal {G}=(G_0, G_1, G_2, \dots )\) with period p is an infinite periodic sequence of graphs \(G_i = G_{i + p} = (V,E_i)\) , where \(i \geq 0\) . The graph \(G=(V,\cup _i E_i)\) is called the footprint of \(\mathcal {G}\) . Recently, the arena where the Cops and Robber game is played has been extended from a graph to a periodic graph; in this case, the cop number is also the minimum number of cops sufficient for capturing the robber. We study the connections and distinctions between the cop number \(c(\mathcal {G})\) of a periodic graph \(\mathcal {G}\) and the cop number \(c(G)\) of its footprint G and establish several facts. For instance, we show that the smallest periodic graph with \(c(\mathcal {G}) = 3\) has at most 8 nodes; in contrast, the smallest graph G with \(c(G) = 3\) has 10 nodes. We push this investigation by generating multiple examples showing how the cop numbers of a periodic graph \(\mathcal {G}\) , the subgraphs \(G_i\) and its footprint G can be loosely tied. Based on these results, we derive upper bounds on the cop number of a periodic graph from properties of its footprint such as its treewidth.