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 interni: | |
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 |