On a pursuit game on Cayley digraphs. (English) Zbl 0639.05026
The author considers a pursuit game on a graph G which was previously studied by A. Quilliot, M. Aigner and M. Fromme, and others; for the rules see e.g. [M. Aigner and M. Fromme, Discrete Appl. Math. 8, 1-11 (1984; Zbl 0539.05052)]. The main result is that \(\lceil 3k/4\rceil\) pursuers can catch the evader when G is a connected Cayley graph of degree k defined on an Abelian group.
Reviewer: Th.Andreae
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 91A24 | Positional games (pursuit and evasion, etc.) |
Citations:
Zbl 0539.05052References:
| [1] | Aigner, M.; Fromme, M., A game of cops and robbers, Appl. Discr.Math., 8, 1-12 (1984) · Zbl 0539.05052 |
| [2] | Andreae, T., Note on a pursuit game played on graphs, Appl. Discr.Math., 9, 111-115 (1984) · Zbl 0548.05056 |
| [3] | P. Frankl, Cops and robbers in graphs with large girth and Caley Preprint.; P. Frankl, Cops and robbers in graphs with large girth and Caley Preprint. |
| [4] | M. Maamoun and H. Meyniel, on a game of policemen and robber, Preprint.; M. Maamoun and H. Meyniel, on a game of policemen and robber, Preprint. |
| [5] | Margulis, G. A., Explicit construction of graphs without short cycles and low density codes, Combinatorica, 2, 71-78 (1982) · Zbl 0492.05044 |
| [6] | A. Quilliot, Jeux positionnels et propriété de Helly, Thèse de 3ème Cycle, Juin 1978, Paris VI.; A. Quilliot, Jeux positionnels et propriété de Helly, Thèse de 3ème Cycle, Juin 1978, Paris VI. |
| [7] | Quilliot, A., Discrete pursuit games, Proceedings of the thirteenth conference on graphs and combinatorics at Boca Raton, Congressus Numerantium, 38, 227-241 (Juin 1983) · Zbl 0574.90108 |
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.
