Title of article :
Edge-critical cops and robber in planar graphs
Author/Authors :
Fitzpatrick، نويسنده , , Shannon L.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2014
Pages :
11
From page :
1
To page :
11
Abstract :
The problem is to determine the number of ‘cops’ needed to capture a ‘robber’ in a game in which the cops always know the location of the robber, and the cops and robber move alternately along edges of a reflexive graph. The cops capture the robber if one of them occupies the same vertex as the robber at any time in the game. A cop-win graph is one in which a single cop has a winning strategy. A graph is cop-win edge-critical with respect to edge addition (respectively, deletion) when the original graph is not cop-win, but the addition (deletion) of any edge results in a cop-win graph. In this paper, edge-critical planar graphs are characterized.
Keywords :
Pursuit game , Edge-critical , Cops and robber , Planar graph
Journal title :
Discrete Mathematics
Serial Year :
2014
Journal title :
Discrete Mathematics
Record number :
1600690
Link To Document :
بازگشت