On the number of fixed points of automorphisms of vertex-transitive graphs (Q2064754)

Knowing the maximum number of vertices fixed by a non-trivial automorphism of a graph is useful with regard to determining the full automorphism group of the graph. This characteristic also contains useful structural information about the graph itself. \par The paper under review contains information on the maximum number of vertices fixed by a non-trivial automorphism for two large and interesting classes of graphs: finite connected edge- and vertex-transitive \(4\)-valent graphs and finite connected vertex-transitive \(3\)-valent graphs. The authors show that the only \(4\)-valent finite connected edge- and vertex-transitive graphs which admit a non-trivial automorphism fixing more than one third of the vertices are six graphs of orders not exceeding \(70\), namely \(K_5\), \(K_{5,5} - 5K_2\), the bipartite complement of the Heawood graph, the incidence graph of the projective plane of order \(3\), the Kneser graph of the \(3\)-subsets of a \(7\)-element set, and the canonical double cover of this Kneser graph, and infinitely many Praeger-Xu graphs \(C(r,s)\) with \( 1 \leq s < 2r/3 \) and \( r \geq 3 \). All these graphs are also arc-transitive. Likewise, the only \(3\)-valent finite connected vertex-transitive graphs admitting non-trivial automorphisms fixing more than one third of the vertices are shown to be six graphs of orders not exceeding \(20\), which are \(K_4\), \(K_{3,3}\), the cube, the Petersen graph, the Heawood graph, and the canonical double cover of the Petersen, and infinitely many Split Praeger-Xu graphs \(C(r,s)\) with \( 1 \leq s < 2r/3 \) and \( r \geq 3 \) (where the \(3\)-valent Split Praeger-Xu graph is obtained from the \(4\)-valent Praeger-Xu graph by dividing each vertex into two vertices connected via a new edge). The proofs rely on combinations of various previous results concerning automorphisms of graphs and permutation groups, and are quite involved.