The one-visibility Localization game
share
We introduce a variant of the Localization game in which the cops only have visibility one, along with the corresponding optimization parameter, the one-visibility localization number ζ_1. By developing lower bounds using isoperimetric inequalities, we give upper and lower bounds for ζ_1 on k-ary trees with k≥ 2 that differ by a multiplicative constant, showing that the parameter is unbounded on k-ary trees. We provide a O(√(n)) bound for K_h-minor free graphs of order n, and we show Cartesian grids meet this bound by determining their one-visibility localization number up to four values. We present upper bounds on ζ_1 using pathwidth and the domination number and give upper bounds on trees via their depth and order. We conclude with open problems.
READ FULL TEXT