A SHORT NOTE ON COPS AND ROBBERS PLAYING ON TOTAL GRAPHS
CHARLES DOMINIC
Department of Mathematics, Universidade de Aveiro, 3810-193, Aveiro, Portugal.
DOMINGOS M. CARDOSO
Department of Mathematics, Universidade de Aveiro, 3810-193, Aveiro, Portugal.
LUKASZ WITKOWSKI
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznan, Poland.
MARCIN WITKOWSKI *
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznan, Poland.
*Author to whom correspondence should be addressed.
Abstract
Cop Robber game is a two player game played on an undirected graph. In this game, the cops try to capture a robber moving on the vertices of the graph. The cop number of a graph is the least number of cops needed to guarantee that the robber will be captured. The total graph T(G) of a graph G has a vertex for each edge and vertex of G and an edge in T(G) for every edge-edge, vertex-edge, and vertex-vertex adjacency in G. In this paper, we play the game on the total graph T(G), showing in particular that c(T(G)) ≤ 3 for every planar graph G.
Keywords: Cops and robbers, vertex-pursuit games