Meyniel extremal families of abelian Cayley graphs

DOI10.1007/S00373-022-02460-8zbMATH Open1485.05115arXiv1909.03027OpenAlexW2971858457MaRDI QIDQ2117525FDOQ2117525

Fatemeh Hasiri, Igor Shinkar

Publication date: 21 March 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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(sqrtn)$, i.e., that $O(sqrtn)$ 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(sqrtn)$. This proves that the $O(sqrtn)$ upper bound for Cayley graphs proved by Bradshaw is tight up to a multiplicative constant. In particular, this shows that Meyniel's conjecture, if true, is tight to a multiplicative constant even for abelian Cayley graphs. In order to prove the result, we construct Cayley graphs on $n$ vertices with $Omega(sqrtn)$ generators that are $K_{2,3}$-free. This shows that the K"{o}v'{a}ri, S'{o}s, and Tur'{a}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.

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

zbMATH Keywords

Cayley graphscops and robbersMeyniel extremal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Games on graphs (graph-theoretic aspects) (05C57) Structural characterization of families of graphs (05C75) Games involving graphs (91A43)

Cites Work

• Cops and robbers in graphs with large girth and Cayley graphs
• Vertex-to-vertex pursuit in a graph
• Cops and robbers in a random graph
• The difference between consecutive primes. II
• Variations on cops and robbers
• On Meyniel's conjecture of the cop number
• Chasing robbers on random graphs: Zigzag theorem
• Pursuit-Evasion in Models of Complex Networks
• Title not available (Why is that?)
• A Bound for the Cops and Robbers Problem
• A game of cops and robbers
• Norm-graphs and bipartite Turán numbers
• On a problem of K. Zarankiewicz
• Meyniel's conjecture on the cop number: a survey
• Cops and robbers on graphs based on designs
• Title not available (Why is that?)
• On a pursuit game on Cayley graphs
• A short note about pursuit games played on a graph with a given genus
• Title not available (Why is that?)
• A proof of the Meyniel conjecture for abelian Cayley graphs
• Vertex Pursuit Games in Stochastic Network Models
• Cops and robbers on directed and undirected abelian Cayley graphs

Cited In (1)

• On the cop number of graphs of high girth

This page was built for publication: Meyniel extremal families of abelian Cayley graphs

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