2024/08/05 by Alexander Clow, Clow, Alexander, Melissa A. Huggan +3
Social Sciences · #05C57 #05C75 #Combinatorics (math.CO) #Crime, Illicit Activities, and Governance #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2408.02225
openalex publication_date 2024/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper considers the Cops and Attacking Robbers game, a variant of Cops and Robbers, where the robber is empowered to attack a cop in the same way a cop can capture the robber. In a graph G, the number of cops required to capture a robber in the Cops and Attacking Robbers game is denoted by \attCop(G). We characterise the triangle-free graphs G with \attCop(G) ≤ 2 via a natural generalisation of the cop-win characterisation by Nowakowski and Winkler \citenowakowski1983vertex. We also prove that all bipartite planar graphs G have \attCop(G) ≤ 4 and show this is tight by constructing a bipartite planar graph G with \attCop(G) = 4. Finally we construct 17 non-isomorphic graphs H of order 58 with \attCop(H) = 6 and \cop(H)=3. This provides the first example of a graph H with \attCop(H) - \cop(H) ≥ 3 extending work by Bonato, Finbow, Gordinowicz, Haidar, Kinnersley, Mitsche, Prałat, and Stacho \citebonato2014robber. We conclude with a list of conjectures and open problems.