Cops and robbers on oriented toroidal grids

被引：4

作者：

de la Maza, Sebastian Gonzalez Hermosillo ^{[1
]}

Hosseini, Seyyed Aliasghar ^{[1
]}

Knox, Fiachra ^{[1
]}

Mohar, Bojan ^{[1
]}

Reed, Bruce ^{[2
]}

机构：

[1] Simon Fraser Univ, 8888 Univ Dr, Burnaby, BC, Canada

[2] McGill Univ, Sch Comp Sci, 3480 Univ, Montreal, PQ H3A 2A7, Canada

来源：

THEORETICAL COMPUTER SCIENCE | 2021年 / 857卷

基金：

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

关键词：

Cops and robber; Directed graphs; Toroidal grid; Cop number;

D O I：

10.1016/j.tcs.2021.01.012

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13. (c) 2021 Elsevier B.V. All rights reserved.

引用

页码：166 / 176

页数：11

共 8 条

[1]

[Anonymous], 1992, GEOMETRY OF SURFACES

[2]

[Anonymous], 2011, STUDENT MATH LIB

[3]

Bradshaw P., 2020, ARXIV200510849

[4]

Bradshaw Peter, 2019, ARXIV190905342

[5]

Hosseini S.A., 2018, THESIS S FRASER U

[6] Game of cops and robbers in oriented quotients of the integer grid [J].

Hosseini, Seyyed Aliasghar ;

Mohar, Bojan .

DISCRETE MATHEMATICS, 2018, 341 (02) :439-450

[7] VERTEX-TO-VERTEX PURSUIT IN A GRAPH [J].

NOWAKOWSKI, R ;

WINKLER, P .

DISCRETE MATHEMATICS, 1983, 43 (2-3) :235-239

[8]

Quilliot A., 1978, THESIS U PARIS 6, P131

← 1 →