Back to Search
Start Over
Meyniel's conjecture holds for random graphs
- Source :
- Random Structures & Algorithms. 48:396-421
- Publication Year :
- 2015
- Publisher :
- Wiley, 2015.
-
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 C|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016
- Subjects :
- Random graph
Discrete mathematics
Conjecture
Applied Mathematics
General Mathematics
010102 general mathematics
0102 computer and information sciences
16. Peace & justice
01 natural sciences
Computer Graphics and Computer-Aided Design
Graph
Combinatorics
010201 computation theory & mathematics
Random regular graph
Almost surely
0101 mathematics
Absolute constant
Software
Connectivity
Mathematics
Subjects
Details
- ISSN :
- 10429832
- Volume :
- 48
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi...........c013809b20f51dfdba846049d7208c77