The Cops & Robber game on series-parallel graphs

arXiv0712.2908MaRDI QIDQ6207874FDOQ6207874

Publication date: 18 December 2007

Abstract: The Cops and Robber game is played on undirected finite graphs.

k

cops and one robber are positioned on vertices and take turn in moving along edges. The cops win if, after a move, a cop and the robber are on the same vertex. A graph is called

k

-copwin, if the cops have a winning strategy. It is known that planar graphs are 3-copwin (Aigner & Fromme, 1984) and that outerplanar graphs are 2-copwin (Clarke, 2002). In this short note, we prove that series-parallel (i.e., graphs with no

K_{4}

minor) graphs are 2-copwin. It is a well-known trick in the literature of cops & robber games to define variants of the game which impose restrictions on the possible strategies of the cops (see Clarke, 2002). For our proof, we define the ``cops & robber game with exits. Our proof yields a winning strategy for the cops.

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Games involving graphs (91A43) Graph theory (05C99)

This page was built for publication: The Cops & Robber game on series-parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6207874)