Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On a Generalization of Meyniel’s Conjecture on the Cops and Robbers Game. | On a Generalization of Meyniel s Conjecture on the Cops and Robbers Game Noga Alon Tel Aviv University and Institute for Advanced Study Princeton nogaa@ Abbas Mehrabian Department of Combinatorics and Optimization University of Waterloo amehrabian@ Submitted Oct 11 2010 Accepted Jan 11 2011 Published Jan 19 2011 Mathematics Subject Classification 05C57 Abstract We consider a variant of the Cops and Robbers game where the robber can move s edges at a time and show that in this variant the cop number of a connected s 3 graph on n vertices can be as large as Q ns 1 . This improves the Q ns 2 lower bound of Frieze et al. 5 and extends the result of the second author 10 which establishes the above bound for s 2 4. 1 Introduction The game of Cops and Robbers introduced by Nowakowski and Winkler 11 and independently by Quilliot 13 is a perfect information game played on a finite graph G. There are two players a set of cops and a robber. Initially the cops are placed on vertices of their choice in G where more than one cop can be placed at a vertex . Then the robber being fully aware of the cops placement positions herself in one of the vertices of G. Then the cops and the robber move in alternate rounds with the cops moving first where every cop may move in each round and players are permitted to remain stationary on their turn if they wish. The players use the edges of G to move from vertex to vertex. The cops Research supported in part by an ERC Advanced grant by a USA-Israeli BSF grant by the Oswald Veblen Fund and by the Bell Companies Fellowship. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P19 1 win and the game ends if eventually a cop steps into the vertex currently occupied by the robber otherwise . if the robber can elude the cops indefinitely the robber wins. The parameter of interest is the cop number of G which is defined as the minimum number of cops needed to ensure that the cops can win. We will assume that the graph G is simple
