Meyniel's conjecture holds for random d-regular graphs

DOI10.1002/RSA.20874MaRDI QIDQ4973643zbMATH OpenOpenAlexWikidataFDO

Authors Paweł Prałat, Nicholas Wormald

Publication date 28 November 2019

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

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

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)

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

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

Cited in

(8)

• On the cop number and the weak Meyniel conjecture for algebraic graphs
• Goldberg's conjecture is true for random multigraphs
• Meyniel's conjecture on graphs of bounded degree
• Parameterized analysis of the cops and robber problem
• Meyniel's conjecture holds for random graphs
• On the cop number of graphs of high girth
• Linear colouring of binomial random graphs
• Conjectures on cops and robbers

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)