On the number of fixed edges of automorphisms of vertex-transitive graphs of small valency

Potočnik and Spiga have proved in [11] that, if \(\varGamma \) is a finite connected 3-valent vertex-transitive graph, or a 4-valent vertex- and edge-transitive graph then, unless \(\varGamma \) belongs to a well-known family of graphs, every non-identity automorphism of \(\varGamma \) fixes at most 1/3 of the vertices. In the same work, they have proposed a similar investigation with respect to the edges of the graph, see [11, Problem 1.7]. In this paper we solve this problem.

Theorem 1

Let \(\varGamma \) be a finite connected 4-valent vertex- and edge-transitive graph admitting a non-identity automorphism fixing more than 1/3 of the edges. Then one of the following holds:

1. 1.

   \(\varGamma \) is isomorphic to the complete graph on 5 vertices;

2. 2.

   \(\varGamma \) is isomorphic to a Praeger–Xu graph C(r, s), for some r and s with \(3s < 2r-3\).

Theorem 2

Let \(\varGamma \) be a finite connected 3-valent vertex-transitive graph admitting a non-identity automorphism fixing more than 1/3 of the edges. Then \(\varGamma \) is isomorphic to a split Praeger–Xu graph SC(r, s), for some r and s with \(3s < 2r-2\).

We refer to Sect. 2.3 for the definition of the ubiquitous Praeger–Xu graphs and for their splitting. The bound in Theorem 2 is sharp. For instance, each 3-valent graph admitting a non-identity automorphism fixing elementwise a complete matching has the aforementioned property. For valency 4, we conjecture that the bound 1/3 in Theorem 1 can be strengthened to 1/4, by eventually including some more small exceptional graphs in part (1).

Theorems 1 and 2 rely on the following group-theoretic fact:

Theorem 3

[10, Theorem 1.1] Let G be a finite transitive permutation group on \(\varOmega \) containing no non-identity normal subgroup of order a power of 2. Suppose there exists \(\omega \in \varOmega \) such that the stabilizer \(G_\omega \) of \(\omega \) in G is a 2-group. Then, every non-identity element of G fixes at most 1/3 of the points.

The main results of this paper and the results in [11] show that, besides small exceptions or well-understood families of graphs, non-identity automorphisms of 3-valent or 4-valent vertex-transitive graphs cannot fix many vertices or edges, where “too many” in this context has to be considered as a linear function on the number of vertices (and, even then, with a small caveat for 4-valent graphs, because of the assumption of edge-transitivity). In our opinion, the difficulty in having a unifying theory of vertex-transitive graphs of small valency admitting non-identity automorphisms fixing too many vertices or edges is due to our lack of understanding possible generalizations of Praeger–Xu graphs, that is, a family of vertex-transitive graphs of bounded valency playing the role of Praeger–Xu graphs. It seems to us that this is a recurrent problem in the theory of groups acting on finite graphs of bounded valency. A general investigation in this direction, but with much weaker bounds and only for arc-transitive graphs, is in [7].

Investigations on the number of fixed points of graph automorphisms do have interesting applications. For instance, very recently Potočnik, Toledo and Verret [14] pivoting on the results in [11] have proved remarkable results on the cycle structure of general automorphisms of 3-valent vertex-transitive and 4-valent arc-transitive graphs.

1.1 Structure of the paper

In Sect. 2, we introduce some basic terminology and, in particular, we introduce the Praeger–Xu graphs and their splitting. Then, we start in Sect. 3 with some preliminary results. In Sect. 4, we prove Theorem 1 and, in Sect. 5, we prove Theorem 2.

2.1 Basic group-theoretic notions

Given a permutation g on a set \(\varOmega \), we write \(\mathrm {Fix}(\varOmega ,g)\) for the set of fixed points of g , i.e.

and we write \(\mathrm {fpr} (\varOmega ,g)\) for the fixed-point ratio of g , i.e.

A permutation group G on \(\varOmega \) is said to be semiregular if the identity is the only element fixing some point. When G is semiregular and transitive on \(\varOmega \), the group G is regular on \(\varOmega \).

Given a permutation group G of \(\varOmega \) and a partition \(\Sigma \) of \(\varOmega \), we say that \(\Sigma \) is G-invariant if \(\sigma ^g\in \pi \), for every \(\sigma \in \Sigma \). Given a normal subgroup N of G, the orbits of N on \(\varOmega \) form a G-invariant partition, which we denote by \(\varOmega / N\).

We present here a useful lemma involving the notion just defined.

Lemma 1

[11, Lemma 1.17] Let G be a group acting transitively on \(\varOmega \) and let \(\Sigma \) be a G-invariant partition of \(\varOmega \). For \(g\in G\), let \(g^\Sigma \) be the permutation of \(\Sigma \) induced by g. Then \( \mathrm {fpr}(\varOmega , g) \le \mathrm {fpr}(\Sigma , g^\Sigma ).\) In particular, if \(N\unlhd G\), then \(\mathrm {fpr}(\varOmega , g) \le \mathrm {fpr}(\varOmega /N, Ng)\).

2.2 Basic graph-theoretic notions

In this paper, a digraph is a binary relation

where \(A\varGamma \subseteq V\varGamma \times V\varGamma \). We refer to the elements of \(V\varGamma \) as vertices and to the elements of \(A\varGamma \) as arcs. A graph is a finite simple undirected graph, i.e. a pair

where \(V\varGamma \) is a finite set of vertices, and \(E\varGamma \) is a set of unordered pairs of \(V\varGamma \), called edges. In particular, a graph can be thought of as a digraph where the binary relation is symmetric and contains no loops. Given a non-negative integer s, an s-arc of \(\varGamma \) is an ordered set of \(s+1\) adjacent vertices with any three consecutive elements pairwise distinct. When \(s=0\), an s-arc is simply a vertex of \(\varGamma \); when \(s=1\), an s-arc is simply an arc, that is, an oriented edge.

The girth of \(\varGamma \), denoted by \(g(\varGamma )\), is the minimum length of a cycle in \(\varGamma \).

We denote by \(\varGamma (v)\) the neighbourhood of the vertex v. The size of \(|\varGamma (v)|\) is the valency of v. We are mainly dealing with regular graphs, that is, with graphs where \(|\varGamma (v)|\) is constant as v runs through the elements of \(V\varGamma \). In these cases, we refer to the valency of the graph.

Let \(\varGamma \) be a graph, let G be a subgroup of the automorphism group \(\mathrm {Aut}(\varGamma )\) of \(\varGamma \), let \(v \in V\varGamma \) and let \(w\in \varGamma (v)\). We denote by \(G_v\) the stabilizer of the vertex v, by \(G_{\{v,w\}}\) the setwise stabilizer of the edge \(\{v,w\}\), by \(G_{vw}\) the pointwise stabilizer of the edge \(\{v,w\}\) (that is, the stabilizer of the arc (v, w) underlying the edge \(\{v,w\}\)). The group \(G_v\) acts on \(\varGamma (v)\) and we denote by \(G_v^{[1]}\) the kernel of the action of \(G_v\) on \(\varGamma (v)\). Now, the permutation group induced by \(G_v\) on \(\varGamma (v)\) is denoted by \(G_v^{\varGamma (v)}\) and we have

When G acts transitively on the set of s-arcs of \(\varGamma \), we say that G is s-arc-transitive. When \(s=0\), we say that G is vertex-transitive and, when \(s=1\), we say that G is arc-transitive. Moreover, when G acts regularly on the set of s-arcs of \(\varGamma \) we emphasize this fact by saying that G is s-arc-regular.

When G acts transitively on \(E\varGamma \), we say that G is edge-transitive. Finally, when G is edge- and vertex-transitive, but not arc-transitive, we say that G is half-arc-transitive. This name comes from the fact that G has two orbits on ordered pairs of adjacent vertices of \(\varGamma \) (a.k.a. arcs), each orbit containing precisely one of the two arcs underlying each edge.

We say that \(\varGamma \) is vertex-, edge- or arc-transitive when \(\mathrm {Aut}(\varGamma )\) is vertex-, edge- or arc-transitive.

Let G be a finite group and let S be a subset of G. The Cayley digraph on G with connection set S is the digraph \(\varGamma :=\mathrm {Cay}(G,S)\) having vertex set G and where \((g,h)\in A\varGamma \) if and only if \(gh^{-1}\in G\). Now, \(\mathrm {Cay}(G,S)\) is a symmetric binary relation if and only if S is inverse closed, that is, \(S=S^{-1}\) where \(S^{-1}:=\{s^{-1}\mid s \in S\}\). Observe that the right regular representation of G acts as a group of automorphisms on \(\mathrm {Cay}(G,S)\).

2.3 Praeger–Xu graphs

In this and in the next section, we introduce the infinite families of graphs appearing in our main theorems. We introduce the 4-valent Praeger-Xu graphs C(r, s) through their directed counterpart defined in [16]. Further details on Praeger–Xu graphs can be found in [2, 4, 17]. We also advertise [5], where the authors have begun a thorough investigation of Praeger–Xu graphs, motivated by the recurrent appearance of these objects in the theory of groups acting on graphs.

Let \(r\ge 3 \) be an integer. Then \(\mathbf {C}(r,1)\) is the lexicographic product of a directed cycle of length r with the edgeless graph on 2 vertices. In other words, \(V\mathbf {C}(r,1)={\mathbb {Z}}_r\times {\mathbb {Z}}_2\), and the two arcs starting in (x, i) end in \((x+1,0)\) and in \((x+1,1)\). For any \(2\le s\le r-1\), \(V\mathbf {C}(r,s)\) is defined as the set of all \((s-1)\)-arcs of \(\mathbf {C}(r,1)\), and \((v_0,v_1,\dots ,v_{s-1})\in V\mathbf {C}(r,s)\) is the beginning point of the two arcs ending in \((v_1, v_2,\dots ,v_{s-1},u)\) and in \((v_1, v_2,\dots ,v_{s-1},u')\), where u and \(u'\) are the two vertices of \(\mathbf {C}(r,1)\) that prolong the \((s-1)\)-arc \((v_1, v_2,\dots ,v_{s-1})\). The Praeger–Xu graph C(r, s) is then defined as the non-oriented underlying graph of \(\mathbf {C}(r,s)\). It can be verified that C(r, s) is a connected 4-valent graph with \(r2^s\) vertices and \(r2^{s+1}\) edges.

We describe the automorphisms of C(r, s). Some automorphism of C(r, s) arises from the action of \(\mathrm {Aut}(C(r,1))\) on the set of s-arcs of C(r, 1). Let \(i\in {\mathbb {Z}}_r\) and let \(\tau _i\) be the transposition on \(V\mathbf {C}(r,1)\) swapping the vertices (i, 0) and (i, 1) and fixing the remaining vertices. Since \(\tau _i\) is an automorphism of \(\mathbf {C}(r,1)\), it is immediate to extended the action of \(\tau _i\) to C(r, 1) and to C(r, s). We define the group

and throughout this paper the symbol K will always refer to this group for some C(r, s). Focusing on the cyclic nature of the Praeger-Xu graphs, it is also natural to define on \(V\mathbf {C}(r,1)\) the permutations \(\rho \) and \(\sigma \) as follows

While \(\rho \) is an automorphism of \(\mathbf {C}(r,1)\), \(\sigma \) is an automorphism of C(r, 1) but not of \(V\mathbf {C}(r,1)\). Moreover, observe that the group \(\langle \rho ,\sigma \rangle \) normalizes K. Define

and, as for K, the symbols H and \(H^+\) will always refer to these groups. Clearly \(H\cong C_2 \wr D_r\) is a group of automorphisms of C(r, s) and \(H^+\cong C_2 \wr C_r\) is a group of automorphisms of \(\mathbf {C}(r,s)\). Moreover, H acts vertex- and edge-transitively on C(r, s) (and so does \(H^+\) on \(\mathbf {C}(r,s)\)), but not 2-arc-transitively.

Lemma 2

Using the notation above, \(\mathrm {Aut}( \mathbf {C}(r,s)) = H^+\) and, if \(r\ne 4\), \(\mathrm {Aut}(C(r,s))=H\). Moreover,

Proof

It follows from [16, Theorem 2.8] and [17, Theorem 2.13] when \(p=2\). \(\square \)

The Praeger–Xu graphs also admit the following algebraic characterization.

Lemma 3

Let \(\varGamma \) be a finite connected 4-valent graph and let G be a vertex- and edge-transitive group of automorphisms of \(\varGamma \). If G has an abelian normal subgroup which is not semiregular on \(V\varGamma \), then \(\varGamma \) is isomorphic to a Praeger–Xu graph C(r, s), for some integers r and s.

Proof

It follows by [16, Theorem 2.9] and [17, Theorem 1] upon setting \(p=2\). \(\square \)

2.4 Split Praeger–Xu graphs

For our purposes, the split Praeger–Xu graphs are obtained from the Praeger–Xu graphs via the splitting operation which was introduced in [12, Construction 9], and which we will comment upon in Sect. 5.

Here we give an explicit description of SC(r, s). Split any vertex of \(\mathbf {C}(r,s)\) into two copies, say \(v_+\) and \(v_-\). For any arc of \(\mathbf {C}(r,s)\) of the form (v, u), let \(v_+\) be adjacent to \(v_-\) and \(u_-\). From the complementary perspective, the neighbourhood of \(v_-\) is made up of \(v_+\) plus the two vertices \(w_+\) such that (w, v) is an arc of \(\mathbf {C}(r,s)\).

3.1 Graph-theoretical considerations

In this section, we develop our tool box that extends outside the scope of proving our main theorems.

Lemma 4

Let \(\varGamma \) be a connected k-valent graph, with \(k\ge 3\), and let G be an s-arc-transitive group of automorphisms of \(\varGamma \). Then \(2s\le g(\varGamma ) +2\). In particular, the girth of \(\varGamma \) is greater than s.

Proof

The first part of the statement is [1, Proposition 17.2]. The second one is an immediate computation if \(s\ge 2\), and it follows from \(g(\varGamma )\ge 3\) if \(s=1\). \(\square \)

Lemma 5

Let \(\varGamma \) be a finite connected graph and let \(v\in V\varGamma \) be a vertex. For each \(w\in \varGamma (v)\), suppose there exists \(t_w\) automorphism of \(\varGamma \) such that \(v^{t_w}=w\). Then \(T:=\langle t_w\mid w\in \varGamma (v)\rangle \) is vertex-transitive on \(\varGamma \).

Proof

Let \(u\in V\varGamma \). As \(\varGamma \) is connected, we prove the existence of \(t_u\in T\) with \(v^{t_u}=u\) arguing by induction on the minimal distance \(d:=d(v,u)\) from v to u in \(\varGamma \). When \(d=0\), that is, \(v=u\), we may take \(t_u\) to be the identity of T. Suppose then \(d>0\). Let \(v_0,\ldots ,v_d\) be a path of distance d from \(v=v_0\) to \(u=v_d\) in \(\varGamma .\) Now, \(d(v,v_{d-1})=d-1\) and hence, by induction, there exists \(t\in T\) with \(v^{t}=v_{d-1}\). Set \(u':=u^{t^{-1}}\). As \(u=v_d\in \varGamma (v_{d-1})\), we have

By hypothesis, \(t_{u'}\in T\) and \(v^{t_{u'}}=u'\). Therefore, \(v^{t_{u'}t}=u'^{t}=u\) and we may take \(t_u:=t_{u'}t\). \(\square \)

Lemma 6

[3, Lemma 3.3.3] Let \(\varGamma \) be a finite connected vertex-transitive graph of valency k. Then \(\varGamma \) is k-edge-connected, i.e. \(\varGamma \) remains connected upon eliminating any m edges, with \(m\le k-1\).

A general result on the fixed-point ratio of Cayley graphs can be proven regardless of the valency.

Lemma 7

Let G be a finite group, let S be an inverse closed non-empty subset of G, let \(\varGamma :=\mathrm {Cay}(G,S)\) and let \(g\in G\setminus \{1\}\). If \(\mathrm {fpr}(E\varGamma ,g)\ne 0\), then \(g^2=1\) and

where \(g^G:=\{hgh^{-1}\mid h\in G\}\) is the conjugacy class of g in G. In particular, \(\mathrm {fpr}(E\varGamma ,g)\le 1/|S|\) and the equality is attained if and only if \(g^G\subseteq S\).

Proof

Suppose \(\mathrm {fpr}(E\varGamma ,g)\ne 0\). We let \(\mathbf{C}_G(g)\) denote the centralizer of g in G.

For each \(s\in S\), let \(E_s:=\{\{x,sx\}\mid x\in G\}\). Observe that \(E_s\) is a complete matching of \(\varGamma \) and that \(\{E_s\mid s\in S\}\) is a partition of the edge set \(E\varGamma \).

Let \(s\in S\). Suppose \(E_s\cap \mathrm {Fix}(E\varGamma ,g)\ne \emptyset \) and fix \(\{{\bar{x}},s{\bar{x}}\}\in E_s\cap \mathrm {Fix}(E\varGamma ,g)\). As g fixes the edge \(\{{\bar{x}},s{\bar{x}}\}\), we have \({\bar{x}}g=s{\bar{x}}\) and \(s{\bar{x}}g={\bar{x}}\). We deduce \(g^2=1\) and \(s={\bar{x}}g{\bar{x}}^{-1}\). In other words, g has order 2 and g has a conjugate in S. Now, for every \(\{x,sx\}\in E_s\), with a similar computation, we obtain that \(\{x,sx\}\in \mathrm {Fix}(E\varGamma ,g)\) if and only if \(s=xgx^{-1}\). Thus \({\bar{x}}g{\bar{x}}^{-1}=xgx^{-1}\) and \(x\in {\bar{x}}\mathbf{C}_G(g)\). In particular, \(E_s\cap \mathrm {Fix}(E\varGamma ,g)=\{\{{\bar{x}}h,s{\bar{x}}h\}\mid h\in \mathbf{C}_G(x)\}\) and hence

The previous paragraph has established that g has order 2. Moreover, for each \(s\in S\), \(E_s\cap \mathrm {Fix}(E\varGamma ,g)\ne \emptyset \) if and only if \(s\in g^G\). Furthermore, in the case that \(s\in g^G\), the cardinality of \(E_s\cap \mathrm {Fix}(E\varGamma ,g)\) does not depend on s and equals \(|\mathbf{C}_G(g)|/2\). Therefore,

Since \(|g^G\cap S|\le |g^G|\), we have \(\mathrm {fpr}(E\varGamma ,S)\le 1/|S|\). Moreover, the equality is attained if and only if \(g^G\cap S=g^G\), that is, \(g^G\subseteq S\). \(\square \)

The next lemma studies the nature of fixed edges in a Praeger–Xu graph.

Lemma 8

Let \(\varGamma =C(r,s)\) be a Praeger–Xu graph and let \(g\in \mathrm {Aut}(\varGamma )\) with \(g\ne 1\) and with \(\mathrm {fpr}(E\varGamma , g)> 1/3\). Then \(3s < 2r-3\) and, either \(g\in K\) or \((r,s)=(4,1)\). In particular, g fixes an edge if and only if g fixes both of its ends. (The group K is defined in Sect. 2.3.)

Proof

The lexicographic product \(C(4,1)\cong K_{4,4}\) admits automorphisms h fixing 8 edges and hence \(\mathrm {fpr}(E\varGamma ,h)=8/16=1/2>1/3\). (The non-identity elements h in \(\mathrm {Aut}(C(4,1))\) with \(\mathrm {fpr}(E\varGamma ,h)>1/3\) are not necessarily in K, but they fix an edge if and only if they fix both of its ends.) Similarly, it can be verified that, for every \(h\in \mathrm {Aut}(C(4,2))\) with \(h\ne 1\), we have \(\mathrm {fpr}(E\varGamma ,h)\le 8/32=1/4\). Furthermore, for every \(h\in \mathrm {Aut}(C(4,3))\) with \(h\ne 1\), we have \(\mathrm {fpr}(E\varGamma , h)=8/64=1/8\). In particular, when \(r=4\), the result follows from these computations.

Suppose \(r\ne 4\). By Lemma 2, \(\mathrm {Aut}(\varGamma )=H=K\langle \rho , \sigma \rangle \). In particular,

Denote by \(\varDelta _x\) the set of \((s-1)\)-arcs in \(\mathbf {C}(r,1)\) starting at (x, 0) or at (x, 1). From the definition of the vertex set of C(r, s), we have \(\varDelta _x\subseteq VC(r,s)\), \(|\varDelta _x|=2^s\) and

We claim that the subgraph induced by \(\varGamma \) on \(\varDelta _x\cup \varDelta _{x+1}\) is the disjoint union of cycles of length 4. In fact, consider the \((s-1)\)-arcs in \(\varDelta _x\) parameterized as

for some \(y_i \in {\mathbb {Z}}_2\). In \(\varGamma \), they are both adjacent to

Since the induced subgraph is 2-valent, these elements form a cycle of length 4, which is a connected component of the induced graph. Moreover, \(\varDelta _x\) is a K-orbit, and, for any \(x\in {\mathbb {Z}}_r\),

We start by proving that \(g\in K\).

Suppose \(\varepsilon =0\). Let \(\{a,b\}\in \mathrm {Fix}(E\varGamma ,g)\). Replacing a with b if necessary, we may suppose that \(a\in \varDelta _x\) and \(b\in \varDelta _{x+1}\), for some \(x\in {\mathbb {Z}}_r\). If \(a^g=a\) and \(b^g=b\), we have \(\varDelta _x^g=\varDelta _{x}\) and \(\varDelta _{x+1}^g=\varDelta _{x+1}\). Now, (3.1) yields \(x+i=x\) and \((x+1)+i=x+1\), that is, \(i=0\). Therefore \(g\in K\). Similarly, if \(a^g=b\) and \(b^g=a\), we have \(\varDelta _x^g=\varDelta _{x+1}\) and \(\varDelta _{x+1}^g=\varDelta _{x}\). Now, (3.1) yields \(x+i=x+1\) and \((x+1)+i=x\), that is, \(2=0\). However, this implies \(r=2\), which is a contradiction because \(r\ge 3\).

Suppose \(\varepsilon =1\). Since \(\langle \rho ,\sigma \rangle \) is a dihedral group of order 2r, replacing g by a suitable conjugate if necessary, we may suppose that either r is odd and \(i=0\), or r is even and \(i\in \{0,1\}\).

Assume \(i=0\). Let \(\{a,b\}\in \mathrm {Fix}(E\varGamma ,g)\). As above, replacing a with b if necessary, we may suppose that \(a\in \varDelta _x\) and \(b\in \varDelta _{x+1}\), for some \(x\in {\mathbb {Z}}_r\). If \(a^g=a\) and \(b^g=b\), we have \(\varDelta _x^g=\varDelta _{x}\) and \(\varDelta _{x+1}^g=\varDelta _{x+1}\). Now, (3.1) yields \(-x-s+1=x\) and \(-(x+1)-s+1=x+1\), that is, \(2=0\). However, this gives rise to the contradiction \(r=2\). Similarly, if \(a^g=b\) and \(b^g=a\), we have \(\varDelta _x^g=\varDelta _{x+1}\) and \(\varDelta _{x+1}^g=\varDelta _{x}\). Now, (3.1) yields \(-x-s+1=x+1\) and \(-(x+1)-s+1=x\), that is, \(2x+s=0\). When r is odd, the equation \(2x+s=0\) has only one solution in \({\mathbb {Z}}_r\) and, when r is even, the equation \(2x+s=0\) has either zero or two solutions in \({\mathbb {Z}}_r\) depending on whether s is odd or even. Recalling that the subgraph induced by \(\varGamma \) on \(\varDelta _x\cup \varDelta _{x+1}\) is a disjoint union of cycles of length 4, and noticing that g fixes at most 2 edges of any cycle, we obtain that

In both cases, we have \(\mathrm {fpr}(E\varGamma ,g)\le 1/4\), which is a contradiction.

Assume \(i=1\). Observe that this implies that r is even. Here the analysis is entirely similar. Let \(\{a,b\}\in \mathrm {Fix}(E\varGamma ,g)\). As above, replacing a with b if necessary, we may suppose that \(a\in \varDelta _x\) and \(b\in \varDelta _{x+1}\), for some \(x\in {\mathbb {Z}}_r\). If \(a^g=a\) and \(b^g=b\), we have \(\varDelta _x^g=\varDelta _{x}\) and \(\varDelta _{x+1}^g=\varDelta _{x+1}\). Now, (3.1) yields \(-(x+1)-s+1=x\) and \(-(x+2)-s+1=x\), that is, \(2=0\). However, this gives rise to the usual contradiction \(r=2\). Similarly, if \(a^g=b\) and \(b^g=a\), we have \(\varDelta _x^g=\varDelta _{x+1}\) and \(\varDelta _{x+1}^g=\varDelta _{x}\). Now, (3.1) yields \(-(x+1)-s+1=x+1\) and \(-(x+2)-s+1=x\), that is, \(2x+s+1=0\). As r is even, the equation \(2x+s+1\) has either zero or two solutions in \({\mathbb {Z}}_r\) depending on whether s is even or odd. Recalling that the subgraph induced by \(\varGamma \) on \(\varDelta _x\cup \varDelta _{x+1}\) is a disjoint union of cycles of length 4, and noticing that g fixes at most 2 edges of any cycle, we obtain that

Thus, we have \(\mathrm {fpr}(E\varGamma ,g)\le 1/4\), which is a contradiction.

Since \(g\in K\), if g fixes the edge \(\{a,b\}\in E\varGamma \), then g fixes both end-vertices a and b. It remains to show that \(3s<2r-3\). Notice that \(\tau _i\) moves precisely those \((s-1)\)-arcs of \(\mathbf {C}(r,1)\) that pass through one of the vertices (i, 0) or (i, 1). Therefore, \(\tau _i\), as an automorphism of C(r, s), fixes all but \(s2^s\) vertices, thus it fixes all but those \((s+1)2^{s+1}\) edges which are incident with such vertices. Since any element in K is obtained as a product of some \(\tau _i\), such an element fixes at most as many edges as a single \(\tau _i\). Hence

\(\square \)

Lemma 9

Let \(\varGamma =C(r,s)\) be a Praeger–Xu graph, let G be a vertex- and edge-transitive group of automorphism of \(\varGamma \) containing a non-identity element g fixing more than 1/3 of the edges and with G not 2-arc-transitive. Then G is \(\mathrm {Aut}(\varGamma )\)-conjugate to a subgroup of H as defined in Sect. 2.3.

Proof

By Lemma 8, \(3s < 2r-3\). If \(r\ne 4\), then by Lemma 2 we have \(G\le \mathrm {Aut}(\varGamma )=H\). When \(r=4\), then inequality \(3s<2r-3\) implies \(s=1\). Now, the veracity of this lemma can be verified with a computation in \(\mathrm {Aut}(C(4,1))=\mathrm {Aut}(K_{4,4})=S_4\wr S_2\). \(\square \)

Lemma 10

[11, Lemma 1.14] Let \(\varGamma \) be a finite connected 4-valent graph, let G be a vertex- and edge-transitive group of automorphisms of \(\varGamma \), and let N be a minimal normal subgroup of G. If N is a 2-group and \(\varGamma /N\) is a cycle of length at least 3, then \(\varGamma \) is isomorphic to a Praeger–Xu graph C(r, s) for some integers r and s.

In this section we prove Theorem 1. Our proof is divided into two cases, depending on whether \(\varGamma \) admits a group of automorphisms acting 2-arc-transitively or not.

4.1 Proof of Theorem 1 when \(\varGamma \) is 2-arc-transitive

The following lemma involves four graphs not yet considered in this paper, so it is worth to spend some ink here to describe them.

• The complete graph \(K_5\) is the only sporadic example arising in Theorem 1, its automorphism group is \(S_5\) and each transposition in \(S_5\) fixes 4 edges out of 10.

• The graph \(K_{5,5}-5K_2\) is obtained deleting a complete matching from the complete bipartite graph \(K_{5,5}\), its automorphism group is \(S_5\times C_2\) and every non-identity automorphism fixes at most 6 edges out of 20.

• The hypercube \(Q_4\) is the Cayley graph

  $$\begin{aligned} Q_4 := \mathrm {Cay} ({\mathbb {Z}}_2 ^4, \{(1,0,0,0),(0,1,0,0), (0,0,1,0), (0,0,0,1)\}). \end{aligned}$$

  A non-identity automorphism of \(Q_4\) fixes at most 8 edges out of 32.

• The graph BCH is the bipartite complement of the Heawood graph. The vertices of BCH can be identified with the 7 points and the 7 lines of the Fano plane. The incidence in the graph is given by the anti-flags in the plane, i.e. the point p is adjacent to the line L if, and only if, \(p\notin L\). The automorphism group of BCH is isomorphic to \(\mathrm {SL}_3(2).2\). A non-identity automorphism of BCH fixes at most 4 edges out of 28.

Lemma 11

Let \(\varGamma \) be a finite connected 4-valent 2-arc-transitive graph of girth at most 4, i.e. \(g(\varGamma )\in \{3,4\}\). Then one of the following holds:

1. 1.

   \(g(\varGamma )=3\) and \(\varGamma \) is isomorphic to the complete graph \(K_5\);

2. 2.

   \(g(\varGamma )=4\) and \(\varGamma \) is isomorphic to \(K_{4,4}\cong C(4,1)\);

3. 3.

   \(g(\varGamma )=4\) and \(\varGamma \) is isomorphic to \(K_{5,5}-5K_2\), \(Q_4\) or BCH.

Proof

Let v be a vertex, let \(\varGamma (v)=\{w_1,w_2,w_3,w_4\}\) be its neighbourhood and let \(G:=\mathrm {Aut}(\varGamma )\).

First, assume \(g(\varGamma )=3\). Without loss of generality, suppose \(w_1\) and \(w_2\) are adjacent. Since G is 2-arc-transitive, \(G_v\) is 2-transitive on \(\varGamma (v)\). Hence \(w_i\) is adjacent to \(w_j\) for any \(i\ne j\). Thus \(\varGamma \cong K_5\) and part (1) holds.

Now, suppose \(g(\varGamma )=4\). We need to recall the classification arising from [15, Theorem 3.3]. If \(\varDelta \) is a 4-valent edge-transitive graph, then one of the following holds

1. (i)

   each vertex in \(\varDelta \) is contained in exactly one 4-cycle,

2. (ii)

   there exist two distinct vertices \(v_1,v_2\) with \(\varDelta (v_1)=\varDelta (v_2)\),

3. (iii)

   \(\varDelta \) is isomorphic to \(K_{5,5}-5K_2\), \(Q_4\) or BCH.

We consider these three possibilities for \(\varGamma \) in turn. Up to a permutation of the indices, there exists \(u\in \varGamma (w_1)\cap \varGamma (w_2)\) such that \((v,w_1,u,w_2)\) is a 4-cycle. Since \(G_v^{\varGamma (v)}\) is 2-transitive, there exists \(g\in G_v\) with \((w_1,w_2)^g=(w_3,w_4)\). Therefore, \((v,w_1,u,w_2)^g=(v,w_3,u^g,w_4)\) is a 4-cycle different from \((v,w_1,u,w_2)\). Thus part (i) is excluded. If \(\varGamma \) satisfies (ii), then [15, Lemma 4.3] gives that \(\varGamma \) is isomorphic to C(r, 1) for some integer r. From Lemma 2, C(r, 1) is 2-arc-transitive only when \(r=4\); therefore we obtain part (2). If \(\varGamma \) satisfies part (iii), then we obtain the examples in part (3). \(\square \)

Definition 1

Let \(\varGamma \) be a finite connected 4-valent graph and let g be an automorphism of \(\varGamma \). We partition \(E\varGamma \) with respect to the action of g.

• We let \(A(\varGamma ,g)\) be the set of edges which are pointwise fixed by g, that is, \(\{a,b\}\in A(\varGamma ,g)\) if and only if \(\{a,b\}\in E\varGamma \), \(a^g=a\) and \(b^g=b\);

• we let \(F(\varGamma ,g):=\mathrm {Fix}(E\varGamma ,g)\setminus A(\varGamma ,g)\), that is, \(\{a,b\}\in F(\varGamma ,g)\) if and only if \(\{a,b\}\in E\varGamma \), \(a^g=b\) and \(b^g=a\);

• we let \(N(\varGamma ,g):=E\varGamma \setminus \mathrm {Fix}(E\varGamma ,g)\).

We let \(\varGamma [g]\) denote the subgraph of \(\varGamma \) induced by \(\varGamma \) on the vertices which are incident with edges in \(A(\varGamma ,g)\). The edge-set of \(\varGamma [g]\) is \(A(\varGamma ,g)\) and its vertices are 1-, 2- or 4-valent. Given \(i\in \{1,2,4\}\), we let \(V_i(\varGamma ,g)\) denote the set of vertices of \(\varGamma [g]\) having valency i.

Lemma 12

Let \(\varGamma \) be a finite connected 4-valent graph of girth \(g(\varGamma )\ge 5\) and let g be an automorphism of \(\varGamma \). Then \(2|F(\varGamma ,g)|+4|V_1(\varGamma ,g)|+3|V_2(\varGamma ,g)|+|V_4(\varGamma ,g)|\le |V\varGamma |\).

Proof

We let

Since \(V_1(\varGamma ,g),V_2(\varGamma ,g),V_4(\varGamma ,g),{\mathcal {F}},{\mathcal {N}}\) are pairwise disjoint and since \(|{\mathcal {F}}|=2|F(\varGamma ,g)|\), it suffices to show that \(|{\mathcal {N}}|\ge 3|V_1(\varGamma ,g)|+2|V_2(\varGamma ,g)|\).

We construct an auxiliary graph \(\varDelta \). The vertex set of \(\varDelta \) is \(V_1(\varGamma ,g)\cup V_2(\varGamma ,g)\cup {\mathcal {N}}\) and we declare a vertex \(v\in V_1(\varGamma ,g)\cup V_2(\varGamma ,g)\) adjacent to a vertex \(u\in {\mathcal {N}}\) if \(\{v,u\}\in E\varGamma \). By construction, \(\varDelta \) is bipartite with parts \(V_1(\varGamma ,g)\cup V_2(\varGamma ,g)\) and \({\mathcal {N}}\).

Given \(v\in V_1(\varGamma ,g)\), the automorphism g acts as a 3-cycle on \(\varGamma (v)\). Let \(v_1,v_2,v_3\in \varGamma (v)\) forming the 3-cycle of g. Then \(\{v,v_1\},\{v,v_2\},\{v,v_3\}\in N(\varGamma ,g)\) and hence \(v_1,v_2,v_3\in {\mathcal {N}}\). This shows that each vertex in \(V_1(\varGamma ,g)\) has three neighbours in \({\mathcal {N}}\). Similarly, each vertex in \(V_2(\varGamma ,g)\) has two neighbours in \({\mathcal {N}}\). As \(g(\varGamma )>4\), we have \(g(\varDelta )>4\) and hence \(3|V_1(\varGamma ,g)|+2|V_2(\varGamma ,g)|\le |{\mathcal {N}}|\), because \(\varDelta (v)\cap \varDelta (v')=\emptyset \) for any two distinct vertices \(v,v'\in V_1(\varGamma ,g)\cup V_2(\varGamma ,g)\). \(\square \)

Let B, L and R be groups, and let \(\iota _L: B \rightarrow L\) and \(\iota _R: B\rightarrow R\) be injective homomorphisms of groups. The pair \((\iota _L,\iota _R)\) is said to be an amalgam. When B is a subgroup of both L and R, we can think of \(\iota _L\) and \(\iota _R\) as the inclusion mappings. In this case, the amalgam is determined by the triple (L, B, R) and, in this paper, this is the point of view we take.

Let (L, B, R) be an amalgam, we say that its index is the couple

Moreover, (L, B, R) is said to be faithful if no subgroup of B is normal in L and in R. When the index is precisely (k, 2), for some positive integer k, (L, B, R) is said to be 2-transitive if the action of L on the right cosets of B by right multiplication is 2-transitive.

Observe that, if \(\varGamma \) is a finite connected G-arc-transitive graph of valency k, then for any \(v\in V\varGamma \) and \(w\in \varGamma (v)\), the triplet

is a faithful amalgam of index (k, 2).

Finite faithful 2-transitive amalgams of index (4, 2) have been studied in detail by Potočnik in [9]. We use this work to deduce some properties on \(\mathrm {Fix}(E\varGamma ,g)\).

Lemma 13

Let \(\varGamma \) be a finite connected 4-valent graph, let G be an s-arc-transitive group of automorphisms of \(\varGamma \) with \(s\ge 2\) and let \(g\in G\) fixing pointwise the s-arc \((v_0,\ldots ,v_{s-1})\). If G is not \((s+1)\)-arc-transitive and g fixes pointwise \(\varGamma (v_0)\cup \varGamma (v_{s-1})\), then \(g=1\).

Proof

If G is s-arc-regular, then \(g=1\) because g fixes an s-arc. Using [9], we see that there are 6 amalgams such that G is not s-arc-regular. For each of these remaining amalgams a case-by-case computation shows that the only automorphism leaving the neighbourhood of each end of a given s-arc fixed is the identity map. \(\square \)

Lemma 14

Let \(\varGamma \) be a finite connected 4-valent graph of girth \(g(\varGamma )\ge 5\), let G be a 2-arc-transitive group of automorphisms of \(\varGamma \) such that \(G_v^{[1]}\cap G_w^{[1]}\) is a 3-group, for any two distinct vertices at distance at most 2, and let \(g\in G\setminus \{1\}\). Then \(3|V_4(\varGamma ,g)|\le 3|V_1(\varGamma ,g)|+|V_2(\varGamma ,g)|\).

Proof

Assume that the vertices in \(V_4(\varGamma ,g)\) are at pairwise distance more than 2. Then any two such vertices share no common neighbour. In particular, \(\bigcup _{v\in V_4(\varGamma ,g)} \varGamma (v)\) has cardinality \(4|V_4(\varGamma ,g)|\) and is contained in \(V_1(\varGamma ,g)\cup V_2(\varGamma ,g)\). Therefore, \(4|V_4(\varGamma ,g)|\le |V_1(\varGamma ,g)|+|V_2(\varGamma ,g)|\) and the lemma immediately follows in this case.

Assume that there exist two distinct vertices v and w of \(V_4(\varGamma ,g)\) having distance at most 2. In particular, \(g\in G_v^{[1]}\cap G_w^{[1]}\) and hence g has order a power of 3, because \(G_v^{[1]}\cap G_w^{[1]}\) is a 3-group. Observe that \(V_2(\varGamma ,g)=\emptyset \) because an element of order 3 in a local group cannot fix exactly two elements. Let \(s\ge 2\) such that G is s-arc-transitive, but not \((s+1)\)-arc-transitive.

Suppose \(\varGamma [g]\) is not a forest. Then \(\varGamma [g]\) contains an \(\ell \)-cycle C. As \(V_2(\varGamma ,g)=\emptyset \), the vertices of C are elements of \(V_4(\varGamma ,g)\). From Lemma 4, we have \(g(\varGamma [g])\ge g(\varGamma )\ge s+1\) and hence, from C, we can extract an s-arc whose ends lie in \(V_4(\varGamma ,g)\), contradicting Lemma 13.

Suppose \(\varGamma [g]\) is a forest. Let c be the number of connected components of \(\varGamma [g]\). From Euler’s formula, we have \(|V\varGamma [g]|-|E\varGamma [g]|=c\). Clearly, \(|V\varGamma [g]|=|V_1(\varGamma ,g)|+|V_4(\varGamma ,g)|\). Let \({\mathcal {S}}:=\{(v,w)\in V\varGamma [g]\times V\varGamma [g]\mid \{v,w\}\in E\varGamma [g]\}\). Then

It follows that \(2|V_4(\varGamma ,g)|=|V_1(\varGamma ,g)|-2c<|V_1(\varGamma ,g)|\). \(\square \)

Proof

(Proof of Theorem 1 when \(\varGamma \) is 2-arc-transitive) Let \(\varGamma \) be a finite connected 4-valent 2-arc-transitive graph admitting a non-identity automorphism g with \(\mathrm {fpr}(E\varGamma ,g)>1/3\) and let \(G:=\mathrm {Aut}(\varGamma )\).

If \(g(\varGamma )\le 4\), then the proof follows from Lemma 11 and from the remarks at the beginning of Sect. 4.1. Therefore, for the rest of the proof we suppose that \(g(\varGamma )>4\). Since \(4|V\varGamma |=2|E\varGamma |\), we have

where in the last inequality we have used Lemma 12.

We claim that, for any two distinct vertices \(v,w\in V\varGamma \) at distance at most 2 one of the following holds

1. (i)

   \(G_v^{[1]}\cap G_w^{[1]}\) is a 3-group;

2. (ii)

   the pair \((\varGamma ,G)\) defines the amalgam

   $$\begin{aligned} \left( S_3\times S_4, S_3\times S_3, (S_3\times S_3)\rtimes C_2 \right) , \end{aligned}$$

   moreover, if \(d(v,w)=1\), then \(G_v^{[1]}\cap G_w^{[1]}=1\) and, if \(d(v,w)=2\), then \(G_v^{[1]}\cap G_w^{[1]}\) is isomorphic to \(C_2\).

The claim follows with a case-by-case computation on the finite faithful 2-transitive amalgams of index (4, 2) classified in [9]. We now divide the proof according to (i) and (ii).

Suppose that (i) holds. From Lemma 14, we have \(3|V_4(\varGamma ,g)|\le 3|V_1(\varGamma ,g)|+|V_2(\varGamma ,g)|\). Using this inequality and (4.1), we obtain \(\mathrm {fpr}(E\varGamma ,g)\le 1/4<1/3\), which is a contradiction.

Suppose that (ii) holds. If there exist two distinct vertices v and w in \(V_4(\varGamma ,g)\) with \(d(v,w)=1\), then \(g\in G_v^{[1]}\cap G_w^{[1]}=1\), which is a contradiction. Assume there exist two distinct vertices v and w in \(V_4(\varGamma ,g)\) with \(d(v,w)=2\). Then \(g\in G_v^{[1]}\cap G_w^{[1]}\cong C_2\) and hence g has order 2. This implies \(V_1(\varGamma ,g)=\emptyset \) because an involution in a local group cannot fix only one element. Since the subgraph induced by \(\varGamma [g]\) on \(V_4(\varGamma ,g)\) has no edges and since each vertex in \(V_4(\varGamma ,g)\) has valency 4, we deduce \(4|V_4(\varGamma ,g)|\le |E\varGamma [g]|=|V_2(\varGamma ,g)|+2|V_4(\varGamma ,g)|\). Using this inequality and (4.1), we obtain \(\mathrm {fpr}(E\varGamma ,g)<1/3\), which is a contradiction.

Finally, assume that the vertices in \(V_4(\varGamma ,g)\) are at pairwise distance more than 2. Then any two such vertices share no common neighbour. In particular, \(\bigcup _{v\in V_4(\varGamma ,g)} \varGamma (v)\) has cardinality \(4|V_4(\varGamma ,g)|\) and is contained in \(V_1(\varGamma ,g)\cup V_2(\varGamma ,g)\). Therefore, \(4|V_4(\varGamma ,g)|\le |V_1(\varGamma ,g)|+|V_2(\varGamma ,g)|\). Using this inequality and (4.1), we obtain \(\mathrm {fpr}(E\varGamma ,g)\le 1/4<1/3\), which is a contradiction. \(\square \)

4.2 Proof of Theorem 1 when \(\varGamma \) is not 2-arc-transitive

To conclude the proof of Theorem 1, we argue by induction on \(|V\varGamma |\).

Let \(\varGamma \) be a finite connected vertex- and edge-transitive 4-valent graph admitting a non-identity automorphism g fixing more than 1/3 of the edges and with \(G:=\mathrm {Aut}(\varGamma )\) not 2-arc-transitive. If \(\varGamma \) is isomorphic to a Praeger–Xu graph, then part (2) of Theorem 1 holds. Therefore, for the rest of the argument, we suppose that \(\varGamma \) is not isomorphic to C(r, s), for any choice of r and s with \(r\ge 3\) and \(1\le s\le r-1\).

Let \(v\in V\varGamma \). Since G is not 2-arc-transitive, \(G_v^{\varGamma (v)}\) is not 2-transitive on \(\varGamma (v)\). Since G is vertex- and edge-transitive, we obtain that either \(G_v^{\varGamma (v)}\) is transitive or \(G_v^{\varGamma (v)}\) has two orbits of cardinality 2. In both cases, we deduce that \(G_v^{\varGamma (v)}\) is a 2-group. As \(\varGamma \) is connected, it follows that \(G_v\) is a 2-group.

If G has no non-identity normal subgroups having cardinality a power of 2, Theorem 3 (applied to the faithful and transitive action of G on \(E\varGamma \)) contradicts \(\mathrm {fpr}(E\varGamma ,g)>1/3\). Thus, G has a minimal normal 2-subgroup N.

As \(\varGamma \) is not isomorphic to a Praeger–Xu graph, Lemma 3 yields that N acts semi-regularly on \(V\varGamma \). Consider the quotient graph \(\varGamma /N\) and observe that, as G is vertex- and edge-transitive, \(\varGamma /N\) has valency 0, 1, 2 or 4.

If \(\varGamma /N\) has valency 0, then N is transitive on \(V\varGamma \). Thus N is vertex-regular on \(\varGamma \). As \(\varGamma \) is connected of valency 4, N is generated by at most 4 elements and hence \(|V\varGamma |=|N|\) divides \(2^4\). If \(\varGamma /N\) has valency 1, then N has two orbits on \(V\varGamma \). Moreover, [11, Lemma 1.15] implies that \(|V\varGamma |=2|N|\) divides 128. In both cases, the statement can be checked computationally by inspecting the candidate graphs from the census of all 4-valent vertex- and edge-transitive graphs of small order, see [12, 13]. If \(\varGamma /N\) has valency 2, then we contradict Lemma 10. Therefore, for the rest of the proof, we may suppose that \(\varGamma /N\) has valency 4.

Let K be the kernel of the action of G on \(V\varGamma /N\). Since the quotient graph is not degenerate, \(K_v=1\). Thus \(K=K_vN=N\). In particular, G/N acts faithfully as a group of automorphisms on \(\varGamma /N\). Moreover, G/N acts vertex- and edge-transitively on \(\varGamma /N\), but not 2-arc-transitively. Observe that \(g\notin N\), because the elements in N fix no edge of \(\varGamma \). Thus Ng is not the identity automorphism of \(\varGamma /N\) and, by Lemma 1, we have \(\mathrm {fpr}(E\varGamma /N,Ng)>1/3\). Our inductive hypothesis on \(|V\varGamma |\) implies that \(\varGamma /N\) is isomorphic to \(K_5\) or to a Praeger–Xu graph C(r, s) with \(3s < 2r-3\).

Assume \(\varGamma /N\cong K_5\). Now, \(\mathrm {Aut}(K_5)=S_5\) and \(S_5\) contains a unique conjugacy class of subgroups which are vertex- and edge-transitive, but not 2-transitive (namely, the Frobenius groups of order 20). Therefore, G/N is isomorphic to a Frobenius group of order 20. In particular, as N is an irreducible module for a Frobenius group of order 20, we get \(|N|\le 16\). We deduce \(|V\varGamma |\le 10\cdot 16=160\) and, as above, the statement can be checked computationally by inspecting the census of all 4-valent vertex- and edge-transitive graphs of small order.

Assume \(\varGamma /N\cong C(r,s)\), for some r and s with \(3s<2r-3\). From Lemma 9, G/N is \(\mathrm {Aut}(\varGamma /N)\)-conjugate to a subgroup of H as defined in Sect. 2.3. Without loss of generality, we can identify G/N with such a subgroup, so that \(G/N\le H\). Now, we first deal with the exceptional case \((r,s)=(4,1)\). As G/N is a 2-group and N is a minimal normal subgroup of G, we deduce \(|N|=2\) and hence \(|V\varGamma |=|V\varGamma /N||N|=8\cdot 2=16\). Now, the proof follows inspecting the vertex- and edge-transitive graphs of order 16. Therefore, for the rest of the argument, we suppose \((r,s)\ne (4,1)\). Now, Lemma 8 implies \(Ng\in K\le H^+\). Denote by X the group \(G/N\cap H^+\). This group is a half-arc-transitive group of automorphisms of \(\varGamma /N\) and, since \(|H:H^+|=2\), we have \(|G/N:X|\le 2\). Denote by \(G^+\) the preimage of X with respect to the quotient projection \(G\rightarrow G/N\), so that \(G^+/N\cong X\). Now, \(G^+\) acts half-arc-transitively on \(\varGamma \) and, from \(Ng\in X\), we see that \(g\in G^+\). In particular, replacing G with \(G^+\) if necessary, in the rest of our argument we may suppose that \(G=G^+\), that is, \(G/N\le H^+\).

By Lemma 8, all the edges fixed in \(\varGamma /N\) by Ng are fixed as arcs. Therefore, all the edges fixed in \(\varGamma \) by g are fixed as arcs.

Considering the graph induced by \(\varGamma \) on \(\mathrm {Fix}(V\varGamma ,g)\), we deduce \( 2|\mathrm {Fix}(E\varGamma ,g)| \le 4|\mathrm {Fix}(V\varGamma ,g)|\). In particular, if \(|\mathrm {Fix}(V\varGamma ,g)|\le |V\varGamma |/3\), then

which is a contradiction. Therefore \(\mathrm {fpr}(V\varGamma , g)>1/3\). Now, the hypothesis of Lemma 2.3 in [11] are satisfied. Therefore, [11, Lemma 2.3] implies that \(\varGamma \) is a Praeger–Xu graph, which is our final contradiction.

We now turn our attention to finite connected 3-valent vertex-transitive graphs. We divide the proof of Theorem 2 in three cases, which we now describe. Let \(\varGamma \) be a finite connected 3-valent vertex-transitive graph, let \(G:=\mathrm {Aut}(\varGamma )\) and let \(v\in V\varGamma \). The local group \(G_v^{\varGamma (v)}\) is a subgroup of the symmetric group of degree 3 and we divide the proof of Theorem 2 depending on the structure of \(G_v^{\varGamma (v)}\). When \(G_v^{\varGamma (v)}=1\), the connectivity of \(\varGamma \) implies \(G_v=1\) and hence G acts regularly on \(V\varGamma \). In this case an observation of Sabidussi [18] yields that \(\varGamma \) is Cayley graph over G. We deal with this case in Sect. 5.1. When \(G_v^{\varGamma (v)}\) is cyclic of order 2, [12] has established a fundamental relation between \(\varGamma \) and a certain finite connected 4-valent graph; in Sect. 5.2, we exploit this relation and Theorem 1 to deal with this case. When \(G_v^{\varGamma (v)}\) is transitive, \(\varGamma \) is arc-transitive and we use the amazing result of Tutte concerning the structure of \(G_v\) to deal with this case in Sect. 5.3.

5.1 Proof of Theorem 2 when the local group is the identity

Let \(\varGamma \) be a finite connected 3-valent vertex-transitive graph, let \(v\in V\varGamma \), let \(G:=\mathrm {Aut}(\varGamma )\) and let \(g\in G\setminus \{1\}\). Assume that \(G_v^{\varGamma (v)}=1\). Lemma 7 yields \(\mathrm {fpr}(E\varGamma ,g)\le 1/3\) and hence Theorem 2 holds in this case.

5.2 Proof of Theorem 2 when the local group is cyclic of order 2

In our proof of this case, we need to refer to two families of 3-valent Cayley graphs. Given \(n\in {\mathbb {N}}\) with \(n\ge 3\), the prism \(\mathrm {Pr}_n\) is the Cayley graph

Similarly, given \(n\in {\mathbb {N}}\) with \(n\ge 2\), the Möbius ladder \(\mathrm {Mb}_n\) is the Cayley graph

For these two classes of graphs the proof of Theorem 2 follows with a computation. When \(n\ne 4\), the automorphism group of \(\mathrm {Pr}_n\) is isomorphic to \(D_n\times C_2\) and, for each \(x\in \mathrm {Aut}(\mathrm {Pr}_n)\) with \(x\ne 1\), it can be verified that \(\mathrm {fpr}(E\mathrm {Pr}_n,x)\le 1/3\), see also Lemma 7. The case \(n=4\) is exceptional, because \(\mathrm {Pr}_4\cong Q_4\) is 2-arc-transitive and hence \(\mathrm {Pr}_4\) is of no concern to us here. Similarly, when \(n\notin \{2,3\}\), the automorphism group of \(\mathrm {Mb}_n\) is isomorphic to \(D_{2n}\) and, for each \(x\in \mathrm {Aut}(\mathrm {Mb}_n)\) with \(x\ne 1\), it can be verified that \(\mathrm {fpr}(E\mathrm {Mb},x)\le 1/3\), again see also Lemma 7. The cases \(n\in \{2,3\}\) are exceptional, because \(\mathrm {Mb}_2\cong K_4\) and \(\mathrm {Mb}_3\) are 2-arc-transitive and hence are of no concern to us here.

Now, let \(\varGamma \) be a finite connected 3-valent vertex-transitive graph not isomorphic to \(\mathrm {Pr}_n\) and not isomorphic to \(\mathrm {Mb}_n\), let \(v\in V\varGamma \), let \(G:=\mathrm {Aut}(\varGamma )\) and let \(g\in G\setminus \{1\}\) with \(\mathrm {fpr}(E\varGamma ,g)>1/3\). Assume that \(G_v^{\varGamma (v)}\) is cyclic of order 2.

For a vertex \(w \in V\varGamma \), let \(w'\) be the neighbour of w such that \(\{w'\}\) is the orbit of \(G_w\) of length 1. Then clearly \((w')' = w\) and \(G_w = G_{w'}\). Hence, the set \({\mathcal {M}} := \{\{w, w' \} \mid w \in V\varGamma \}\) is a complete matching of \(\varGamma \), while edges outside \({\mathcal {M}}\) form a 2-factor \({\mathcal {F}}\). The group G in its action on \(E\varGamma \) fixes setwise both \({\mathcal {F}}\) and \({\mathcal {M}}\) and acts transitively on the arcs of each of these two sets. Let \({\tilde{\varGamma }}\) be the graph with vertex-set \({\mathcal {M}}\) and two vertices \(e_1 , e_2 \in {\mathcal {M}}\) adjacent if and only if they are (as edges of \(\varGamma \)) at distance 1 in \(\varGamma \). The graph \({\tilde{\varGamma }}\) is then called the merge of \(\varGamma \). We may also think of \(\varGamma \) as being obtained by contracting all the edges in \({\mathcal {M}}\). The group G acts as an arc-transitive group of automorphisms on \({\tilde{\varGamma }}\). Moreover, the connected components of the 2-factor \({\mathcal {F}}\) gives rise to a decomposition \({\mathcal {C}}\) of \(E{\tilde{\varGamma }}\) into cycles.

Since we are assuming that \(\varGamma \) is neither a prism nor a Möbius ladder, [12, Lemma 9 and Theorem 10] implies that \({\tilde{\varGamma }}\) is 4-valent. Moreover, the action of G on \({\tilde{\varGamma }}\) is faithful, arc-transitive but not 2-arc-transitive.

Noticing that \(|E{\tilde{\varGamma }}|=2|V{\tilde{\varGamma }}|\), we can link the fixed-point ratios of \(\varGamma \) and its 4-valent merge \({\tilde{\varGamma }}\) as follows

Observe that either \(\mathrm {fpr}(V{\tilde{\varGamma }},g)> 1/3\) or \(\mathrm {fpr}(E{\tilde{\varGamma }},g)> 1/3\), otherwise

Using [11, Theorem 1.1] when \(\mathrm {fpr}(V{\tilde{\varGamma }},g)> 1/3\), and using Theorem 1 when \(\mathrm {fpr}(E{\tilde{\varGamma }},g)> 1/3\), it follows that either \({\tilde{\varGamma }}\cong C(r,s)\), with \(3s<2r\), or \(|V{\tilde{\varGamma }}|\le 70\). The latter case yields \(|V\varGamma |\le 140\) and the veracity of Theorem 2 follows with an inspection on the connected 3-valent graphs having at most 140 vertices.

Therefore, we can suppose \({\tilde{\varGamma }}\cong C(r,s)\). In view of [12, Theorem 12], the graph \(\varGamma \) can be uniquely reconstructed from \({\tilde{\varGamma }}\) and the decomposition \({\mathcal {C}}\) of \(E{\tilde{\varGamma }}\) arising from the 2-factor \({\mathcal {F}}\) via the splitting operation defined in Sect. 2.4. Hence, \(\varGamma \cong S(C(r,s))\). Finally, observe that

(The \(\tau _i\)’s are defined in Sect. 2.3.) Hence, a direct computation leads to \(3s<2r-2\).

5.3 Proof of Theorem 2 when the local group is transitive

Let \(\varGamma \) be a finite connected 3-valent vertex-transitive graph, let \(v\in V\varGamma \), let \(G:=\mathrm {Aut}(\varGamma )\) and let \(g\in G\setminus \{1\}\) with \(\mathrm {fpr}(E\varGamma ,g)>1/3\). Assume that \(G_v^{\varGamma (v)}\) is transitive. Let \(s\ge 1\) such that G is s-arc-transitive and G is not \((s+1)\)-arc-transitive. Tutte’s theorem [19] implies that G is s-arc-regular.

Similarly to Definition 1, we partition \(E\varGamma \) with respect to the action of g.

• We let \(A(\varGamma ,g)\) be the set of edges which are pointwise fixed by g, that is, \(\{a,b\}\in A(\varGamma ,g)\) if and only if \(\{a,b\}\in E\varGamma \), \(a^g=a\) and \(b^g=b\);

• we let \(F(\varGamma ,g):=\mathrm {Fix}(E\varGamma ,g)\setminus A(\varGamma ,g)\), that is, \(\{a,b\}\in F(\varGamma ,g)\) if and only if \(\{a,b\}\in E\varGamma \), \(a^g=b\) and \(b^g=a\);

• we let \(N(\varGamma ,g):=E\varGamma \setminus \mathrm {Fix}(E\varGamma ,g)\).

We let \(\varGamma [g]\) denote the subgraph of \(\varGamma \) induced by \(\varGamma \) on the vertices which are incident with edges in \(A(\varGamma ,g)\).^{Footnote 1} The edge-set of \(\varGamma [g]\) is \(A(\varGamma ,g)\) and its vertices are 1- or 3-valent. Given \(i\in \{1,3\}\), we let \(V_i(\varGamma ,g)\) denote the set of vertices of \(\varGamma [g]\) having valency i.

Suppose \(\varGamma [g]\) is not a forest. Then \(\varGamma [g]\) contains an \(\ell \)-cycle C. From Lemma 4, we have \(g(\varGamma [g]) \ge g(\varGamma ) \ge s + 1\) and hence, from C, we can extract an s-arc \((v_0,v_1,\ldots ,v_{s-1})\). As g fixes this s-arc and as G is s-arc-regular, we deduce \(g=1\), which is a contradiction. Therefore \(\varGamma [g]\) is a forest. Before proceeding with the proof of Theorem 2, we prove a preliminary lemma.

Lemma 15

We have \(2|F(\varGamma ,g)|+3|V_1(\varGamma ,g)|+|V_3(\varGamma ,g)|\le |V\varGamma |\).

Proof

When \(s=1\), the arc-regularity of G implies \(V_1(\varGamma ,g)=V_3(\varGamma ,g)=\emptyset \) and the proof immediately follows. Hence for the rest of the proof we may suppose \(s\ge 2\).

We let

Since \(V_1(\varGamma ,g),V_3(\varGamma ,g),{\mathcal {F}},{\mathcal {N}}\) are pairwise disjoint and since \(|{\mathcal {F}}|=2|F(\varGamma ,g)|\), it suffices to show that \(|{\mathcal {N}}|\ge 2|V_1(\varGamma ,g)|\). We divide this proof according to the girth of \(\varGamma \).

Suppose \(g(\varGamma )\ge 5\). Here, we construct an auxiliary graph \(\varDelta \). The vertex set of \(\varDelta \) is \(V_1(\varGamma ,g)\cup {\mathcal {N}}\) and we declare a vertex \(v\in V_1(\varGamma ,g)\) adjacent to a vertex \(u\in {\mathcal {N}}\) if \(\{v,u\}\in E\varGamma \). By construction, \(\varDelta \) is bipartite with parts \(V_1(\varGamma ,g)\) and \({\mathcal {N}}\). Given \(v\in V_1(\varGamma ,g)\), the automorphism g acts as a 2-cycle on \(\varGamma (v)\). Let \(v_1,v_2\in \varGamma (v)\) forming the 2-cycle of g. Then \(\{v,v_1\},\{v,v_2\}\in N(\varGamma ,g)\) and hence \(v_1,v_2\in {\mathcal {N}}\). This shows that each vertex in \(V_1(\varGamma ,g)\) has two neighbours in \({\mathcal {N}}\). As \(g(\varGamma )\ge 5\), we have \(g(\varDelta )\ge 5\) and hence \(2|V_1(\varGamma ,g)|\le |{\mathcal {N}}|\), because \(\varDelta (v)\cap \varDelta (v')=\emptyset \) for any two distinct vertices \(v,v'\in V_1(\varGamma ,g)\).

Suppose \(g(\varGamma )= 3\). Let \(\varGamma (v) = \{w_1 , w_2 , w_3\}\). Without loss of generality, suppose \(w_1\) and \(w_2\) are adjacent. Since G is arc-transitive, \(w_i\) is adjacent to \(w_j\) for any \(i \ne j\). Thus \(\varGamma \cong K_4\). The graph \(K_4\) admits no non-identity automorphisms with \(\mathrm {fpr}(E\varGamma ,g)>1/3\).

Suppose \(g(\varGamma )= 4\). Since \(s\ge 2\), [8, Theorem 1.1 and Table I] implies that \(\varGamma \) is isomorphic to either \(K_{3,3}\) or \(K_{4,4}-4K_2\). In both cases, \(\varGamma \) does not admit a non-identity automorphism g with \(\mathrm {fpr}(E\varGamma ,g)>1/3\). \(\square \)

We now resume our proof of Theorem 2. As \(2|E\varGamma |=3|V\varGamma |\), from Lemma 15, we have

Let c be the number of connected components of \(\varGamma [g]\). From Euler’s formula, we have \(|V\varGamma [g]|-|E\varGamma [g]|=c\). Let \({\mathcal {S}}:=\{(v,w)\in V\varGamma [g]\times V\varGamma [g]\mid \{v,w\}\in E\varGamma [g]\}\). Then

It follows that \(|V_3(\varGamma ,g)|=|V_1(\varGamma ,g)|-2c<|V_1(\varGamma ,g)|\). Using (5.1) and this inequality, we obtain \(\mathrm {fpr}(E\varGamma ,g)\le 1/3\), which is our final contradiction.