Introduction of some one-searchable graphs

Document Type : Original Article

Author

pnu university

Abstract
Search Graph problems are usually modeled in the form of On-Graph games between one
escaping thief and some police officers. Police intends to arrest the thief while the real goal of robber is
prevention from arrest. As it has been evaluated in this paper, it is known as Cops Robber Game. There
are two specific characteristics for this play which may separate it from others. Firstly it has unlimited
speed and secondly all players have special playing time.

Keywords

Subjects


[1] Aigner, M. & Fromme, M., (1984). A game of cops and robbers, Discrete Appl. Math. 8 , 1-12. 1, 2
[2] Bonato, A., Hahn, G. & Wang, C., (2007). The cop density of a graph, Contrib. Discrete Math. 2 ,133-144. 1
[3] Bonato, A., Pralat, P. & Wang, C., (2009). Pursuit-evasion in models of complex networks, Internet Math., 419-436.1
[4] Clarke, N. E. & Connon, E. L., (2006). Cops, robber, and alarms, Ars Combin. 81 , 283-296. 1
[5] Fomin, F. V., Golovach, P. A. & Kratochv l, J., (2008).On tractability of cops and robbers game, in: Proc.5th IFIP International Conference on Theoretical Computer Science (TCS 2008), Springer-Verlag IFIP International Federation for Information Processing, vol. 237, pp. 171-185. 1
[6] Frankl, P., (1987). On a pursuit game on Cayley graphs, Combinatorica 7 , 67-70. 1
[7] Nowakowski, R. & Winkler, P., (1983). Vertex-to-vertex pursuit in a graph, Discrete Math. 43 , 235-239. 2
Volume 6, Issue 2
Spring 2025
Pages 72-76

  • Receive Date 16 December 2024
  • Revise Date 04 April 2025
  • Accept Date 24 April 2025