Cop-edge critical generalized Petersen and Paley graphs

Document Type : Original paper

Authors

1 HRIST (Deemed to be university), Bengaluru-560029, Karnataka

2 Adam Mickiewicz University, Poznan, Poland

Abstract

Cop Robber game is a two player game played on an undirected graph. In this game, the cops try to capture a robber moving on the vertices of the graph. The cop number of a graph is the least number of cops needed to guarantee that the robber will be caught. We study textit{cop-edge critical} graphs, i.e. graphs $G$ such that for any edge $e$ in $E(G)$ either $c(G-e)< c(G)$ or $c(G-e)>c(G)$. In this article, we study the edge criticality of generalized Petersen graphs and Paley graphs. 

Keywords

Main Subjects

References

[1] M. Aigner and M. Fromme, A game of cops and robbers, Discrete Appl. Math. 8 (1984), no. 1, 1–12.
[2] W. Ananchuen and L. Caccetta, On the adjacency properties of Paley graphs, Networks 23 (1993), no. 4, 227–236.
[3] W. Ananchuen, L. Caccetta, and W. Australia, On graphs satisfying a strong adacency property, Australas. J. Combin. 8 (1993), 153–168.
[4] W. Baird, A. Beveridge, P. Codenotti, A. Maurer, J. McCauley, and S. Valeva, On the minimum order of $k$-cop-win graphs, Contrib. Discrete Math. 9, no. 1, 70–84.
[5] T. Ball, R.W. Bell, J. Guzman, M. Hanson-Colvin, and N. Schonsheck, On the cop number of generalized Petersen graphs, Discrete Math. 340 (2017), no. 6, 1381–1388.
[6] J. Beck, Combinatorial Games: Tic-Tac-Toe Theory (encyclopedia of mathematics and its applications), vol. 114, Cambridge University Press, Cambridge, 2008.
[7] A. Bonato and R.J. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Soc., 2011.
[8] L. Caccetta, P. Erdös, and K. Vijayan, A property of random graphs, Ars Combin. 19 (1985), 287–294.
[9] D.M. Cardoso, C. Dominic, Ł. Witkowski, and M. Witkowski, On cops and robbers on GΞ and cop-edge critical graphs, Contrib. Discrete Math. 12, no. 2, 167–186.
[10] H.S.M. Coxeter, R. Frucht, and D.L. Powers, Zero-symmetric graphs: Trivalent graphical regular representations of groups, Academic Press, 2014.
[11] F. Harary, Graph Theory, Addison-Wesley, Reading, MA., 1969.
[12] R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43 (1983), no. 2-3, 235–239.
Communications in Combinatorics and Optimization
Volume 8, Issue 2
June 2023
Pages 359-378

Files

Share

How to cite

Statistics