Throttling for the game of cops and robbers on graphs

DOI10.1016/J.DISC.2018.05.017MaRDI QIDQ724850zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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)$.

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

Cites work

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

Cited in

(12)

• Propagation time for probabilistic zero forcing
• scientific article; zbMATH DE number 7232976 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 7731182 (Why is no real title available?)
• 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)