We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Meyniel Extremal Families of Abelian Cayley Graphs.
- Authors
Hasiri, Fatemeh; Shinkar, Igor
- Abstract
We study the game of Cops and Robbers, where cops try to capture a robber on the vertices of a graph. Meyniel's conjecture states that for every connected graph G on n vertices, the cop number of G is upper bounded by O (n) . That is, for every graph G on n vertices O (n) cops suffice to catch the robber. We present several families of abelian Cayley graphs that are Meyniel extremal, i.e., graphs whose cop number is O (n) . This proves that the O (n) upper bound for Cayley graphs proved by Bradshaw (Discret Math 343:1, 2019) is tight. In particular, this shows that Meyniel's conjecture, if true, is tight even for abelian Cayley graphs. In order to prove the result, we construct Cayley graphs on n vertices with Ω (n) generators that are K 2 , 3 -free. This shows that the Kövári, Sós, and Turán theorem, stating that any K 2 , 3 -free graph of n vertices has at most O (n 3 / 2) edges, is tight up to a multiplicative constant even for abelian Cayley graphs.
- Subjects
GRAPH connectivity; CAYLEY graphs; CHARTS, diagrams, etc.; ROBBERS
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02460-8