BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Vertex-primitive graphs having vertices with almost equal neighbourhoods, and vertex-primitive graphs of valency 5 Verret, Gabriel


A graph is vertex-primitive if its automorphism group does not preserve any nontrivial partition of its vertex-set. It is an easy exercise to prove that (apart from some trivial exceptions) a vertex-primitive graph cannot have distinct vertices with equal neighbourhoods. I will discuss some results about vertex-primitive graphs having two vertices with “almost” equal neighbourhoods, and how these results were used to answer a question of Araújo and Cameron about synchronising permutation groups. These results were also the motivation for a recent classification of vertex-primitive graphs of valency 5. (Graphs of valency at most 4 had previously been classified.) I will describe this classification, some of the issues that arose in the proof, and the connection with the previous problem.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International