A Sublinear Bound on the Cop Throttling Number of a Graph

2019/01/25 by Anthony Bonato, Bonato, Anthony, Sean English +1
Computer Science · #05C57 #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1901.09011

openalex publication_date 2019/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide a sublinear bound on the cop throttling number of a connected graph. Related to the graph searching game Cops and Robbers, the cop throttling number, written th_c(G), is given by th_c(G)=min_k\k+capt_k(G)\, in which capt_k(G) is the k-capture time, or the length of a game of Cops and Robbers with k cops on the graph G, assuming both players play optimally. No general sublinear bound was known on the cop throttling number of a connected graph. Towards a question asked by Breen et al., we prove that th_c(G)≤ ((2+o(1))n√(W(log(n))))/(√(log(n))), where W=W(x) is the Lambert W function.

Citations

• Vertex-to-vertex pursuit in a graph

Related

• Optimizing the trade-off between number of cops and capture time in Cops and Robbers
• Throttling for the game of Cops and Robbers on graphs
• The damage throttling number of a graph
• Throttling numbers for adversaries on connected graphs
• The Cop Number of Graphs with Forbidden Induced Subgraphs