Cops and robbers on directed and undirected abelian Cayley graphs

2019/09/11 by Bradshaw, Peter, Hosseini, Seyyed Aliasghar, Turcotte, Jérémie · 1 citation
#05C25 #05C57 (Primary) 05C20 #05E15 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1909.05342

Abstract

We show that the cop number of directed and undirected Cayley graphs on abelian groups has an upper bound of the form of O(√(n)), where n is the number of vertices, by introducing a refined inductive method. With our method, we improve the previous upper bound on cop number for undirected Cayley graphs on abelian groups, and we establish an upper bound on the cop number of directed Cayley graphs on abelian groups. We also use Cayley graphs on abelian groups to construct new Meyniel extremal families, which contain graphs of every order n with cop number Θ(√(n)).

Cited by

• Pushing Cops and Robber on Graphs of Maximum Degree 4

Related

• Meyniel Extremal Families of Abelian Cayley Graphs
• The Lamplighter groups have infinite weak cop number
• Meyniel's conjecture on the cop number: a survey
• Topological directions in Cops and Robbers
• A new bound for the cops and robbers problem