TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS

DOI10.17654/DM027010039MaRDI QIDQ5076122zbMATH OpenOpenAlexFDO

Authors Pamela E. Harris, Erik Insko, Alicia Prieto, Rade Stoisavljevic, Haun Sullivan

Publication date 16 May 2022

Published in Advances and Applications in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cop and robber game on graphspursuit-evasion games on graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Games on graphs (graph-theoretic aspects) (05C57) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43) Cell movement (chemotaxis, etc.) (92C17)

Abstract: Motivated by a biological scenario illustrated in the YouTube video url{ https://www.youtube.com/watch?v=Z_mXDvZQ6dU} where a neutrophil chases a bacteria cell moving in random directions, we present a variant of the cop and robber game on graphs called the tipsy cop and drunken robber game. In this game, we place a tipsy cop and a drunken robber at different vertices of a finite connected graph $G$. The game consists of independent moves where the robber begins the game by moving to an adjacent vertex from where he began, this is then followed by the cop moving to an adjacent vertex from where she began. Since the robber is inebriated, he takes random walks on the graph, while the cop being tipsy means that her movements are sometimes random and sometimes intentional. Our main results give formulas for the probability that the robber is still free from capture after $m$ moves of this game on highly symmetric graphs, such as the complete graphs, complete bipartite graphs, and cycle graphs. We also give the expected encounter time between the cop and robber for these families of graphs. We end the manuscript by presenting a general method for computing such probabilities and also detail a variety of directions for future research.

Recommendations

• The game of cops and robbers on graphs
• The game of Cops and Robber on circulant graphs
• A game of cops and robbers played on products of graphs
• Cops and Robber game with a fast robber on expander graphs and random graphs
• A Tandem version of the Cops and Robber Game played on products of graphs
• A game of cops and robbers on graphs with periodic edge-connectivity
• Cops and robbers in a random graph
• The cops and robber game on graphs with forbidden (induced) subgraphs
• Chasing a drunk robber in many classes of graphs
• The game of overprescribed Cops and Robbers played on graphs

Cites work

• A game of cops and robbers
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Capturing the drunk robber on a graph
• Collisions Among Random Walks on a Graph
• Maximum hitting time for random walks on graphs
• On cop-win graphs
• On the cop number of a graph
• Some results about pursuit games on metric spaces obtained through graph theory techniques
• The capture time of a graph
• Vertex-to-vertex pursuit in a graph

This page was built for publication: TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS

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