Constructible graphs and pursuit
Constructible graphs and pursuit
复制标题
可构造的图表和追踪
DOI：
10.1016/j.tcs.2022.07.023
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Ivan M
中科院分区：
文献类型：
--
作者：
Ivan M
一个（有限或无限）图称为可构造的，如果它可以从一点图通过重复添加控制顶点递归地获得。在有限情形下，可构造图就是cop-win图，但对于无限情形，这一情形还没有得到很好的理解，本文的目的之一就是给出一个cop-win但不可构造的图。这是已知的第一个这样的例子。我们还表明，每一个可数序数出现的一些可构造图的秩，回答了一个问题的埃夫龙，所罗门和斯塔尔。此外，我们给出了一个有限的可构造图，没有建设秩序，其相关的控制映射是一个同态，回答一个问题的Chastand，Laviolette和Polat。Lehner表明，每一个可构造图是一个弱的警察赢（这意味着警察最终可以迫使强盗出任何有限集）。我们的另一个主要目的是研究这个概念与“局部可构造”（每个有限图都包含在一个有限可构造子图中）的概念之间的关系。我们证明了，在温和的额外条件下，每一个局部可构造的图是一个弱cop win。但我们也给出了一个例子来表明，在一般情况下，一个局部可构造的图不一定是一个弱cop win。令人惊讶的是，这个图甚至可以被选择为局部有限的。我们还提出了一些开放的问题。
A (finite or infinite) graph is called constructible if it may be obtained recursively from the one-point graph by repeatedly adding dominated vertices. In the finite case, the constructible graphs are precisely the cop-win graphs, but for infinite graphs the situation is not well understood.One of our aims in this paper is to give a graph that is cop-win but not constructible. This is the first known such example. We also show that every countable ordinal arises as the rank of some constructible graph, answering a question of Evron, Solomon and Stahl. In addition, we give a finite constructible graph for which there is no construction order whose associated domination map is a homomorphism, answering a question of Chastand, Laviolette and Polat.Lehner showed that every constructible graph is a weak cop win (meaning that the cop can eventually force the robber out of any finite set). Our other main aim is to investigate how this notion relates to the notion of ‘locally constructible’ (every finite graph is contained in a finite constructible subgraph). We show that, under mild extra conditions, every locally constructible graph is a weak cop win. But we also give an example to show that, in general, a locally constructible graph need not be a weak cop win. Surprisingly, this graph may even be chosen to be locally finite. We also give some open problems.
登录
查看更多内容
关于可构造图、局部 Helly 图和凸性
影响因子：
0.9
作者：
N. Polat
通讯作者：
N. Polat
图表的捕获时间
DOI：
10.1016/j.disc.2008.04.004
发表时间：
2009
期刊：
Discret. Math.
影响因子：
--
作者：
A. Bonato;P. Golovach;G. Hahn;Jan Kratochvíl
通讯作者：
Jan Kratochvíl
DOI：
10.1002/jgt.3190190105
发表时间：
1995
期刊：
J. Graph Theory
影响因子：
--
作者：
N. Polat
通讯作者：
N. Polat
DOI：
10.1016/j.tcs.2016.04.024
发表时间：
2016
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Florian Lehner
通讯作者：
Florian Lehner
关于共赢图
DOI：
10.1016/s0012-365x(02)00260-1
发表时间：
2002
期刊：
Discret. Math.
影响因子：
--
作者：
G. Hahn;François Laviolette;N. Sauer;R. Woodrow
通讯作者：
R. Woodrow