Small Connected Planar Graph with 1-Cop-Move Number 4

2019/12/15 by Wei Quan Lim, Lim, Wei Quan
Computer Science · Mathematics · #05C57 (Primary) 91A43 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1912.07004

openalex publication_date 2019/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper describes a 720-vertex connected planar graph G such that cop1(G), denoting the minimum number of cops needed to catch the robber in the 1-cop-move game on G, is at least 4 and at most 7. Furthermore, G has a connected subgraph H such that cop1(H) is exactly 4, meaning that 4 cops are barely sufficient to catch the robber in the 1-cop-move game on H. This is a significant improvement over the graph given by Gao and Yang in 2017.

Citations

• Vertex-to-vertex pursuit in a graph
• The 3x3 rooks graph is the unique smallest graph with lazy cop number 3

Related

• The Cop Number of the One-Cop-Moves Game on Planar Graphs
• On 1-Planar Graphs with Bounded Cop-Number
• Cops and robbers on planar directed graphs
• Cops and Robbers on 1-Planar Graphs
• Cops and robber on subclasses of P₅-free graphs