A Note on Intersecting Cliques in Cayley Graphs

Abstract

We show that for infinitely many $n$, there exists a Cayley graph $\mathrm{\Gamma }$ of order $n$ in which any two largest cliques have a nonempty intersection. This answers a question of Hahn, Hell, and Poljak. Further, the graphs constructed have a surprisingly small clique number $c_{\mathrm{\Gamma }}=\lfloor \sqrt{2n}\rfloor$ (and we do not know if the constant $\sqrt{2}$ can be made smaller).