Cops and Robbers on Graphs of Bounded Diameter

DOI10.1137/19M126606XzbMATH Open1444.05096arXiv1912.07203OpenAlexW3036334686MaRDI QIDQ3300761FDOQ3300761

Authors: Seyyed Aliasghar Hosseini, Fiachra Knox, Bojan Mohar 

Publication date: 30 July 2020

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

Abstract: The game of Cops and Robbers is a well known game played on graphs. In this paper we consider the class of graphs of bounded diameter. We improve the strategy of cops and previously used probabilistic method which results in an improved upper bound for the cop number of graphs of bounded diameter. In particular, for graphs of diameter four, we improve the upper bound from $n^{frac23+o(1)}$ to $n^{frac35+o(1)}$ and for diameter three from $n^{frac23+o(1)}$ to $n^{frac47+o(1)}$.

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

Recommendations

• Cops and Robbers on diameter two graphs
• Cops and robbers on oriented graphs
• Cops and Robbers on Planar‐Directed Graphs
• Cops and robbers in graphs with large girth and Cayley graphs
• Cops and robbers on geometric graphs
• The game of Cops and Robber on circulant graphs
• Cops and robber on some families of oriented graphs
• Cops and robber on some families of oriented graphs
• Cops and robbers on graphs based on designs
• The game of cops and robbers on graphs

zbMATH Keywords

bounded diameterprobabilistic methodCops and Robbers

Mathematics Subject Classification ID

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

Cites Work

• Vertex-to-vertex pursuit in a graph
• On Meyniel's conjecture of the cop number
• The game of cops and robbers on graphs
• A bound for the cops and robbers problem
• Cops and Robbers on diameter two graphs

Cited In (11)

• Cops and Robbers on Planar‐Directed Graphs
• Title not available (Why is that?)
• A partition approach to lower bounds for zero-visibility cops and robber
• Cops and Robbers on diameter two graphs
• A note on hyperopic cops and robber
• The node cop‐win reliability of unicyclic and bicyclic graphs
• Cops and Robbers on String Graphs
• On the Capture Time of Cops and Robbers Game on a Planar Graph
• Cops and robbers on graphs with a set of forbidden induced subgraphs
• The impact of loops on the game of cops and robbers on graphs
• A note on cops and robbers, independence number, domination number and diameter

This page was built for publication: Cops and Robbers on Graphs of Bounded Diameter

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