Bounds on the localization number |
| |
Authors: | Anthony Bonato William B Kinnersley |
| |
Institution: | 1. Department of Mathematics, Ryerson University, Toronto, Ontario, Canada;2. Department of Mathematics, University of Rhode Island, Kingston, Rhode Island |
| |
Abstract: | We consider the localization game played on graphs, wherein a set of cops attempt to determine the exact location of an invisible robber by exploiting distance probes. The corresponding optimization parameter for a graph G is called the localization number and is written as ζ(G). We settle a conjecture of Bosek et al by providing an upper bound on the chromatic number as a function of the localization number. In particular, we show that every graph with ζ(G) ≤ k has degeneracy less than 3k and, consequently, satisfies χ(G) ≤ 3ζ(G). We show further that this degeneracy bound is tight. We also prove that the localization number is at most 2 in outerplanar graphs, and we determine, up to an additive constant, the localization number of hypercubes. |
| |
Keywords: | degeneracy graph searching hypercubes localization game outerplanar graphs pursuit-evasion games |
|
|