Most generalized Petersen graphs of girth 8 have cop number 4
| dc.contributor.author | Morris, Joy | |
| dc.contributor.author | Runte, Tigana | |
| dc.contributor.author | Skelton, Adrian | |
| dc.date.accessioned | 2025-12-13T20:21:04Z | |
| dc.date.available | 2025-12-13T20:21:04Z | |
| dc.date.issued | 2022 | |
| dc.description | Open access article. Creative Commons Attribution 4.0 International license (CC BY 4.0) applies | |
| dc.description.abstract | A generalized Petersen graph GP (n, k) is a regular cubic graph on 2n vertices (the parameter k is used to define some of the edges). It was previously shown (Ball et al., 2015) that the cop number of GP (n, k) is at most 4, for all permissible values of n and k. In this paper we prove that the cop number of “most” generalized Petersen graphs is exactly 4. More precisely, we show that unless n and k fall into certain specified categories, then the cop number of GP (n, k) is 4. The graphs to which our result applies all have girth 8. In fact, our argument is slightly more general: we show that in any cubic graph of girth at least 8, unless there exist two cycles of length 8 whose intersection is a path of length 2, then the cop number of the graph is at least 4. Even more generally, in a graph of girth at least 9 and minimum valency δ, the cop number is at least δ +1 | |
| dc.description.peer-review | Yes | |
| dc.identifier.citation | Morris, J., Runte, T., & Skelton, A. (2022). Most generalized Petersen graphs of girth 8 have cop number 4. Australasian Journal of Combinatorics, 83, 204-224. | |
| dc.identifier.uri | https://hdl.handle.net/10133/7256 | |
| dc.language.iso | en | |
| dc.publisher | Centre for Discrete Mathematics and Computing | |
| dc.publisher.department | Department of Mathematics and Computer Science | |
| dc.publisher.faculty | Arts and Science | |
| dc.publisher.institution | University of Lethbridge | |
| dc.subject | Generalised Petersen graphs | |
| dc.subject | Girth | |
| dc.subject | Cop number | |
| dc.title | Most generalized Petersen graphs of girth 8 have cop number 4 | |
| dc.type | Article |