Cops and robbers on oriented toroidal grids

Autor: Seyyed Aliasghar Hosseini, Fiachra Knox, Bruce Reed, Sebastián González Hermosillo de la Maza, Bojan Mohar
Rok vydání: 2021
Předmět:
FOS: Computer and information sciences
Computer Science::Computer Science and Game Theory
Discrete Mathematics (cs.DM)
General Computer Science
Computer Science::Human-Computer Interaction
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Computer Science::Robotics
Computer Science::Discrete Mathematics
FOS: Mathematics
0202 electrical engineering
electronic engineering
information engineering
Mathematics - Combinatorics
Klein bottle
Mathematics
Discrete mathematics
Toroid
Quantitative Biology::Neurons and Cognition
Torus
16. Peace & justice
Grid
010201 computation theory & mathematics
Bounded function
020201 artificial intelligence & image processing
Combinatorics (math.CO)
Constant (mathematics)
Computer Science - Discrete Mathematics
Zdroj: Theoretical Computer Science. 857:166-176
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2021.01.012
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: