Time-delayed Cops and Robbers

被引：0

作者：

Clarke, Nancy E. ^{[1
]}

Cox, Danielle ^{[2
]}

Huggan, Melissa A. ^{[3
]}

Huntemann, Svenja ^{[2
]}

Marbach, Trent G. ^{[4
]}

机构：

[1] Acadia Univ, Dept Math & Stat, Wolfville, NS, Canada

[2] Mt St Vincent Univ, Dept Math & Stat, Halifax, NS, Canada

[3] Vancouver Isl Univ, Dept Math, Nanaimo, BC, Canada

[4] Toronto Metropolitan Univ, Dept Math, Toronto, ON, Canada

来源：

DISCRETE APPLIED MATHEMATICS | 2025年 / 360卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Pursuit evasion; Cops and Robber; Imperfect information; Time delay; Graph;

D O I：

10.1016/j.dam.2024.09.030

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider a variation of the Cops and Robbers game in which the cops do not have perfect information; the information they receive regarding the robber's position is delayed by one round. Our parameter of interest is the time-delayed cop number of a graph G , the minimum number of cops that suffice to guarantee a win on G . We present a variety of results on this parameter, including general bounds, and make comparisons to the cop numbers of known related variants of the original game. We have particular interest in graph products, Meyniel-type bounds, and cop density. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

引用

页码：394 / 405

页数：12

共 14 条

[1] Hyperopic Cops and Robbers
Bonato, A.
Clarke, N. E.
Cox, D.
Finbow, S.
Mc Inerney, F.
Messinger, M. E.
[J]. THEORETICAL COMPUTER SCIENCE, 2019, 794 : 59 - 68
[2] Bonato A., 2011, Student mathematical library
[3] Bonato A., 2007, Contrib. Discrete Math., V2, P133
[4] Cops that surround a robber
Burgess, Andrea C.
Cameron, Rosalind A.
Clarke, Nancy E.
Danziger, Peter
Finbow, Stephen
Jones, Caleb W.
Pike, David A.
[J]. DISCRETE APPLIED MATHEMATICS, 2020, 285 : 552 - 566
[5] Limited visibility Cops and Robber
Clarke, N. E.
Cox, D.
Duffy, C.
Dyer, D.
Fitzpatrick, S. L.
Messinger, M. E.
[J]. DISCRETE APPLIED MATHEMATICS, 2020, 282 : 53 - 64
[6] Clarke N.E., 2002, Doctoral thesis
[7] Clarke N.E., Preprints
[8] DesRoches D., 2016, Honours thesis
[9] COPS AND ROBBERS IN GRAPHS WITH LARGE GIRTH AND CAYLEY-GRAPHS
FRANKL, P
[J]. DISCRETE APPLIED MATHEMATICS, 1987, 17 (03) : 301 - 305
[10] Joret G., 2010, CONTRIB DISCRET MATH, V5, P40, DOI [10.11575/cdm.v5i2.62032, DOI 10.11575/CDM.V5I2.62032]

← 1 2 →