A note on the Cops & Robber game on graphs embedded in non-orientable surfaces

Details A note on the Cops & Robber game on graphs embedded in non-orientable surfaces A note on the Cops & Robber game on graphs embedded in non-orientable surfaces

2008-03-04

arxiv.org/abs/0803.0538v3

Mathematics

Combinatorics

5 pages, 1 figure

Scientific paper

The Cops and Robber game is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if they can catch the robber. The minimum number of cops needed to win on a graph is called its cop number. It is known that the cop number of a graph embedded on a surface $X$ of genus $g$ is at most $3g/2 + 3$, if $X$ is orientable (Schroeder 2004), and at most $2g+1$, otherwise (Nowakowski & Schroeder 1997). We improve the bounds for non-orientable surfaces by reduction to the orientable case using covering spaces. As corollaries, using Schroeder's results, we obtain the following: the maximum cop number of graphs embeddable in the projective plane is 3; the cop number of graphs embeddable in the Klein Bottle is at most 4, and an upper bound is $3g/2 + 3/2$ for all other $g$.

Affiliated with

Also associated with

No associations

Rating

A note on the Cops & Robber game on graphs embedded in non-orientable surfaces 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 A note on the Cops & Robber game on graphs embedded in non-orientable surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on the Cops & Robber game on graphs embedded in non-orientable surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-160191