×

The capture time of a graph. (English) Zbl 1177.91056

Summary: We consider the game of cops and robbers played on finite and countably infinite connected graphs. The length of games is considered on cop-win graphs, leading to a new parameter, the capture time of a graph. While the capture time of a cop-win graph on \(n\) vertices is bounded above by \(n - 3\), half the number of vertices is sufficient for a large class of graphs including chordal graphs. Examples are given of cop-win graphs which have unique corners and have capture time within a small additive constant of the number of vertices. We consider the ratio of the capture time to the number of vertices, and extend this notion of capture time density to infinite graphs. For the infinite random graph, the capture time density can be any real number in [0,1]. We also consider the capture time when more than one cop is required to win. While the capture time can be calculated by a polynomial algorithm if the number \(k\) of cops is fixed, it is NP-complete to decide whether \(k\) cops can capture the robber in no more than \(t\) moves for every fixed \(t\).

MSC:

91A43 Games involving graphs
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B., Searching and sweeping graphs: A brief survey, Matematiche (Catania), 59, 5-37 (2006) · Zbl 1195.05019
[2] Berarducci, A.; Intrigila, B., On the cop number of a graph, Adv. Appl. Math., 14, 389-403 (1993) · Zbl 0801.90150
[3] Bonato, A.; Hahn, G.; Wang, C., The cop density of a graph, Contrib. Discrete Math, 2, 133-144 (2007) · Zbl 1203.05131
[4] Cameron, P. J., The random graph, (Graham, R. L.; Nešetřil), J., Algorithms and Combinatorics, vol. 14 (1997), Springer Verlag: Springer Verlag New York), 333-351 · Zbl 0864.05076
[5] N. Clarke, Constrained Cops and Robber, Ph.D Dissertation, Dalhousie University, 2002; N. Clarke, Constrained Cops and Robber, Ph.D Dissertation, Dalhousie University, 2002
[6] Erdős, P.; Rényi, A., Asymmetric graphs, Acta Mathematica Academiae Scientiarum Hungaricae, 14, 295-315 (1963) · Zbl 0118.18901
[7] F.V. Fomin, D.M. Thilikos, An annotated bibliography of guaranteed graph searching, preprint, 2007; F.V. Fomin, D.M. Thilikos, An annotated bibliography of guaranteed graph searching, preprint, 2007 · Zbl 1160.68007
[8] Garey, M.; Johnson, D., Computers and Intractability (1979), W.H.Freeman
[9] T. Gavenčiak, Cop-win graphs with maximal capture-time, preprint, 2007; T. Gavenčiak, Cop-win graphs with maximal capture-time, preprint, 2007
[10] Goldstein, A. S.; Reingold, E. M., The complexity of pursuit on a graph, Theoret. Comput. Sci., 143, 93-112 (1995) · Zbl 0873.68152
[11] Hahn, G., Cops, robbers and graphs, Tatra Mt. Math. Publ., 36, 1-14 (2007) · Zbl 1164.05063
[12] Hahn, G.; Laviolette, F.; Sauer, N.; Woodrow, R. E., On cop-win graphs, Discrete Math., 258, 27-41 (2002) · Zbl 1009.05085
[13] Hahn, G.; MacGillivray, G., A note on \(k\)-cop, \(l\) robber games on graphs, Discrete Mathematics, 306, 2492-2497 (2006) · Zbl 1201.91018
[14] Hahn, G.; Tardif, C., Graph homomorphisms: Structure and symmetry, (Hahn, G.; Sabidussi, G., Graph Symmetry. Graph Symmetry, NATO ASI Series C, vol. 497 (1997), Kluwer), 107-166 · Zbl 0880.05079
[15] P. Hell, J. Nešetřil, Graphs and homomorphisms, Oxford Lecture Series in Mathematics and Applications, Oxford, 2004; P. Hell, J. Nešetřil, Graphs and homomorphisms, Oxford Lecture Series in Mathematics and Applications, Oxford, 2004
[16] Kratochvíl, J., A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Appl. Math., 52, 233-252 (1994) · Zbl 0810.68083
[17] Nowakowski, R.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235-239 (1983) · Zbl 0508.05058
[18] A. Quilliot, Jeux et pointes fixes sur les graphes, Ph.D Dissertation, Université de Paris VI, 1978; A. Quilliot, Jeux et pointes fixes sur les graphes, Ph.D Dissertation, Université de Paris VI, 1978
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.