TY - GEN
T1 - The One-Cop-Moves Game on Graphs of Small Treewidth
AU - Wang, Lusheng
AU - Yang, Boting
PY - 2019/12
Y1 - 2019/12
N2 - This paper considers the one-cop-moves game played on a graph. In this game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph’s edges with perfect information about each other’s positions. The goal of the cops is to capture the robber. At cops’ turns, exactly one cop is allowed to move from his location to an adjacent vertex; at robber’s turns, she is allowed to move from her location to an adjacent vertex or to stay still. We want to find the minimum number of cops to capture the robber. This number is known as the cop number. In this paper, we investigate the cop number of several classes of graphs, including graphs with treewidth at most 2, Halin graphs, and Cartesian product graphs. We also give a characterization of k-winnable graphs in the one-cop-moves game.
AB - This paper considers the one-cop-moves game played on a graph. In this game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph’s edges with perfect information about each other’s positions. The goal of the cops is to capture the robber. At cops’ turns, exactly one cop is allowed to move from his location to an adjacent vertex; at robber’s turns, she is allowed to move from her location to an adjacent vertex or to stay still. We want to find the minimum number of cops to capture the robber. This number is known as the cop number. In this paper, we investigate the cop number of several classes of graphs, including graphs with treewidth at most 2, Halin graphs, and Cartesian product graphs. We also give a characterization of k-winnable graphs in the one-cop-moves game.
UR - http://www.scopus.com/inward/record.url?scp=85078514172&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85078514172&origin=recordpage
U2 - 10.1007/978-3-030-36412-0_42
DO - 10.1007/978-3-030-36412-0_42
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783030364113
T3 - Lecture Notes in Computer Science
SP - 517
EP - 528
BT - Combinatorial Optimization and Applications
PB - Springer
T2 - 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019)
Y2 - 13 December 2019 through 15 December 2019
ER -