The Petersen graph is the smallest 3-cop-win graph
| Autor: | Beveridge, Andrew, Codenotti, Paolo, Maurer, Aaron, McCauley, John, Valeva, Silviya |
|---|---|
| Rok vydání: | 2011 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In the game of \emph{cops and robbers} on a graph $G = (V,E)$, $k$ cops try to catch a robber. On the cop turn, each cop may move to a neighboring vertex or remain in place. On the robber's turn, he moves similarly. The cops win if there is some time at which a cop is at the same vertex as the robber. Otherwise, the robber wins. The minimum number of cops required to catch the robber is called the \emph{cop number} of $G$, and is denoted $c(G)$. Let $m_k$ be the minimum order of a connected graph satisfying $c(G) \geq k$. Recently, Baird and Bonato determined via computer search that $m_3=10$ and that this value is attained uniquely by the Petersen graph. Herein, we give a self-contained mathematical proof of this result. Along the way, we give some characterizations of graphs with $c(G) >2$ and very high maximum degree. Comment: 14 pages, 3 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|