Clique graphs and 2-geodesic transitive graphs of valency 4

Wei Jin (University of Western Australia, Australia)

Let $\Gamma$ be a connected, undirected graph and  $s$ be a positive integer. Then an $s$-arc of $\Gamma$ is an $(s+1)$-tuple $(v_0,v_1,\cdots,v_s)$ of vertices such that $v_{i-1}$ and $v_i$ are adjacent for  $1\leq i \leq s$, and $v_{j-1}\neq v_{j+1}$ for $1\leq j\leq s-1$; an $s$-geodesic from vertex $u$ to  $v$ is a path of shortest length from $u$ to $v$ such that $d_{\Gamma}(u,v)=s\leq \mathrm{diam}(\Gamma)$; the clique graph  $C(\Gamma)$ of $\Gamma$  is the graph with vertex set all maximum cliques of $\Gamma$, and two such cliques are adjacent if and only if they have at least  one common vertex in $\Gamma$. In this paper, we first give a characterisation of a special family of regular graphs such that $[\Gamma(u)]\cong mK_r$ for each $u\in V(\Gamma)$ where $m\geq 1,r\geq 1$, and prove that $\Gamma\cong C(C(\Gamma))$; next, we discuss the relationship between the $(s+1)$-arc transitivity of $\Gamma$ and the $s$-geodesic transitivity of its line graph $L(\Gamma)$ where $s\leq \mathrm{diam}(L(\Gamma))$; finally, as an application of  the above two results we give a classification of 2-geodesic transitive but not 2-arc transitive graphs of valency $4$.

Joint work with Alice Devillers, Cai Heng Li and Cheryl E. Praeger.