On 1-arc-regular graphs (Q1864592)

For a finite, simple and undirected graph \(\Gamma\), is denoted by \(V\Gamma\), \(E\Gamma\) and \(\Aut\Gamma\) its vertex set, edge set and full automorphism group, respectively. \(\Gamma\) is said to be vertex-transitive (edge-transitive) if \(\Aut\Gamma\) acts transitively on \(V\Gamma\) \((E\Gamma)\). A sequence \((\alpha_1,\alpha_2,\dots,\alpha_{s+1})\) of \(s+1\) vertices of \(\Gamma\) is called an \(s\)-arc if \(\{\alpha_i,\alpha_{i+1}\}\) belongs to \(E\Gamma\) for \(1\leq i \leq s\) and \(\alpha_{i-1}\not=\alpha_{i+1}\) for \(2\leq i \leq s\). Let \(G\leq \Aut\Gamma\). The graph \(\Gamma\) is called \((G,s)\)-arc-transitive if \(G\) acts transitively on \(V\Gamma\) and on the set of \(s\)-arcs of \(\Gamma\); and \(\Gamma\) is said to be \(s\)-arc-transitive if it is \((\Aut\Gamma,s)\)-arc-transitive. In particular, \(\Gamma\) is called arc-transitive if it is 1-arc-transitive. A \((G,s)\)-arc-transitive graph \(\Gamma\) is said to be \((G,s)\)-arc-regular if \(G\) acts regularly on the sets of \(s\)-arcs of \(\Gamma\). Similarly, \((\Aut\Gamma,s)\)-arc-transitive graphs are called \(s\)-arc-regular. For a group \(G\) and a subset \(S\) of \(G\) satisfying \(1_G\not\in S\) and \(S^{-1}=S\), the Cayley graph \(\Gamma=\text{Cay}(G,S)\) of \(G\) relative to \(S\) is defined as the graph with \(V\Gamma=G\) and \(E\Gamma\) consisting of those unordered pairs \(\{x,y\}\) from \(G\) for which \(yx^{-1}\in S\). The paper under review is concerned with 1-arc-regular graphs of prime valencies. The first interesting case is valency 3. The first example of 1-arc-regular trivalent graphs was given by \textit{R. Frucht} [Can. J. Math. 4, 240-247 (1952; Zbl 0046.40903)]. Some other examples were given in \textit{M. D. E. Condor} and \textit{C. E. Praeger} [Eur. J. Comb. 17, 371-378 (1996; Zbl 0871.05029)] and \textit{R. C. Miller} [J. Comb. Theory, Ser. B 10, 163-182 (1971; Zbl 0223.05113)]. Moreover it was shown in \textit{Y.-Q. Feng} and \textit{J. H. Kwak} [Eur. J. Comb. 23, 559-565 (2002; Zbl 1016.05039)] that if \(\Gamma\) is a \((G,1)\)-arc-regular trivalent graph with \(G\) soluble then there is a subgroup \(H\) of \(G\) such that \(\Gamma\) is a Cayley graph of \(H\). The main results of the paper under review are the following theorems: Theorem 1.1. Let \(G\) be a finite soluble group and \(\Gamma\) be a \((G,1)\)-arc-regular graph of valency \(p\), for \(p\) an odd prime. Then \(G\) has a normal subgroup \(M\) of index \(p\) such that \(\Gamma\) is a Cayley graph of \(M\). Theorem 1.2. Let \(G\) be a finite nonabelian simple group and let \(b\) be an element of \(G\) with order 3 satisfying that \(b\) and \(b^{-1}\) are not conjugate in \(\Aut(G)\). Suppose that there exists an involution \(a\in G\) such that \(\langle a,b\rangle=G\). Set \(S=\{a,a^b,a^{b^2}\}\) and \(\Gamma=\text{Cay}(G,S)\). Then \(\Gamma\) is a connected, 1-arc-regular graph. As an application of Theorem 1.2 the authors consider the Ree simple groups \(\text{Ree}(q)\) and obtain as Theorem 1.3 an infinite family of 1-arc-regular graphs of valency 3 such that the graphs have insoluble automorphism groups. In Theorem 1.4 they deal with the quotient graph of a graph constructed in Theorem 1.3 and obtain another family of 1-arc-regular graphs of valency 3, which are not Cayley graphs. The statements of the two last-mentioned theorems are too technical to be produced here.