Uniformly vertex-transitive graphs

MaRDI QIDQ6330135zbMATH OpenFDO

Authors Simon Schmidt, Chase Vogeli, Moritz Weber

Publication date 29 November 2019

Mathematics Subject Classification ID

Graph theory (05C99) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Abstract: We introduce uniformly vertex-transitive graphs as vertex-transitive graphs satisfying a stronger condition on their automorphism groups, motivated by a problem which arises from a Sinkhorn-type algorithm. We use the derangement graph $D(Gamma)$ of a given graph $Gamma$ to show that the uniform vertex-transitivity of $Gamma$ is equivalent to the existence of cliques of sufficient size in $D(Gamma)$. Using this method, we find examples of graphs that are vertex-transitive but not uniformly vertex-transitive, settling a previously open question. Furthermore, we develop sufficient criteria for uniform vertex-transitivity in the situation of a graph with an imprimitive automorphism group. We classify the non-Cayley uniformly vertex-transitive graphs on less than 30 vertices outside of two complementary pairs of graphs.

This page was built for publication: Uniformly vertex-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330135)