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

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.Non UBCUnreviewedAuthor affiliation: University of Western AustraliaPostdoctora