Cop numbers of periodic graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913566556160000 |
|---|---|
| author | De Carufel, Jean-Lou Flocchini, Paola Santoro, Nicola Simard, Frédéric |
| author_facet | De Carufel, Jean-Lou Flocchini, Paola Santoro, Nicola Simard, Frédéric |
| contents | A \emph{periodic graph} ${\cal 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 ${\cal 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({\cal G})$ of a periodic graph ${\cal 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({\cal 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 ${\cal 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_13616 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cop numbers of periodic graphs De Carufel, Jean-Lou Flocchini, Paola Santoro, Nicola Simard, Frédéric Combinatorics Discrete Mathematics A \emph{periodic graph} ${\cal 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 ${\cal 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({\cal G})$ of a periodic graph ${\cal 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({\cal 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 ${\cal 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. |
| title | Cop numbers of periodic graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2310.13616 |