Graph searching - structural properties

点击翻译按钮获取中文摘要

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.***