Meyniel extremal families of abelian Cayley graphs

DOI10.1007/S00373-022-02460-8MaRDI QIDQ2117525zbMATH OpenOpenAlexFDO

Authors Fatemeh Hasiri, Igor Shinkar

Publication date 21 March 2022

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

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)

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.

Recommendations

• A proof of the Meyniel conjecture for abelian Cayley graphs
• Cops and robbers on directed and undirected abelian Cayley graphs
• On Meyniel's conjecture of the cop number
• Meyniel's conjecture on the cop number: a survey
• On a pursuit game on Cayley graphs

Cites work

• scientific article; zbMATH DE number 1665333 (Why is no real title available?)
• A bound for the cops and robbers problem
• A game of cops and robbers
• A proof of the Meyniel conjecture for abelian Cayley graphs
• A short note about pursuit games played on a graph with a given genus
• Chasing robbers on random graphs: zigzag theorem
• Cops and robbers in a random graph
• Cops and robbers in graphs with large girth and Cayley graphs
• Cops and robbers on directed and undirected abelian Cayley graphs
• Cops and robbers on graphs based on designs
• Meyniel's conjecture on the cop number: a survey
• Norm-graphs and bipartite Turán numbers
• On Meyniel's conjecture of the cop number
• On a problem of K. Zarankiewicz
• On a pursuit game on Cayley graphs
• Pursuit-evasion in models of complex networks
• The difference between consecutive primes. II
• The game of cops and robbers on graphs
• Variations on cops and robbers
• Vertex Pursuit Games in Stochastic Network Models
• Vertex-to-vertex pursuit in a graph
• When does a random graph have constant cop number?

Cited in

(5)

• A proof of the Meyniel conjecture for abelian Cayley graphs
• On the cop number of graphs of high girth
• Meyniel's conjecture on graphs with few P4's
• Meyniel's conjecture holds for random \(d\)-regular graphs
• Cops and robbers on directed and undirected abelian Cayley graphs

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)