The game of cops and robber is a turn based vertex pursuit game played on a connected graph between a team of cops and a single robber. The cops and the robber move alternately along the edges of the graph. We say the team of cops win the game if a cop and the robber are at the same vertex of the graph. The minimum number of cops required to win in each component of a graph is called the cop number of the graph. Sivaraman [Discrete Math. 342(2019), pp. 2306-2307] conjectured that for every $t\geq 5$, the cop number of a connected $P_t$-free graph is at most $t-3$, where $P_t$ denotes a path on $t$~vertices. Turcotte [Discrete Math. 345 (2022), pp. 112660] showed that the cop number of any $2K_2$-free graph is at most $2$, which was earlier conjectured by Sivaraman and Testa. Note that if a connected graph is $2K_2$-free, then it is also $P_5$-free. Liu showed that the cop number of a connected ($P_t$, $H$)-free graph is at most $t-3$, where $H$ is a cycle of length at most $t$ or a claw. So the conjecture of Sivaraman is true for ($P_5$, $H$)-free graphs, where $H$ is a cycle of length at most $5$ or a claw. In this paper, we show that the cop number of a connected ($P_5,H$)-free graph is at most $2$, where $H\in \{C_4$, $C_5$, diamond, paw, $K_4$, $2K_1\cup K_2$, $K_3\cup K_1$, $P_3\cup P_1\}$.
翻译:警察与强盗的游戏是一个基于转折的顶点追击游戏。警察和强盗在一组警察与一个强盗之间连接的图表上玩了一个基于转弯的顶点。警察和强盗在图形的边缘轮流移动。我们说,如果警察和强盗在图形的顶点上,警察队赢得了游戏。在图的每个部分中,赢得警察的最低人数被称为图的警号。Sivaraman [Discrete Math. 342(2019),pp. 2306-3307] 预测,每5美元美元,就连通的P_t$的警号,最多为$3美元, 其中$3美元, 美元表示警察队赢得游戏的警队获胜, $3美元, 美元