.png){kind=icon}
.png){kind=icon}
Return
Cops and robbers on multi-layer graphs
.png){kind=icon}
OA
AI
DOI：10.1016/j.dam.2026.01.017.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 demonstrate 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 increasing function of the cop numbers of the individual layers. We show that it is NP-hard to decide if k cops are sufficient to catch the robber, even if every cop layer is a tree and a set of 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 divisions 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. (c) 2026 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Cops and robbers
Multi-layer graphs
Pursuit-evasion games
Meyniel's conjecture
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
D
IF:
1.1
Papers:
336
Citations:
7.7K