A simple method for proving lower bounds in the zero-visibility cops and robber game

Yuan Xue (), Boting Yang () and Sandra Zilles ()
Additional contact information
Yuan Xue: University of Regina
Boting Yang: University of Regina
Sandra Zilles: University of Regina

Journal of Combinatorial Optimization, 2022, vol. 43, issue 5, No 30, 1545-1570

Abstract: Abstract Cops and Robbers is a classical pursuit and evasion game in graph theory, which was introduced by Nowakowski and Winkler and independently by Quilliot. In this paper, we study the zero-visibility cops and robber game, which is a variant of Cops and Robbers. In the zero-visibility cops and robber game, the robber is invisible to the cops throughout the game. We introduce a simple method for proving lower bounds on the zero-visibility cop number. This lower bound method is based on a connection between the zero-visibility cop number and the matching number. Using this technique, we investigate graph joins, lexicographic products of graphs, complete multipartite graphs and split graphs. For each of these classes of graphs, we prove lower bounds and upper bounds on the zero-visibility cop number. We also present a linear time approximation algorithm for computing the lexicographic product of a tree and a graph G. The approximation ratio of this algorithm is bounded by $$|V(G)| / (\nu (G) + |V(G) {\setminus } V(\mathcal {M}(G))| )$$ | V ( G ) | / ( ν ( G ) + | V ( G ) \ V ( M ( G ) ) | ) , where V(G) is the vertex set of G, $$\nu (G)$$ ν ( G ) is the matching number of G, $$\mathcal {M}(G)$$ M ( G ) is a maximum matching of G and $$V(\mathcal {M}(G))$$ V ( M ( G ) ) is the vertex set of $$\mathcal {M}(G)$$ M ( G ) .

Keywords: Cops and robbers; Zero-visibility cops and robber game; Pursuit evasion games (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00710-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:5:d:10.1007_s10878-021-00710-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00710-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().