Graph searching - structural properties

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

Cops-and-robbers*games have been studied since the 1980's, especially after the*discovery of connections with various graph widths. Algorithmic and complexity questions*seem 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 and*Winkler, and by Quillot, and to consider new models. Our graph theory*group (two researchers, up to five students) has been studying the*influence of loops on the number of cops needed (there are graphs that alternate between cop-win*and not with the addition of loops one by one starting with a loopless graph). *In the summer 2016*we have worked on a version of the game in which the cops have to catch*the robber at a specified vertex (this is no longer a total knowledge game, the robber does not know the vertex). We wish to continue*studying 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 the*robber, but also the cost of doing so. Perhaps having a few more cops*would cost less? The main problem here is defining the cost. We have considered several*possibilities 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 they*are worth looking at again, especially in connection with some of the models (vaguely) described*above.****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). A*recent 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 at*characterising infinite cop-win graphs through an ordering like that for finite ones is doomed to*failure. This indicates that even for*finite 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 a*construction from our 2009 paper we have examples of universal countable graphs that are*different from the unique (ultra)homogeneous countable graph (the random, or Rado, graph).*We wish to continue studying such structures.***