1-GUARDABLE SUBGRAPHS OF GRAPHS

Year 2024, Volume: 7 Issue: To memory "Assoc. Prof. Dr. Zeynep AKDEMİRCİ ŞANLI", 138 - 145, 29.12.2024

Nazlıcan Çakmak , Emrah Akyar

https://doi.org/10.33773/jum.1564717

Abstract

The cops and robber game is played on a graph. There are two players in the game, consisting of a set of cops and only one robber. They
play, respectively; on each player’s turn, the player may either stay in their vertex or move to an adjacent vertex. The robber is captured when
one of the cops enters the vertex with the robber. Therefore, the cop wins the game, and the game ends.
In this study, 1-guardable subgraphs of graphs in the game of cops and robber are considered. We mention some special subgraphs and their
relations. It is known that if the subgraph is 1-guardable, then it must be isometric, but the converse of this argument may not be true. We
show that for the converse to be true, some conditions must be added.

Keywords

Graphs, Cops and Robber, 1-Guardable

References

• R. Nowakowski, P. Winkler, Vertex-to-Vertex Pursuit in a Graph, Discrete Mathematics, Vol.43, No.2-3, pp.235-239 (1983).
• M. Aigner, M. Fromme, A Game of Cops and Robbers, Discrete Applied Mathematics, Vol.8, No.1, pp.1-12 (1984).
• A. Berarducci, B. Intrigila, On the Cop Number of a Graph, Advances in Applied Mathematics, Vol.14, No.4, pp.389-403 (1993).
• A. Bonato, R. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Society, Providence, RI (2011).
• P. Frankl, Cops and Robbers in Graphs with Large Girth and Cayley-Graphs, Discrete Applied Mathematics, Vol.17, No.3, pp.301-305 (1987).
• E. Chiniforooshan, A Better Bound for the Cop Number of General Graphs, Journal of Graph Theory, Vol.58, No.1, pp.45-48 (2008).
• L. Lu, X. Peng, On Meyniel's Conjecture of the cop Number, Journal of Graph Theory, Vol.71, No.2, pp.192-205 (2012).
• T. Ball, R. W. Bell, J. Guzman, On the Cop Number of Generalized Petersen Graphs, Discrete Mathematics (2016).
• A. Quilliot, A Retraction Problem on Graph Theory, Discrete Mathematics, Vol.54, pp.61-71 (1985).
• A. Bonato, P. Golovach, G. Hahn, J. Kratochvil, The Capture Time of a Graph, Discrete Mathematics, Vol.309, No.18,SI, pp.5588-5595 (2009).
• T. Gavenciak, Cop-win Graphs with Maximum Capture-time, Discrete Mathematics, Vol.310, No.10-11, pp.1557-1563 (2010).
• L. Lu, Z. Wang, A Note on 1-Guardable Graphs in the Cops and Robber Game, Ariv, eprint-1804.02802, math.Co (2018).