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.

On the cop number of a graph

BERARDUCCI, ALESSANDRO;
1993-01-01

Abstract

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.
1993
Berarducci, Alessandro; Intrigila, B.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/25907
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 75
  • ???jsp.display-item.citation.isi??? 62
social impact