Mathematics – Combinatorics
Scientific paper
2007-12-18
Mathematics
Combinatorics
short communication (final draft, small changes)
Scientific paper
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.
No associations
LandOfFree
The Cops & Robber game on series-parallel graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Cops & Robber game on series-parallel graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Cops & Robber game on series-parallel graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-549220