论文标题
将强盗局限
Confining the Robber on Cographs
论文作者
论文摘要
在本文中，介绍了{\ em捕获}和{\ em限制}的概念。我们为某些$ k \ ge 4 $的$ k $顶点（称为$ p_k $ - free Graphs）上的图形$ g $提供了一些结构性的条件，因此$ k-3 $ cops没有捕获或限制$ g $的抢劫策略。利用这种条件，我们表明，对于平面cographs和Planar $ p_5 $ - free图，限制COP编号最多是一个和两个。还表明，连接的Caphich的顶点数量，其中一个警察没有限制强盗的策略，其下部的下部紧密，为八个。我们还探索了双胞胎操作的影响 - 众所周知，这些操作对捕获或限制强盗在Cophaphs上所需的警察数量。最后，我们提出了两个关于$ p_5 $的限制COP数字的猜想，以及最小的平面图，即限制三个的COP数字。
In this paper, the notions of {\em trapping} and {\em confining} the robber on a graph are introduced. We present some structural 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$. Utilizing such conditions, we show that for planar cographs and planar $P_5$-free graphs the confining cop number is at most one and two, respectively. It is also shown 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. We also 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. We conclude by posing two conjectures concerning the confining cop number of $P_5$-free graphs and the smallest planar graph of confining cop number of three.
