Graph searching - structural properties

自20世纪80年代以来，人们就开始研究警察与强盗的游戏，特别是在发现了各种图形宽度之间的联系之后。算法和复杂性问题似乎主导了该领域，因为在优化等方面的应用，但一些基本问题仍未得到解答：图的cop-number， k-cop-win图的特征，最优博弈的长度等。我们希望研究由Nowakowski和winkler以及Quillot定义的游戏的这些基本问题，并考虑新的模型。我们的图论小组（两名研究人员，最多五名学生）一直在研究循环对所需的警察数量的影响（有些图在警察之间交替，而不是从无循环图开始一个接一个地添加循环）。2016年夏天，我们制作了一个版本的游戏，其中警察必须在指定的顶点抓住强盗（这不再是一个完全的知识游戏，强盗不知道顶点）。我们希望继续研究这些变体，我们已经有了一些初步结果。我们的算法决定k个警察能否在给定的（有限）图上抓住r个劫匪，用于机器人运动规划，我们认为指定捕获顶点和描述策略的算法对机器人专家也很有用。此外，我们不仅要考虑逮捕暴徒所需的警察数量，还要考虑这样做的成本，从而进行概括。也许多几个警察会少花点钱？这里的主要问题是定义成本。我们考虑了几种可能性，并将继续朝这个方向努力。由于有限正则图除非完全，否则不是双赢的，所以Cayley图没有被考虑太多。我们认为它们值得再看一遍，特别是与上面描述的一些（模糊的）模型联系起来。最后，我们希望研究cop-win无限图。我们相信，理解无限会带来对有限的理解。无限图上的抢抢游戏是不同的（有许多抢赢的顶点传递无限图，但只有完全有限图）。雷纳最近的一篇论文表明，我们一直在向后看这个问题，忽略了一个事实，即对于有限图，而对于无限图，良序的逆是良序。因此，任何试图通过类似于有限图的排序来描述无限图的尝试都注定要失败。这表明，即使对于有限图，我们也应该重新考虑我们的方法。我们正打算这样做。无限共赢图研究的一部分是图的结构性质。推广我们2009年论文的构造，我们有不同于唯一（超）齐次可数图（随机或Rado图）的全称可数图的例子。我们希望继续研究这种结构。

Cops-and-robbersgames have been studied since the 1980's, especially after thediscovery of connections with various graph widths. Algorithmic and complexity questionsseem to dominate the field because of applications in optimisation, among other things, but some basic questions remain unanswered: the cop-number of a graph, a characterisation of k-cop-win graphs, the length of an optimal game, etc.We wish to study these basic questions for the game as defined by Nowakowski andWinkler, and by Quillot, and to consider new models. Our graph theorygroup (two researchers, up to five students) has been studying theinfluence of loops on the number of cops needed (there are graphs that alternate between cop-winand not with the addition of loops one by one starting with a loopless graph). In the summer 2016we have worked on a version of the game in which the cops have to catchthe robber at a specified vertex (this is no longer a total knowledge game, the robber does not know the vertex). We wish to continuestudying these variants where we have some preliminary results. Our algorithm to decide whether k cops can catch r robbers on a given(finite) graph is used in robotics for robot motion planning and we think that specifying a capture vertex and an algorithm to describe a strategy would also be useful to roboticists.Further, we would like to generalise by considering not only the number of cops needed to catch therobber, but also the cost of doing so. Perhaps having a few more copswould cost less? The main problem here is defining the cost. We have considered severalpossibilities and will continue in this direction.Since finite regular graphs are not cop-win unless complete, Cayley graphs have not been much considered. We think theyare worth looking at again, especially in connection with some of the models (vaguely) describedabove.Last, we wish to study cop-win infinite graphs. We believe that understanding the infinite brings an understanding of the finite. Cops-and-robbers games on infinite graphs are different (there are many cop-win vertex transitive infinite graphs but only complete finite ones). Arecent paper by Lehner suggests that we have been looking the problem backwards, overlooking the fact that the reverse of a well-order is a well-order for finite graphs but not for infinite ones. Thus any attempt atcharacterising infinite cop-win graphs through an ordering like that for finite ones is doomed tofailure. This indicates that even forfinite graphs we should reconsider our approach. We propose to do just that.A part of the study of infinite cop-win graphs are the implications to structural properties of graphs. Generalising aconstruction from our 2009 paper we have examples of universal countable graphs that aredifferent from the unique (ultra)homogeneous countable graph (the random, or Rado, graph).We wish to continue studying such structures.