Searching for an intruder on graphs and their subdivisions

DOI10.37236/10577MaRDI QIDQ2153405zbMATH OpenOpenAlexFDO

Authors Anton Bernshteyn, Eugene Lee

Publication date 4 July 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

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

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)

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$.

Recommendations

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

Cites work

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

Cited in

(6)

• 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
• Contiguous search problem in Sierpiński graphs
• 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)