×

zbMATH — the first resource for mathematics

Lazy cops and robbers on hypercubes. (English) Zbl 1371.05178
Summary: We consider a variant of the game of Cops and Robbers, called Lazy Cops and Robbers, where at most one cop can move in any round. We investigate the analogue of the cop number for this game, which we call the lazy cop number. Lazy Cops and Robbers was recently introduced by D. Offner and K. Ojakian [Australas. J. Comb. 59, 229–250 (2014; Zbl 1296.05130)], who provided asymptotic upper and lower bounds on the lazy cop number of the hypercube. By coupling the probabilistic method with a potential function argument, we improve on the existing lower bounds for the lazy cop number of hypercubes.

MSC:
05C57 Games on graphs (graph-theoretic aspects)
05C65 Hypergraphs
91A43 Games involving graphs
91A24 Positional games (pursuit and evasion, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aigner, M. and Fromme, M. (1984) A game of cops and robbers. Discrete Appl. Math.81-12. doi:10.1016/0166-218X(84)90073-8 · Zbl 0539.05052
[2] Alon, N. and Mehrabian, A. Chasing a fast robber on planar graphs and random graphs. J. Graph Theory, to appear. · Zbl 1305.05142
[3] Baird, W. and Bonato, A. (2012) Meyniel’s conjecture on the cop number: A survey. J. Combinatorics3225-238. doi:10.4310/JOC.2012.v3.n2.a6 · Zbl 1276.05074
[4] Bonato, A. (2011) Catch me if you can: Cops and Robbers on graphs. In Proc. 6th International Conference on Mathematical and Computational Models: ICMCM’11.
[5] Bonato, A., WHAT IS . . . Cop Number?, Notices Amer. Math. Soc., 59, 1100-1101, (2012) · Zbl 1284.91071
[6] Bonato, A. and Chiniforooshan, E. (2009) Pursuit and evasion from a distance: algorithms and bounds. In Proc. ANALCO’09.
[7] Bonato, A., Chiniforooshan, E. and Prałat, P. (2010) Cops and Robbers from a distance. Theoret. Comput. Sci.4113834-3844. doi:10.1016/j.tcs.2010.07.003 · Zbl 1200.91042
[8] Bonato, A., Finbow, S., Gordinowicz, P., Haidar, A., Kinnersley, W. B., Mitsche, D., Prałat, P. and Stacho, L. (2013) The robber strikes back. In Proc. International Conference on Computational Intelligence, Cyber Security and Computational Models: ICC3.
[9] Bonato, A. and Nowakowski, R. J. (2011) The Game of Cops and Robbers on Graphs, AMS. · Zbl 1298.91004
[10] Dudek, A., Gordinowicz, P. and Prałat, P. (2014) Cops and Robbers playing on edges. J. Combinatorics5131-153. doi:10.4310/JOC.2014.v5.n1.a6 · Zbl 1287.05089
[11] Frieze, A., Krivelevich, M. and Loh, P. (2012) Variations on Cops and Robbers. J. Graph Theory69383-402. doi:10.1002/jgt.20591 · Zbl 1243.05165
[12] Kehagias, A., Mitsche, D. and Prałat, P. (2013) Cops and Invisible Robbers: The cost of drunkenness. Theoret. Comput. Sci.481100-120. doi:10.1016/j.tcs.2013.01.032 · Zbl 1291.91039
[13] Kehagias, A. and Prałat, P. (2012) Some Remarks on Cops and Drunk Robbers. Theoret. Comput. Sci.463133-147. doi:10.1016/j.tcs.2012.08.016 · Zbl 1258.91042
[14] Nowakowski, R. J. and Winkler, P. (1983) Vertex-to-vertex pursuit in a graph. Discrete Math.43235-239. doi:10.1016/0012-365X(83)90160-7 · Zbl 0508.05058
[15] Offner, D. and Okajian, K. (2014) Variations of Cops and Robber on the hypercube. Australasian J. Combinatorics59229-250. · Zbl 1296.05130
[16] Quilliot, A. (1978) Jeux et pointes fixes sur les graphes. Thèse de 3ème cycle, Université de Paris VI, pp. 131-145.
[17] West, D. B., Introduction to Graph Theory, (2001), Prentice Hall
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.