Meyniel's conjecture holds for random d-regular graphs

DOI10.1002/RSA.20874zbMATH Open1428.05285arXiv1510.03003OpenAlexW2963647147WikidataQ122871561 ScholiaQ122871561MaRDI QIDQ4973643FDOQ4973643

Authors: Paweł Prałat, Nicholas Wormald 

Publication date: 28 November 2019

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph $G$ is called the cop number of $G$. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant $C$, the cop number of every connected graph $G$ is at most $Csqrt|V(G)|$. In a separate paper, we showed that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. The result was obtained by showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. In this paper, this deterministic result is used to show that the conjecture holds asymptotically almost surely for random $d$-regular graphs when $d=d(n)ge3$.

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

Recommendations

• Meyniel's conjecture holds for random graphs
• Meyniel's conjecture on the cop number: a survey
• Meyniel's conjecture on graphs of bounded degree
• On Meyniel's conjecture of the cop number
• Meyniel extremal families of abelian Cayley graphs

zbMATH Keywords

cops and robbersrandom graphsvertex-pursuit games

Mathematics Subject Classification ID

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

Cited In (4)

• Goldberg's conjecture is true for random multigraphs
• Meyniel's conjecture on graphs of bounded degree
• On the cop number of graphs of high girth
• Linear colouring of binomial random graphs

This page was built for publication: Meyniel's conjecture holds for random \(d\)-regular graphs

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