Cops and robbers on directed and undirected abelian Cayley graphs

被引：7

作者：

Bradshaw, Peter ^{[1
]}

Hosseini, Seyyed Aliasghar ^{[1
]}

Turcotte, Jeremie ^{[2
]}

机构：

[1] Simon Fraser Univ, Dept Math, Vancouver, BC, Canada

[2] Univ Montreal, Dept Math & Stat, Montreal, PQ, Canada

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2021年 / 97卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

PURSUIT GAME;

D O I：

10.1016/j.ejc.2021.103383

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the cop number of directed and undirected Cayley graphs on abelian groups is in O(root 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 in Theta(root n). (C) 2021 Elsevier Ltd. All rights reserved.

引用

页数：19

共 27 条

[1] A GAME OF COPS AND ROBBERS [J].

AIGNER, M ;

FROMME, M .

DISCRETE APPLIED MATHEMATICS, 1984, 8 (01) :1-12

[2]

Babai L., 1985, European Journal of Combinatorics, V6, P101, DOI [DOI 10.1016/S0195-6698(85)80001-9.190,195, 10.1016/S0195-6698(85)80001-9, DOI 10.1016/S0195-6698(85)80001-9]

[3]

Baird W, 2012, J COMB, V3, P225

[4]

BAKER RC, 2001, P LOND MATH SOC, P83

[5] Cops and Robbers on Graphs Based on Designs [J].