Throttling for the game of cops and robbers on graphs

DOI10.1016/J.DISC.2018.05.017zbMATH Open1392.05080arXiv1712.07728OpenAlexW2964143920WikidataQ129729219 ScholiaQ129729219MaRDI QIDQ724850FDOQ724850

Authors: Jane Breen, Boris Brimkov, Joshua Carlson, Leslie Hogben, K. E. Perry, Carolyn Reinhart 

Publication date: 26 July 2018

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

Abstract: We consider the cop-throttling number of a graph $G$ for the game of Cops and Robbers, which is defined to be the minimum of $(k+ext{capt}_k(G))$, where $k$ is the number of cops and $ext{capt}_k(G)$ is the minimum number of rounds needed for $k$ cops to capture the robber on $G$ over all possible games. We provide some tools for bounding the cop-throttling number, including showing that the positive semidefinite (PSD) throttling number, a variant of zero forcing throttling, is an upper bound for the cop-throttling number. We also characterize graphs having low cop-throttling number and investigate how large the cop-throttling number can be for a given graph. We consider trees, unicyclic graphs, incidence graphs of finite projective planes (a Meyniel extremal family of graphs), a family of cop-win graphs with maximum capture time, grids, and hypercubes. All the upper bounds on the cop-throttling number we obtain for families of graphs are $O(sqrtn)$.

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

Recommendations

• Optimizing the trade-off between number of cops and capture time in cops and robbers
• scientific article; zbMATH DE number 7232976
• The damage throttling number of a graph
• The cops and robber game on graphs with forbidden (induced) subgraphs
• Bounds on the length of a game of cops and robbers

zbMATH Keywords

cops and robberspositive semidefinitezero forcingpropagation timethrottling

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Zero forcing sets and the minimum rank of graphs
• The capture time of a graph
• Cops and robbers in graphs with large girth and Cayley graphs
• On the cop number of a graph
• Vertex-to-vertex pursuit in a graph
• A note on \(k\)-cop, \(l\)-robber games on graphs
• The game of cops and robbers on graphs
• A game of cops and robbers
• Graph theory
• Cop-win graphs with maximum capture-time
• Zero forcing parameters and minimum rank problems
• Propagation time for zero forcing on a graph
• Positive semidefinite propagation time
• New Results on the Complexity of p-Centre Problems
• When does a random graph have constant cop number?
• Throttling zero forcing propagation speed on graphs
• The capture time of grids
• Bounds on the burning number
• Throttling positive semidefinite zero forcing propagation time on graphs
• The capture time of the hypercube
• The game of overprescribed Cops and Robbers played on graphs
• Restricted power domination and zero forcing problems
• Burning a graph as a model of social contagion
• On the Capture Time of Cops and Robbers Game on a Planar Graph
• Cops and Robbers on Planar‐Directed Graphs
• Throttling for the game of cops and robbers on graphs

Cited In (12)

• Propagation time for probabilistic zero forcing
• Title not available (Why is that?)
• A survey of graph burning
• Throttling for the game of cops and robbers on graphs
• Skew throttling
• Throttling processes equivalent to full throttling on trees
• The damage throttling number of a graph
• Product throttling
• Optimizing the trade-off between number of cops and capture time in cops and robbers
• Power domination throttling
• Title not available (Why is that?)
• Various characterizations of throttling numbers

This page was built for publication: Throttling for the game of cops and robbers on graphs

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