Jérémie Turcotte

Nous introduisons le jeu de policiers-voleur sur les graphes. Nous présentons des résultats récents sur les graphes extrémaux pour le cop number. Il est connu que le plus petit graphe nécessitant 3 policiers est le célèbre graphe de Petersen. En utilisant des méthodes formelles et computationnelles, nous déterminons l'ordre minimal des graphes connexes 4-cop-win, confirmant ainsi une conjecture d'Andreae (1986), et plus récemment de Baird et al. (2014), et travaillons vers l'unicité de ce(s) graphe(s). Recherche conjointe avec Samuel Yvon.

We study extremal graphs for the game of Cops and Robbers. It is well known that the smallest connected graph on which 3 cops are needed to capture the robber is the Petersen graph. Using both formal and computational methods, we determine the minimum order of connected 4-cop-win graphs, which confirms a conjecture of Andreae (1986), and later of Baird et al. (2014), and work towards the uniqueness of such graphs. Joint work with Samuel Yvon.

We introduce the game of Cops and Robbers, played on graphs. We present recent progress on graphs which are extremal for the cop number. It is well known that the smallest connected graph for which 3 cops are needed to capture the robber is the Petersen graph. Using both formal and computational methods, we determine the minimum order of connected 4-cop-win graphs, which confirms a conjecture of Andreae (1986), and later of Baird et al. (2014), and work towards the uniqueness of such graphs. Based on joint work with Samuel Yvon.

We consider the game of Cops and robbers on abelian Cayley graphs. By refining the techniques of Frankl, Hamidoune and Bradshaw, we show that the cop number of any undirected abelian Cayley graph is at most \(\frac{1}{\sqrt{(\sqrt{2}-1) e}} \sqrt{n}+\frac{7}{2}\approx 0.9424\sqrt{n}+\frac{7}{2}\), where \(n\) is the number of vertices of the graph. A similar argument shows an upper bound of \(\sqrt{\frac{2}{\left(\sqrt{2}-1\right) e}} \sqrt{n}+2\approx 1.3328\sqrt{n}+2\) for directed abelian Cayley graphs. We also construct families of undirected and directed abelian Cayley graphs with cop number respectively \(\left\lceil\frac{1}{2}\sqrt{n} \right\rceil \) and \(\sqrt{n}\). This shows that our upper bounds are tight up to a relatively small multiplicative factor, and yields new Meyniel extremal families. Joint work with Peter Bradshaw and Seyyed Aliasghar Hosseini.