Graph searching - structural properties
Graph searching - structural properties
批准号:
RGPIN-2017-05065
负责人:
Hahn, Gena
金额:
$1.46万
依托单位:
依托单位国家:
加拿大
项目类别:
Discovery Grants Program - Individual
财政年份:
2020
资助国家:
加拿大
项目状态:
已结题
起止时间:
2020-01-01 至 2021-12-31
中文摘要
警匪
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Graph searching - structural properties
-
批准号:RGPIN-2017-05065
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$2.91万
-
财政年份:2022
-
负责人:Hahn, Gena
-
依托单位:
Graph searching - structural properties
-
批准号:RGPIN-2017-05065
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.46万
-
财政年份:2021
-
负责人:Hahn, Gena
-
依托单位:
Graph searching - structural properties
-
批准号:RGPIN-2017-05065
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.46万
-
财政年份:2019
-
负责人:Hahn, Gena
-
依托单位:
Graph searching - structural properties
-
批准号:RGPIN-2017-05065
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.46万
-
财政年份:2018
-
负责人:Hahn, Gena
-
依托单位:
Graph searching and applications
-
批准号:199-2012
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.24万
-
财政年份:2016
-
负责人:Hahn, Gena
-
依托单位:
Graph searching and applications
-
批准号:199-2012
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.24万
-
财政年份:2015
-
负责人:Hahn, Gena
-
依托单位:
Graph searching and applications
-
批准号:199-2012
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.24万
-
财政年份:2014
-
负责人:Hahn, Gena
-
依托单位:
Graph searching and applications
-
批准号:199-2012
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.24万
-
财政年份:2013
-
负责人:Hahn, Gena
-
依托单位:
Graph searching and applications
-
批准号:199-2012
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.24万
-
财政年份:2012
-
负责人:Hahn, Gena
-
依托单位:
Graphs theoretic aspects of networks
-
批准号:199-2005
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.17万
-
财政年份:2009
-
负责人:Hahn, Gena
-
依托单位:
Graphs theoretic aspects of networks
-
批准号:199-2005
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.17万
-
财政年份:2008
-
负责人:Hahn, Gena
-
依托单位:
Graphs theoretic aspects of networks
-
批准号:199-2005
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.17万
-
财政年份:2007
-
负责人:Hahn, Gena
-
依托单位:
Graphs theoretic aspects of networks
-
批准号:199-2005
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.17万
-
财政年份:2006
-
负责人:Hahn, Gena
-
依托单位:
Graphs theoretic aspects of networks
-
批准号:199-2005
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.17万
-
财政年份:2005
-
负责人:Hahn, Gena
-
依托单位:
Cayley graphs and interconnection networks
-
批准号:199-2001
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.17万
-
财政年份:2004
-
负责人:Hahn, Gena
-
依托单位:
Cayley graphs and interconnection networks
-
批准号:199-2001
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.17万
-
财政年份:2003
-
负责人:Hahn, Gena
-
依托单位:
Cayley graphs and interconnection networks
-
批准号:199-2001
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.85万
-
财政年份:2002
-
负责人:Hahn, Gena
-
依托单位:
Cayley graphs and interconnection networks
-
批准号:199-2001
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$0.49万
-
财政年份:2001
-
负责人:Hahn, Gena
-
依托单位:
Interconnection networks, Cayley graphs and homomorphisms
-
批准号:199-1997
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.51万
-
财政年份:2000
-
负责人:Hahn, Gena
-
依托单位:
Interconnection networks, Cayley graphs and homomorphisms
-
批准号:199-1997
-
项目类别:Discovery Grants Program - Individual
-
资助金额:$1.51万
-
财政年份:1999
-
负责人:Hahn, Gena
-
依托单位:
海外基金