On generalised Petersen graphs of girth 7 that have cop number 4

DOI10.26493/2590-9770.1382.2ADMaRDI QIDQ5045260zbMATH OpenOpenAlexFDO

Authors Harmony Morris, Joy Morris

Publication date 4 November 2022

Published in The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.00699

zbMATH Keywords

cop numbercops and robbersgeneralised Petersen graphsgirth

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Combinatorial games (91A46)

Abstract: We show that if $n=7k/i$ with $iin1,2,3$ then the cop number of the generalised Petersen graph $GP(n,k)$ is $4$, with some small previously-known exceptions. It was previously proved by Ball et al. (2015) that the cop number of any generalised Petersen graph is at most $4$. The results in this paper explain all of the known generalised Petersen graphs that actually have cop number $4$ but were not previously explained by Morris et al. in a recent preprint, and places them in the context of infinite families. (More precisely, the preprint by Morris et al. explains all known generalised Petersen graphs with cop number $4$ and girth $8$, while this paper explains those that have girth $7$.)

Recommendations

• Most generalized Petersen graphs of girth 8 have cop number 4
• On the cop number of generalized Petersen graphs
• A game of cops and robbers
• On the cop number of a graph
• On the cop number of graphs of high girth

Cites work

• I-graphs and the corresponding configurations
• On the cop number of generalized Petersen graphs
• The game of cops and robbers on graphs
• Vertex-to-vertex pursuit in a graph

Cited in

(2)

• On the cop number of generalized Petersen graphs
• Most generalized Petersen graphs of girth 8 have cop number 4

This page was built for publication: On generalised Petersen graphs of girth 7 that have cop number 4

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5045260)