2019/09/06 by Fatemeh Hasiri, Hasiri, Fatemeh, Igor Shinkar +1
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Game Theory and Applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1909.03027
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)), i.e., that O(√(n)) 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 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 Ω(√(n)) generators that are K2,3-free. This shows that the Kövári, Sós, and Turán theorem, stating that any K2,3-free graph of n vertices has at most O(n3/2) edges, is tight up to a multiplicative constant even for abelian Cayley graphs.