Morris, Joy

Permanent URI for this collection

Now showing 1 - 2 of 2

Cayley graphs on abelian and generalized dihedral groups
(University of Primorska, 2023) Morris, Joy; Skelton, Adrian
A number of authors have studied the question of when a graph can be represented as a Cayley graph on more than one nonisomorphic group. In this paper we give conditions for when a Cayley graph on an abelian group can be represented as a Cayley graph on a generalized dihedral group, and conditions for when the converse is true.
Most generalized Petersen graphs of girth 8 have cop number 4
(Centre for Discrete Mathematics and Computing, 2022) Morris, Joy; Runte, Tigana; Skelton, Adrian
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