Cops that surround a robber

DOI10.1016/J.DAM.2020.06.019MaRDI QIDQ2197471zbMATH OpenOpenAlexFDO

Authors Rosalind A. Cameron, Nancy E. Clarke, Peter Danziger, Stephen Finbow, Caleb W. Jones, David A. Pike, Andrea Burgess

Publication date 31 August 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.14200

zbMATH Keywords

games on graphscops and robberspursuit-evasion on graphsgeneralised Petersen graphsproduct graphsgraphs arising from designs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph operations (line graphs, products, etc.) (05C76) Games involving graphs (91A43)

Abstract: We introduce the game of Surrounding Cops and Robbers on a graph, as a variant of the original game of Cops and Robbers. In contrast to the original game in which the cops win by occupying the same vertex as the robber, they now win by occupying each of the robber's neighbouring vertices. We denote by $sigma(G)$ the {em surrounding cop number} of $G$, namely the least number of cops required to surround a robber in the graph $G$. We present a number of results regarding this parameter, including general bounds as well as exact values for several classes of graphs. Particular classes of interest include product graphs, graphs arising from combinatorial designs, and generalised Petersen graphs.

Recommendations

• scientific article; zbMATH DE number 5241699
• Cops and robbers playing on edges
• A game of cops and robbers
• A game of cops and robbers played on products of graphs
• Ambush cops and robbers

Cites work

• scientific article; zbMATH DE number 4064802 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 3432294 (Why is no real title available?)
• A game of cops and robbers
• A game of cops and robbers played on products of graphs
• Containment game played on random graphs: another zig-zag theorem
• Containment: a variation of cops and robber
• Cops and robbers in graphs with large girth and Cayley graphs
• Cops and robbers is EXPTIME-complete
• Cops and robbers on graphs based on designs
• Cops and robbers playing on edges
• Graph minors. II. Algorithmic aspects of tree-width
• Meyniel's conjecture on the cop number: a survey
• On the cop number of a graph
• On the cop number of generalized Petersen graphs
• Pursuing a fast robber on a graph
• Pursuit and evasion from a distance: algorithms and bounds
• The CRC handbook of combinatorial designs
• The complexity of pursuit on a graph
• The cops and robber game on graphs with forbidden (induced) subgraphs
• The game of cops and robbers on graphs
• Vertex-to-vertex pursuit in a graph
• When does a random graph have constant cop number?

Cited in

(7)

• Cops and robber on butterflies, grids, and AT-free graphs
• Primal-dual cops and robber
• Most generalized Petersen graphs of girth 8 have cop number 4
• Cops and an insightful robber
• Ambush cops and robbers
• Time-delayed cops and robbers
• A game theoretical approach for finding near-optimal solutions of an optimization problem

This page was built for publication: Cops that surround a robber

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197471)