Bounds on the localization number

DOI10.1002/JGT.22546MaRDI QIDQ5066905zbMATH OpenOpenAlexFDO

Authors Anthony Bonato, William B. Kinnersley

Publication date 31 March 2022

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.05286

zbMATH Keywords

degeneracygraph searchinghypercubeslocalization gameouterplanar graphspursuit-evasion games

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

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 $zeta(G)$. We settle a conjecture of cite{nisse1} by providing an upper bound on the localization number as a function of the chromatic number. In particular, we show that every graph with $zeta(G)lek$ has degeneracy less than $3^k$ and, consequently, satisfies $chi(G)le{3}^{zeta(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.

Recommendations

• Localization game for random graphs
• The localization game on oriented graphs
• Localization game on geometric and planar graphs
• Localization game for random geometric graphs
• A note on the localization number of random graphs: diameter two case

Cited in

(12)

• Localization game for random graphs
• Localization game for random geometric graphs
• The localization capture time of a graph
• The localization game on Cartesian products
• The number of loci needed for ELOD calculations
• Effective localization number: Building k-surviving degrees
• Reviews
• Edge and pair queries-random graphs and complexity
• The localization number of designs
• A note on robber locating game
• The localization game on locally finite trees (extended abstract)
• Localization game capture time of trees and outerplanar graphs

This page was built for publication: Bounds on the localization number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066905)