Searching for an intruder on graphs and their subdivisions

DOI10.37236/10577zbMATH Open1492.05099arXiv2104.01739OpenAlexW3145271530MaRDI QIDQ2153405FDOQ2153405

Eugene Lee, Anton Bernshteyn

Publication date: 4 July 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this paper we analyze a variant of the pursuit-evasion game on a graph $G$ where the intruder occupies a vertex, is allowed to move to adjacent vertices or remain in place, and is 'invisible' to the searcher, meaning that the searcher operates with no knowledge of the position of the intruder. On each stage, the searcher is allowed to inspect an arbitrary set of $k$ vertices. The minimum $k$ for which the searcher can guarantee the capture of the intruder is called the inspection number of $G$. We also introduce and study the topological inspection number, a quantity that captures the limiting behavior of the inspection number under subdivisions of $G$. Our central theorem provides a full classification of graphs with topological inspection number up to $3$.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• An evasion game on a graph
• Searching and sweeping graphs: a brief survey
• On some problems of guaranteed search on graphs
• scientific article
• scientific article; zbMATH DE number 2220912

zbMATH Keywords

inspection numbertopological inspection number

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Structural characterization of families of graphs (05C75) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• An annotated bibliography on guaranteed graph searching
• Recontamination does not help to search a graph
• Sweeping graphs with large clique number
• Monotonicity in graph searching
• Topology of series-parallel networks
• An evasion game on a graph
• Searching and sweeping graphs: a brief survey
• Lower bounds on the pathwidth of some grid-like graphs
• Title not available (Why is that?)
• How many lions are needed to clear a grid?
• The complexity of zero-visibility cops and robber
• Finding a princess in a palace: a pursuit-evasion problem
• How to hunt an invisible rabbit on a graph
• A Combinatorial Model of Two-Sided Search

Cited In (5)

• Searching for an evader in an unknown graph by an optimal number of searchers
• Evasiveness of subgraph containment and related properties
• How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks
• The one-visibility localization game
• Non-adaptive and adaptive two-sided search with fast objects

This page was built for publication: Searching for an intruder on graphs and their subdivisions

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