Cops and Robbers on Multi-Layer Graphs

Jessica, Enright, William, Pettersson, Kitty, Meeks and Sylvester, John ORCID: 0000-0002-6543-2934 (2023) Cops and Robbers on Multi-Layer Graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023).

Text
pursuit_on_multilayer-2.pdf - Author Accepted Manuscript
Download (363kB) | Preview

Official URL: http://dx.doi.org/10.1007/978-3-031-43380-1_23

Abstract

We generalise the popular cops and robbers game to multi-layer graphs, where each cop and the robber are restricted to a single layer (or set of edges). We show that initial intuition about the best way to allocate cops to layers is not always correct, and prove that the multi-layer cop number is neither bounded from above nor below by any function of the cop numbers of the individual layers. We determine that it is NP-hard to decide if k cops are sufficient to catch the robber, even if each layer is a tree plus some isolated vertices. However, we give a polynomial time algorithm to determine if k cops can win when the robber layer is a tree. Additionally, we investigate a question of worst-case division of a simple graph into layers: given a simple graph G, what is the maximum number of cops required to catch a robber over all multi-layer graphs where each edge of G is in at least one layer and all layers are connected? For cliques, suitably dense random graphs, and graphs of bounded treewidth, we determine this parameter up to multiplicative constants. Lastly we consider a multi-layer variant of Meyniel’s conjecture, and show the existence of an infinite family of graphs whose multi-layer cop number is bounded from below by a constant times n/log n, where n is the number of vertices in the graph.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	31 Aug 2023 07:57
Last Modified:	02 Nov 2023 02:36
DOI:	10.1007/978-3-031-43380-1_23
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3172434