Most generalized Petersen graphs of girth 8 have cop number 4
Loading...
Date
2022
Authors
Morris, Joy
Runte, Tigana
Skelton, Adrian
Journal Title
Journal ISSN
Volume Title
Publisher
Centre for Discrete Mathematics and Computing
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
Description
Open access article. Creative Commons Attribution 4.0 International license (CC BY 4.0) applies
Keywords
Generalised Petersen graphs , Girth , Cop number
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.