×

Containment game played on random graphs: another zig-zag theorem. (English) Zbl 1328.05122

Summary: We consider a variant of the game of Cops and Robbers, called Containment, in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but cannot move along an edge occupied by a cop). The cops win by “containing” the robber, that is, by occupying all edges incident with a vertex occupied by the robber. The minimum number of cops, \(\xi(G)\), required to contain a robber played on a graph \(G\) is called the containability number, a natural counterpart of the well-known cop number \(c(G)\). This variant of the game was recently introduced by N. Komarov and J. Mackey [“Containment: a variation of cops and robbers”, Preprint], who proved that for every graph \(G\), \(c(G) \leq \xi(G) \leq \gamma(G) \Delta(G)\), where \(\gamma(G)\) and \(\Delta(G)\) are the domination number and the maximum degree of \(G\), respectively. They conjecture that an upper bound can be improved and, in fact, \(\xi(G) \leq c(G) \Delta(G)\). (Observe that, trivially, \(c(G) \leq \gamma(G)\).) This seems to be the main question for this game at the moment. By investigating expansion properties, we provide asymptotically almost sure bounds on the containability number of binomial random graphs \(\mathcal{G}(n,p)\) for a wide range of \(p=p(n)\), showing that it forms an intriguing zigzag shape. This result also proves that the conjecture holds for some range of \(p\) (or holds up to a constant or an \(O(\log n)\) multiplicative factors for some other ranges).

MSC:

05C57 Games on graphs (graph-theoretic aspects)
05C80 Random graphs (graph-theoretic aspects)

References:

[1] N. Alon, A. Mehrabian, Chasing a Fast Robber on Planar Graphs and Random Graphs, Journal of Graph Theory 78(2) (2015), 81-96. the electronic journal of combinatorics 22(2) (2015), #P2.3213 · Zbl 1305.05142
[2] D. Bal, A. Bonato, W. Kinnersley, P. Pra lat, Lazy Cops and Robbers on hypercubes, Combinatorics, Probability and Computing, to appear. · Zbl 1371.05178
[3] D. Bal, A. Bonato, W. Kinnersley, P. Pra lat, Lazy Cops and Robbers played on random graphs and graphs on surfaces, preprint 2014. · Zbl 1350.05102
[4] B. Bollob´as, G. Kun, I. Leader, Cops and robbers in a random graph, Journal of Combinatorial Theory Series B 103 (2013), 226-236. · Zbl 1261.05064
[5] A. Bonato, E. Chiniforooshan, P. Pra lat, Cops and Robbers from a distance, Theoretical Computer Science 411 (2010), 3834-3844. · Zbl 1200.91042
[6] A. Bonato, S. Finbow, P. Gordinowicz, A. Haidar, W.B. Kinnersley, D. Mitsche, P. Pra lat, L. Stacho. The robber strikes back, In: Proceedings of the International Conference on Computational Intelligence, Cyber Security and Computational Models (ICC3), 2013. · Zbl 1301.00062
[7] A. Bonato, R.J. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Society, Providence, Rhode Island, 2011. · Zbl 1298.91004
[8] A. Bonato, P. Pra lat, C. Wang, Network security in models of complex networks, Internet Mathematics 4 (2009), 419-436. · Zbl 1206.68030
[9] A. Dudek, P. Gordinowicz, P. Pra lat, Cops and Robbers playing on edges, Journal of Combinatorics 5(1) (2014), 131-153. · Zbl 1287.05089
[10] A. Frieze, M. Krivelevich, P. Loh, Variations on Cops and Robbers, Journal of Graph Theory 69, 383-402. · Zbl 1243.05165
[11] S. Janson, T. Luczak, A. Ruci´nski, Random graphs, Wiley, New York, 2000. · Zbl 0968.05003
[12] A. Kehagias, D. Mitsche, P. Pra lat, Cops and Invisible Robbers: the Cost of Drunkenness, Theoretical Computer Science 481 (2013), 100-120. · Zbl 1291.91039
[13] A. Kehagias, P. Pra lat, Some Remarks on Cops and Drunk Robbers, Theoretical Computer Science 463 (2012), 133-147. · Zbl 1258.91042
[14] N. Komarov, J. Mackey, Containment: A Variation of Cops and Robbers, Preprint 2014. · Zbl 1439.05152
[15] T. Luczak, P. Pra lat, Chasing robbers on random graphs: zigzag theorem, Random Structures and Algorithms 37 (2010), 516-524. · Zbl 1209.05226
[16] D. Offner, K. Okajian, Variations of Cops and Robber on the hypercube, Australasian Journal of Combinatorics 59(2) (2014), 229-250. · Zbl 1296.05130
[17] P. Pra lat, When does a random graph have constant cop number?, Australasian Journal of Combinatorics 46 (2010), 285-296. · Zbl 1196.05089
[18] P. Pra lat, N.C. Wormald, Meyniel’s conjecture holds for random graphs, Random Structures and Algorithms, to appear.
[19] P. Pra lat, N.C. Wormald, Meyniel’s conjecture holds for random d-regular graphs, preprint 2014.
[20] V. Vu, A large deviation result on the number of small subgraphs of a random graph, Combinatorics, Probability and Computing, 10 (2001), no. 1, 79-94. the electronic journal of combinatorics 22(2) (2015), #P2.3214 · Zbl 0982.05092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.