Cops and robbers on oriented toroidal grids

DOI10.1016/J.TCS.2021.01.012MaRDI QIDQ2220788zbMATH OpenOpenAlexFDO

Authors Sebastián González Hermosillo de la Maza, Seyyed Aliasghar Hosseini, Fiachra Knox, Bojan Mohar, Bruce Reed

Publication date 25 January 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

cop numbercops and robberdirected graphstoroidal grid

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) 2-person games (91A05) Games involving graphs (91A43)

Abstract: The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13.

Recommendations

• Cops and robbers on toroidal chess graphs
• Game of cops and robbers in oriented quotients of the integer grid
• Variations of cops and robbers game on grids
• Cops and robbers on oriented graphs
• A game of cops and robbers

Cites work

• Game of cops and robbers in oriented quotients of the integer grid
• Geometry of surfaces
• The game of cops and robbers on graphs
• Vertex-to-vertex pursuit in a graph

Cited in

(10)

• Game of cops and robbers in oriented quotients of the integer grid
• On the cop number of toroidal graphs
• Cops and robbers on directed and undirected abelian Cayley graphs
• Cops and robbers on toroidal chess graphs
• Cops and robber on some families of oriented graphs
• A cops and robber game in multidimensional grids
• Cops and robber on oriented graphs with respect to push operation
• Pushing cops and robber on graphs of maximum degree four
• On the cop number and the weak Meyniel conjecture for algebraic graphs
• Catching a robber on a random k-uniform hypergraph

This page was built for publication: Cops and robbers on oriented toroidal grids

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