\textsc{Cops and Robber} is a game played on graphs where a set of \textit{cops} aim to \textit{capture} the position of a single \textit{robber}. The main parameter of interest in this game is the \textit{cop number}, which is the minimum number of cops that are sufficient to guarantee the capture of the robber. In a directed graph $\overrightarrow{G}$, the \textit{push} operation on a vertex $v$ reverses the orientation of all arcs incident on $v$. We consider a variation of classical \textsc{Cops and Robber} on oriented graphs, where in its turn, each cop can either move to an out-neighbor of its current vertex or push some vertex of the graph, whereas, the robber can move to an adjacent vertex in its turn. [Das et al., CALDAM, 2023] introduced this variant and established that if $\overrightarrow{G}$ is an orientation of a subcubic graph, then one cop with push ability has a winning strategy. We extend these results to establish that if $\overrightarrow{G}$ is an orientation of a $3$-degenerate graph, or of a graph with maximum degree $4$, then one cop with push ability has a winning strategy.


翻译:\textsc{警察与强盗}是在图上进行的一种博弈,其中一组\textit{警察}旨在\textit{捕获}单个\textit{强盗}的位置。该博弈的主要关注参数是\textit{警察数},即保证捕获强盗所需的最小警察数量。在有向图$\overrightarrow{G}$中,对顶点$v$的\textit{推演}操作会反转所有与$v$关联的弧的方向。我们考虑经典\textsc{警察与强盗}博弈在有向图上的一个变体,其中在每个回合中,每个警察可以移动到其当前顶点的出邻居,或对图的某个顶点进行推演;而强盗在其回合中可以移动到相邻顶点。[Das等人,CALDAM,2023]引入了这一变体,并证明了如果$\overrightarrow{G}$是次立方图的定向,则一名具备推演能力的警察拥有必胜策略。我们扩展了这些结果,证明如果$\overrightarrow{G}$是$3$-退化图的定向,或是最大度数为$4$的图的定向,则一名具备推演能力的警察同样拥有必胜策略。

0
下载
关闭预览

相关内容

【AAAI2023】图序注意力网络
专知会员服务
46+阅读 · 2022年11月24日
NeurIPS 2021 | 寻找用于变分布泛化的隐式因果因子
专知会员服务
17+阅读 · 2021年12月7日
专知会员服务
16+阅读 · 2021年10月4日
专知会员服务
50+阅读 · 2021年6月2日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
40+阅读 · 2020年8月22日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Arxiv
0+阅读 · 12月27日
VIP会员
相关VIP内容
【AAAI2023】图序注意力网络
专知会员服务
46+阅读 · 2022年11月24日
NeurIPS 2021 | 寻找用于变分布泛化的隐式因果因子
专知会员服务
17+阅读 · 2021年12月7日
专知会员服务
16+阅读 · 2021年10月4日
专知会员服务
50+阅读 · 2021年6月2日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
40+阅读 · 2020年8月22日
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员