Document Type
Article
Publication Date
2025
Publication Title
AUSTRALASIAN JOURNAL OF COMBINATORICS
Abstract
In the runner locating variation of cops and robbers on a graph, a chaser attempts to locate an invisible runner by probing a single vertex v each turn, from which the chaser learns the runner’s distance. The runner is then permitted to stay at his current vertex or move to an adjacent vertex other than v. A graph is locatable if the chaser is able to locate the runner in a finite number of turns, and the location number of a graph is the minimum number of turns necessary to determine the runner’s location regardless of the runner’s evasion strategy. In this paper, we allow the chaser to use multiple probes per turn; this is related to the metric dimension of a graph, which is equivalent to the number of chaser probes needed to locate the runner in one turn. We explore the number of turns required for the chaser to locate the runner when the number of probes ranges from the minimum needed to locate the runner, up to the graph’s metric dimension.
Recommended Citation
Akinrele, Kola; Brandt, Axel; Breen, Elizabeth; Erbes, Catherine; Lee, Matthew; O’Doherty, Patrick; and Rainer, Weston, "Runner locating with multiple probes" (2025). 2025 Faculty Bibliography. 34.
https://collected.jcu.edu/fac_bib_2025/34
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.