Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 31 min ago
PreprintCC BY 4.0arXiv

The directional localization game on graphs

  • John Jones
  • William B. Kinnersley
Open at sourcePDFDOICite

Abstract

In the localization game on a graph G, a team of cops searches for an invisible, mobile robber on G by "probing" vertices; each probe tells the cops the distance from the probed vertex to the robber. The cops win if they can uniquely determine the robber's location. In this paper, we introduce a related game: the directional localization game. In this game, instead of probes returning distances, they return directions: when the cops probe a vertex v, the robber must respond with one or more neighbors of v that lie on a shortest path from v to the robber's location. The minimum number of cops needed to win this game on G is the directional localization number of G. We study the directional localization game on several classes of graphs, including chordal graphs, Cartesian products, and incidence graphs of projective planes. We also bound the directional localization number of a graph G in terms of the degeneracy and the treewidth of G.

Related

  1. SymNetPro: LOS-Aware Directional Multi-Transmitter Localization from Sparse Radio Observations
    Lyuzhou Ye, Heng Fan, Yan Huang
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
    Lasitha Jayasinghe
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Gaussian and non-Gaussian limits for the total edge-length of random directional nearest-neighbour graphs
    Nicholas Georgiou, Qasem M. Tawhari, Andrew Wade
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  4. The game chromatic number of generalized Mycielski graphs of paths and cycles
    Yushuang Mou, Qiang Sun, Chao Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. On the majority game chromatic number of forests and other graphs
    Yash Chawda, Saraswati Girish Nanoti, Brahadeesh Sankarnarayanan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{jones2026directional,
  title = {{The directional localization game on graphs}},
  author = {John Jones and William B. Kinnersley},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.01745},
  eprint = {2609.01745},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.01745},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The directional localization game on graphs
AU  - John Jones
AU  - William B. Kinnersley
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.01745
UR  - https://arxiv.org/abs/2609.01745
AB  - In the localization game on a graph G, a team of cops searches for an invisible, mobile robber on G by "probing" vertices; each probe tells the cops the distance from the probed vertex to the robber. The cops win if they can uniquely determine the robber's location. In this paper, we introduce a related game: the directional localization game. In this game, instead of probes returning distances, they return directions: when the cops probe a vertex v, the robber must respond with one or more neighbors of v that lie on a shortest path from v to the robber's location. The minimum number of cops needed to win this game on G is the directional localization number of G. We study the directional localization game on several classes of graphs, including chordal graphs, Cartesian products, and incidence graphs of projective planes. We also bound the directional localization number of a graph G in terms of the degeneracy and the treewidth of G.
ER  -