Cop numbers of periodic graphs

Abstract

A \emph{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\ge 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 \emph{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.

Submitted to the proceedings of the 54th Southeastern International Conference on Combinatorics, Graph Theory & Computing