Asian Journal of Mathematics and Computer Research
 

Asian Journal of Mathematics and Computer Research, ISSN No. : 2395-4205 (Print), 2395-4213 (Online), Vol.: 16, Issue.: 1

Short Research Article

A SHORT NOTE ON COPS AND ROBBERS PLAYING ON TOTAL GRAPHS

 

CHARLES DOMINIC1, DOMINGOS M. CARDOSO1, ŁUKASZ WITKOWSKI2 AND MARCIN WITKOWSKI2∗
1Department of Mathematics, Universidade de Aveiro, 3810-193, Aveiro, Portugal.
2Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland.

Abstracts

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.