We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the monotonic zero-visibility copnumber can be bounded both above and below by positive multiples of the pathwidth.
Autorzy
- prof. dr hab. inż. Dariusz Dereniowski link otwiera się w nowej karcie ,
- Danny Dyer,
- Ryan M. Tifenbach,
- Boting Yang
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1007/s10878-014-9712-6
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2015
Źródło danych: MOSTWiedzy.pl - publikacja "Zero-visibility cops and robber and the pathwidth of a graph" link otwiera się w nowej karcie