
arXiv: 2006.08941
In a game of Cops and Robbers on graphs, usually the cops' objective is to capture the robber---a situation which the robber wants to avoid invariably. In this paper, we begin with introducing the notions of trapping and confining the robber and discussing their relations with capturing the robber. Our goal is to study the confinement of the robber on graphs that are free of a fixed path as an induced subgraph. We present some necessary conditions for graphs $G$ not containing the path on $k$ vertices (referred to as $P_k$-free graphs) for some $k\ge 4$, so that $k-3$ cops do not have a strategy to capture or confine the robber on $G$ (Propositions 2.1, 2.3). We then show that for planar cographs and planar $P_5$-free graphs the confining cop number is at most one and two, respectively (Corollary 2.4). We also show that the number of vertices of a connected cograph on which one cop does not have a strategy to confine the robber has a tight lower bound of eight. Moreover, we explore the effects of twin operations---which are well known to provide a characterization of cographs---on the number of cops required to capture or confine the robber on cographs. Finally, we pose two conjectures on confining the robber on $P_5$-free graphs and the smallest planar graph of confining cop number of three.
FOS: Computer and information sciences, confining cop number, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), 05C57, 91A46, train-chasing lemma, cographs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorial games, \(P_k\)-free graph, Combinatorics (math.CO), game of cops and robbers, trapping cop number, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, confining cop number, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), 05C57, 91A46, train-chasing lemma, cographs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorial games, \(P_k\)-free graph, Combinatorics (math.CO), game of cops and robbers, trapping cop number, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
