Cops and Robbers on Graphs of Bounded Diameter

DOI10.1137/19M126606XMaRDI QIDQ3300761zbMATH OpenOpenAlexFDO

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)

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

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)

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

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

Cites work

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

Cited in

(11)

• On the Capture Time of Cops and Robbers Game on a Planar Graph
• Cops and Robbers on String Graphs
• Cops and robbers on graphs with a set of forbidden induced subgraphs
• A partition approach to lower bounds for zero-visibility cops and robber
• Cops and Robbers on Planar‐Directed Graphs
• The impact of loops on the game of cops and robbers on graphs
• Cops and Robbers on diameter two graphs
• A note on hyperopic cops and robber
• The node cop‐win reliability of unicyclic and bicyclic graphs
• scientific article; zbMATH DE number 6820595 (Why is no real title available?)
• 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)