Research project is (co) funded by the Slovenian Research Agency.
UL Member: Faculty of Mathematics and Physics
Code: Z1-50003
Project: The game of Cops and Robber on graphs and geodesic spaces
Period: 1. 10. 2023 - 30. 9. 2025
Range per year: 1 FTE, category: B
Head: Vesna Iršič
Research activity: Natural sciences and mathematics
Research Organisations, Researchers and Citations for bibliographic records
Project description:
Graphs are used to model problems in different areas, for example, in computer science, chemistry and social sciences. Several real-life situations are best modeled as games on graphs. Studying the spread of a new virus, successfully containing a fire, searching for a lost person in a system of caves, or trying to catch a criminal in an urban environment can all be modeled by the Cops and Robber game on graphs (or one of its variants). However, a more general space is sometimes required to provide a good model for a problem. Thus, studying the Cops and Robber game not only on graphs but also on geodesic spaces is of interest.
For decades the Cops and Robber game has been one of the main topics in graph theory. In addition to several real-life applications, the game is tightly related to some general properties of graphs. The game is played on a graph by two players moving on vertices, one controlling the cops and the other the robber. The cops aim to catch the robber while the robber is trying to avoid being captured. The minimum number of cops needed to catch the robber on a given graph is called the cop number of the graph. The main conjectures in this area concern the upper bounds for the cop number of graphs in terms of their order or genus. Several variations of the game have already been introduced and studied. A recent variation concerns the game played on geodesic spaces instead of graphs. While this variant is similar to some other differential games, it keeps the discrete nature and shows a resemblance to the game played on graphs.
This project aims to investigate the game of Cops and Robber on graphs and on geodesic spaces. The upper bounds for the cop number of geodesic spaces in terms of the properties of the space will be investigated. Particular focus will be given to surfaces, simplicial complexes and metric graphs. When considering the game on graphs, the open conjectures, including Meyniel’s and Schröder’s conjectures, will be considered both for the original game and for some already established variants of the game. Possible improvements in the direction of the open conjectures and possible relations between them will be studied.
