CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishThe 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 |
File in questo prodotto:
http://hdl.handle.net/11568/25907
Copyright © 2021