The cop number c(G) of a graph G is an invariant connected with the genus and the girth. We prove that for a fixed k there is a polynomial-time algorithm which decides whether c(G) ≤ k. This settles a question of T. Andreae. Moreover, we show that every graph is topologically equivalent to a graph with c ≤ 2. Finally we consider a pursuit-evasion problem in Littlewood′s miscellany. We prove that two lions are not always sufficient to catch a man on a plane graph, provided the lions and the man have equal maximum speed. We deal both with a discrete motion (from vertex to vertex) and with a continuous motion. The discrete case is solved by showing that there are plane graphs of cop number 3 such that all the edges can be represented by straight segments of the same length.
|Autori:||BERARDUCCI A; INTRIGILA B|
|Titolo:||On the cop number of a graph|
|Anno del prodotto:||1993|
|Digital Object Identifier (DOI):||10.1006/aama.1993.1019|
|Appare nelle tipologie:||1.1 Articolo in rivista|