Vertex-primitive \frac{1}{2}-transitive graphs

D. E. Taylor School of Mathematics and Statistics University of Sydney N.S.W. 2006 Australia Ming-Yao Xu^{∗} Institute of Mathematics Peking University Beijing 100871 People’s Republic of China

August 5, 1994

1 Introduction

Let X = (V (X), E(X)) be a simple undirected graph. We call an ordered pair of adjacent vertices an arc of X. Let G be a subgroup of Aut X. The graph X is said to be G-vertex-transitive, G-edge-transitive, or G-arc-transitive if G acts transitively on the set of vertices, edges, or arcs of X, respectively. Furthermore, X is said to be vertex-transitive, edge-transitive, or arc-transitive, if it is Aut Xvertex-transitive, Aut X-edge-transitive, or Aut X-arc-transitive, respectively. We call a graph \frac{1}{2}-transitive, if it is vertex-transitive, edge-transitive, but not arc-transitive.

The first examples of \frac{1}{2}-transitive graphs were found by I. Z. Bouwer [5] in 1970. He found an infinite family of them. In 1984 D. F. Holt [7] found an example with 27 vertices. Very recently, B. Alspach, D. Marušič and L. Nowitz [1] found several infinite families of these graphs of degree 4: Holt’s graph occurs as the smallest example in one of their families. B. Alspach and the second author [3] determined all such graphs of order 3p with p a prime number greater than 3. All these graphs have automorphism groups acting imprimitively on their vertices, and all of them are so-called metacirculants, defined by Alspach and Parsons [2]. In [8] D. Holton asked if the automorphism group of a \frac{1}{2}- transitive graph is necessarily imprimitive, and we may ask if a \frac{1}{2}-transitive graph is necessarily metacirculant. The first question has been answered by Praeger and the second author [11] in the negative. They found several examples of \frac{1}{2}-transitive graphs with order a product of two distinct primes. In each case the automorphism group is P SL(2, p) acting on the cosets of a maximal subgroup isomorphic to A_{5} or S_{4}, and all of them are metacirculants.

∗The second author thanks the University of Sydney for its hospitality and financial support, where he did his part of this work.

In this paper we exhibit infinitely many vertex-primitive \frac{1}{2}-transitive graphs, most of which are not metacirculants. This answers the two questions mentioned above. More precisely, the main result of this paper is Theorem 3.1 in §3, which shows that for some primitive groups almost all orbitals are not selfpaired and their underlying undirected graphs are \frac{1}{2}-transitive. As an example, we consider the (primitive) action of the group P SL(2, p) on the cosets of a maximal subgroup isomorphic to A_{5}. For each prime p for which A_{5} is maximal in P SL(2, p) we calculate the exact number of non-self-paired orbitals. The result is presented in §4. To do this we use the same ideas and methods used in [11]. We quote some technical lemmas from [11] in the next section.

The link between groups and graphs that we use is the concept of the orbital graph of a permutation group.

Let G be a transitive permutation group on Ω. Consider the natural action of G on Ω × Ω. Assume that Γ_{0}, Γ_{1}, …, Γ_{r−1} are the orbits of G on Ω × Ω, where

Γ_{0} = { (α, α) | α ∈ Ω }.

We call these orbits the orbitals of G and call Γ_{0} the trivial orbital. The number r is called the rank of G. Each nontrivial orbital Γ_{i} can be viewed as a G-arc-transitive directed graph, and if (α, β) ∈ Γ_{i} is equivalent to (β, α) ∈ Γ_{i} for any α, β ∈ Ω, then Γ_{i} can be viewed as an undirected graph, identifying two directed edges (α, β) and (β, α) with one undirected edge αβ. We call this (directed or undirected) graph Γ_{i} an orbital graph of G. If the graph is undirected, the orbital is said to be self-paired. Thus, given G, all G-arc-transitive (undirected) graphs can be found by finding all self-paired orbitals of G. If the full automorphism group of the underlying undirected graph of a non-self-paired orbital digraph is G, then this graph is \frac{1}{2}-transitive.

Take a point α ∈ Ω. The orbits of the stabilizer G_{α} on Ω are called suborbits of G. There is a one-to-one correspondence between the suborbits and the orbitals of G. For each orbital Γ_{i},

Δ_{i} = { β ∈ Ω | (α, β) ∈ Γ_{i} }

is a suborbit, and for each suborbit Δ_{i},

Γ_{i} = { (α, β)^{g} | g ∈ G, β ∈ Δ_{i} }

is an orbital of G. Thus the number of suborbits is the rank of G.

It is well known that G is primitive if and only if all orbital graphs of G are connected. This ensure that all the graphs that we find are connected. The group- and graph-theoretic notation and terminology used in this paper are standard; the reader can refer to [9] and [4] when necessary.

In the next section we give some group-theoretic lemmas which will be used later. In section 3, the main theorem of the paper is proved. An example is given in section 4.

2 Preliminary lemmas

Since the 2-dimesional projective linear groups P SL(2, p) and P GL(2, p) over the field with p elements are the background of our investigation in this paper, we need information about the subgroup structure of these groups. The following theorem is due to Dickson; the reader may refer to [9] II, §8 or [6] for a proof.

Theorem 2.1 Assume that p is a prime number greater than 11. Then

(a) the maximal subgroups of P SL(2, p) are:

(i) One class of subgroups isomorphic to Z_{p} : Z_{\frac{p−1}{2}} , where A : B denotes the semidirect product of A and B and Z_{n} denotes the cyclic group of order n.

(ii) One class of subgroups isomorphic to D_{p−1} and one class isomorphic

to D_{p+1}, where D_{n} denotes the dihedral group of order n. (iii) Two classes of subgroups isomorphic to A_{5}, if p ≡ ±1 (mod 10).

(They are conjugate in P GL(2, p).) (iv) Two classes of subgroups isomorphic to S_{4}, if p ≡ ±1 (mod 8).

(They are conjugate in P GL(2, p).)

(v) One class of subgroups isomorphic to A_{4}, if p ≡ 3, 13, 27, or 37 (mod 40).

(b) the maximal subgroups of P GL(2, p) are:

(i) One class of subgroups isomorphic to Z_{p} : Z_{p−1}. (ii) One class of subgroups isomorphic to D_{2(p−1)} and one class isomor-

phic to D_{2(p+1)}. (iii) One class of of subgroups isomorphic to S_{4}. (iv) P SL(2, p).

To determine suborbits for primitive groups we need the following result of Manning ([11] Lemma 2.1).

Lemma 2.2 Let G be a transitive group on Ω, let H = G_{α} for some α ∈ Ω, and let K ≤ H. Suppose that the set of G-conjugates of K which are contained in H form t conjugacy classes of H, with representatives K_{1}, K_{2}, …, K_{t}. Then K fixes

Σ_{i=1}^{t}|N_{G}(K_{i}) : N_{H}(K_{i})|

points of Ω. In particular, if t = 1, that is if every G-conjugate of K in H is conjugate to K in H, then K fixes |N_{G}(K) : N_{H}(K)| points of Ω.

Given a subgroup K of a group H, there is a natural action of H on the set [H : K] of right cosets of K. If H acts on Ω, let μ_{K}(Ω) be the number of H-orbits of Ω isomorphic to [H : K] and let Fix_{Ω}(K) be the set of fixed points of K in Ω. Then Ω = ⋃_{L} μ_{L}(Ω) [H : L], and therefore

| Fix_{Ω}(K)| = ∑_{L} μ_{L}(Ω)| Fix_{[H:L]}(K)|,  (2.1)

where the union and summation range over a set of representatives for the conjugacy classes of subgroups of H.

We have Fix_{[H:L]}(K) = { Lh | hKh^{−1} ⊆ L } and therefore | Fix_{[H:L]}(K)| = 0 unless L contains a conjugate of K. Thus (2.1) is essentially an upper triangular system of equations and it is easily solved for the μ_{L}(Ω). The coefficients | Fix_{[H:L]}(K)| are given by Lemma 2.2, namely

| Fix_{[H:L]}(K)| = ∑_{i=1}^{t} |N_{H}(K_{i}) : N_{L}(K_{i})|,

where {K_{1}, K_{2}, …, K_{t}} is a set of representatives for the conjugacy classes in L of the H-conjugates of K that are contained in L. In particular, | Fix_{[H:K]}(K)| = |N_{H}(K)/K|.

In the case of a group acting on the cosets of a subgroup isomorphic to A_{5}, these general considerations yield the following lemma (proved in [11]).

Lemma 2.3 ([11, Lemma 2.2]) Let G be a primitive permutation group on Ω, and let H = G_{α} for some α ∈ Ω. Suppose that H = A_{5} and let K_{1}, …, K_{7} be seven subgroups of H satisfying K_{1} ≅ A_{4}, K_{2} ≅ D_{10}, K_{3} ≅ D_{6}, K_{4} ≅ Z_{5}, K_{5} ≅ Z_{3}, K_{6} ≅ D_{4} and K_{7} ≅ Z_{2}. Let k_{i} be the number of points in Ω fixed by K_{i}, for i = 1, 2, …, 7. Then G has 1 suborbit of length 1, k_{1} − 1 suborbits of length 5, k_{2} − 1 suborbits of length 6, k_{3} − 1 suborbits of length 10, \frac{1}{2}(k_{4} − k_{2}) suborbits of length 12, \frac{1}{2}(k_{5} − 2k_{1} − k_{3} + 2) suborbits of length 20, \frac{1}{3}(k_{6} − k_{1}) suborbits of length 15, \frac{1}{2}(k_{7} − 2k_{2} − 2k_{3} − k_{6} + 4) suborbits of length 30, and all the other suborbits have length 60.

To determine which suborbits are self-paired, we need two other lemmas from [11].

Lemma 2.4 ([11, Lemma 2.2]) Let D = ⟨a, b⟩ ≅ D_{2n}, n ≥ 2, be a permutation group on Ω = {1, 2, …, n}, where

a = (1, 2, ⋯, n) and b = (1)(2, n)(3, n − 1) ⋯ (i, n + 2 − i) ⋯

Then the nontrivial orbitals of D are Δ_{i} = (1, i)^{D} = (1, n + 2 − i)^{D}, for 2 ≤ i ≤ \frac{1}{2}(n + 2). Each of these orbitals is self-paired. Moreover, for all points i, j, with i ≠ j, there is an involution in D which interchanges i and j.

The next lemma is a generalization of [11, Lemma 2.4].

Lemma 2.5 Let G be a transitive group on Ω and let H = G_{α} for some α ∈ Ω. Assume that G has t conjugacy classes of involutions, say C_{1}, …, C_{t}. Take a representative u_{j} in C_{j}. Assume that u_{j} has N_{j} cycles of length 2. For a nontrivial self-paired orbital Δ and a pair (α, β) ∈ Δ, let inv(Δ) be the number of involutions in G with a 2-cycle (α, β). Then

∑_{j=1}^{t} \frac{N_{j}}{c_{j}} = \frac{1}{2|H|} ∑_{Δ=Δ′} |Δ(α)| inv(Δ),

where c_{j} is the order of the centralizer of u_{j}.

Proof. We count the elements of the set

M = { (u, {α, β}) | u is an involution and (α, β) is a 2-cycle of u }.

On the one hand

|M| = ∑_{j=1}^{t} N_{j} \frac{|G|}{c_{j}}.

On the other hand we can classify the pairs {α, β} according to the (self-paired) orbital to which they belong. For each self-paired orbital Δ there are

\frac{1}{2}|Δ(α)| |Ω| = \frac{1}{2}|Δ(α)| |G|/|H|

pairs {α, β} such that (α, β) ∈ Δ and each of these has inv(Δ) associated involutions. Thus

|M| = ∑_{Δ=Δ′} \frac{1}{2}|Δ(α)|\frac{|G|}{|H|} inv(Δ),

and the result follows.

3 Main theorem

Theorem 3.1 Let H be a finite group, and let P be an infinite set of positive integers. Assume that { G(p) | p ∈ P } is an infinite family of finite primitive groups acting on a finite set Ω(p), and that for every p, the stabilizer of a point α ∈ Ω(p) is a maximal subgroup of G(p) identified with H. Then the degree d(p) of G(p) is |G(p)|/|H|. Let m(p) be the maximum order of the normalizers of nontrivial subgroups of H in G(p), and let c(p) be the minimun order of the centralizers of involutions in G(p). Let r(p) be the rank of G(p), and let h(p) be the number of non-self-paired orbitals of G(p). Assume that G(p) has t(p) classes of involutions, and that t(p) < t for every p. Suppose that lim_{p→∞}(|G(p)|/m(p)) = ∞ and lim_{p→∞} c(p) = ∞. Then almost all orbitals of G(p) are not self-paired, i.e.,

lim_{p→∞} \frac{h(p)}{r(p)} = 1.

Furthermore, if G(p) is a maximal subgroup of the symmetric group Sym(Ω(p)) for every p, then the underlying undirected graphs of the non-self-paired orbital digraphs are \frac{1}{2}-transitive and pairwise non-isomorphic.

Remark. The conditions of Theorem 3.1 are satisfied in the following cases:

(a) H = A_{5}, P is the set of all prime numbers congruent to ±1 (mod 10), and G(p) = P SL(2, p);

(b) H = S_{4}, P is the set of all prime numbers congruent to ±1 (mod 8), and G(p) = P SL(2, p); (c) H = S_{4}, P is the set of primes greater than 5, and G(p) = P GL(2, p).

Proof of Theorem 3.1. Let K_{1}, K_{2}, …, K_{s} be representatives for the conjugacy classes of nontrivial subgroups of H, let μ_{i}(p) be the number of H-orbits in which the stabilizer of a point is conjugate to K_{i}, and let μ(p) be the number of regular H-orbits (i.e., for which the stabilizer of a point is trivial).

Then μ_{i}(p) ≤ | Fix_{Ω(p)}(K_{i})| and by Lemma 2.2, | Fix_{Ω(p)}(K_{i})| ≤ sm(p), whence

μ_{i}(p) ≤ sm(p).

We have

|H|μ(p) = d(p) − ∑_{i=1}^{s} μ_{i}(p)\frac{|H|}{K_{i}} ≥ \frac{G(p)}{|H|} − s^{2}m(p),

and as lim_{p→∞} |G(p)|/m(p) = ∞, it follows that

lim_{p→∞} \frac{μ_{i}(p)}{μ(p)} = 0 for every i.  (3.1)

In addition,

r(p) = μ(p) + ∑_{i=1}^{s} μ_{i}(p)  (3.2)

and therefore

lim_{p→∞} \frac{μ(p)}{r(p)} = 1.  (3.3)

Now suppose that there are σ(p) self-paired regular H-orbits. Then from Lemma 2.5 we have

\frac{1}{2}σ(p) ≤ ∑_{j} \frac{N_{j}}{c_{j}} ≤ \frac{td(p)}{2c(p)},

and so

\frac{σ(p)}{r(p)} ≤ \frac{d(p)}{r(p)} \frac{t}{c(p)}.

On the other hand, it follows from equations (3.1), (3.2) and (3.3) that lim_{p→∞} d(p)/r(p) = |H|. Therefore lim_{p→∞} σ(p)/r(p) = 0 because, by assumption, lim_{p→∞} c(p) = ∞.

Since r(p) ≥ h(p) ≥ μ(p) − σ(p) we have

1 ≥ lim_{p→∞} \frac{h(p)}{r(p)} ≥ lim_{p→∞} \frac{μ(p)}{r(p)} − lim_{p→∞} \frac{σ(p)}{r(p)} = 1.

and so

lim_{p→∞} \frac{h(p)}{r(p)} = 1.

We are assuming that G(p) is a maximal subgroup of the symmetric group Sym(Ω(p)) and therefore it is the full automorphism group of every orbital graph. In particular, it is the full automorphism group of every non-self-paired orbital digraph and of the underlying undirected graph. Thus these underlying undirected graphs are \frac{1}{2}-transitive.

Finally, we shall show that the orbital graphs and digraphs are pairwise nonisomorphic. If σ is an isomorphism between two of the orbital graphs, Δ_{1} and Δ_{2}, then σ lies in the normalizer in Sym(Ω(p)) of their common automorphism group G(p). Since G(p) is maximal in Sym(Ω(p)), it is self-normalizing, and so σ ∈ G(p), whence Δ_{1} = Δ_{2}, a contradiction. This completes the proof of the theorem.

4 An example

Theorem 4.1 Suppose that p ≡ ±1 (mod 10) and that G = G(p) = P SL(2, p) acts on the set Ω = Ω(p) = [G : H] of right cosets of a subgroup H ≅ A_{5}. Then

(a) We have d = d(p) = |Ω| = (p^{3} − p)/120, the rank of G(p) is r = r(p), and G has 1 suborbit of length 1, x_{1}(p) suborbits of length 5, x_{2}(p) suborbits of length 6, x_{3}(p) suborbits of length 10, x_{4}(p) suborbits of length 12, x_{5}(p) suborbits of length 20, x_{6}(p) = 0 suborbits of length 15, x_{7}(p) suborbits of length 30, and x(p) suborbits of length 60. All the suborbits of G of length less than 60 and y(p) of the suborbits of length 60 are self-paired. The numbers x_{i} = x_{i}(p) are given in Table 4.1 and the numbers r = r(p), x = x(p), y = y(p) and h = h(p) = x − y are given in Table 4.2.

(b) The underlying undirected graphs of the h non-self-paired orbital digraphs are \frac{1}{2}-transitive graphs. These graphs are pairwise non-isomorphic. All have automorphism group P SL(2, p).

(c) Almost all orbital graphs of P SL(2, p) give \frac{1}{2}-transitive graphs. That is,

lim_{p→∞} \frac{h(p)}{r(p)} = 1.

Proof. By Theorem 2.1, P SL(2, p) has only one class of involutions and the centralizer of an involution is D_{p+1} or D_{p−1}, depending on whether 4 divides p + 1 or p − 1. Every maximal subgroup of P SL(2, p) has order at most a quadratic polynomial of p, and so the conditions of Theorem 3.1 are satisfied. Thus conclusions (b) and (c) hold.

Next we shall calculate the exact values of x_{i}, x, y and h for G(p) = P SL(2, p) and H = A_{5}. We must have p ≡ ±1 (mod 10) and the calculations fall naturally into 16 cases according to the value of p (mod 120), namely p ≡ ±1, ±11, ±31, ±41, ±61, ±71, ±91, or ±101 (mod 120). We give details of the proof for the cases p ≡ ±1 (mod 120). The proofs for the other cases are entirely similar and are omitted.

There are 7 conjugacy classes of nontrivial subgroups of H = A_{5}, with representatives K_{1} = A_{4}, K_{2} = D_{10}, K_{3} = D_{6}, K_{4} = Z_{5}, K_{5} = Z_{3}, K_{6} = D_{4} and K_{7} = Z_{2} as in Lemma 2.3. We have the following table, the last line of which comes from Lemma 2.2.

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ K_{i} & A_{4} & D_{10} & D_{6} & Z_{5} & Z_{3} & D_{4} & Z_{2} \\ N_{H}(K_{i}) & A_{4} & D_{10} & D_{6} & D_{10} & D_{6} & A_{4} & D_{4} \\ N_{G}(K_{i}) & S_{4} & D_{20} & D_{12} & D_{p∓1} & D_{p∓1} & S_{4} & D_{p∓1} \\ k_{i} = |Fix_{Ω}(K_{i})| & 2 & 2 & 2 & \frac{1}{10}(p ∓ 1) & \frac{1}{6}(p ∓ 1) & 2 & \frac{1}{4}(p ∓ 1) \end{matrix}

By Lemma 2.3, G has 1 suborbit of length 1, 1 of length 5, 1 of length 6, 1 of length 10, \frac{1}{20}(p ∓ 1) − 1 of length 12, \frac{1}{12}(p ∓ 1) − 2 of length 20, none of length 15, \frac{1}{8}(p ∓ 1) − 3 of length 30, and x of length 60, where

60x = \frac{1}{120}(p^{3} − p) − 1 − 5 − 6 − 10 − 12 · (\frac{1}{20}(p ∓ 1) − 1)

− 20 · (\frac{1}{12}(p ∓ 1) − 2) − 30 · (\frac{1}{8}(p ∓ 1) − 3).

Therefore x = \frac{1}{7200}(p^{3} − 723p ± 722) + 2 and hence G has rank

r = 1 + 1 + 1 + 1 + (\frac{1}{20}(p ∓ 1) − 1) + (\frac{1}{12}(p ∓ 1) − 2)

+ (\frac{1}{8}(p ∓ 1) − 3) + \frac{1}{7200}(p^{3} − 723p ± 722) + 2

= \frac{1}{7200}(p^{3} + 1137p ∓ 1138).

Now we show that all the nontrivial suborbits of length less than 60 are self-paired. The arguments are the same in all cases. For instance, consider a suborbit Δ(α) of length 12. For β ∈ Δ(α), we have G_{αβ} = Z_{5}, and N_{G}(G_{αβ}) ≅ D_{p∓1} acts on Fix_{Ω}(G_{αβ}), a set of size \frac{1}{10}(p ∓ 1), as D_{\frac{p∓1}{5}} . By Lemma 2.4, some element of N_{G}(G_{αβ}) interchanges α and β, and so Δ(α) is self-paired.

Next, we use Lemma 2.5 to determine the number y of self-paired suborbits of length 60. In the following table y_{|Δ(α)|} denotes the number of self-paired suborbits of length |Δ(α)| and inv(Δ) is defined in Lemma 2.5.

\begin{matrix}|Δ(α)| & 5 & 6 & 10 & 12 & 20 & 30 & 60 \\ y_{|Δ(α)|} & 1 & 1 & 1 & \frac{1}{20}(p ∓ 1) − 1 & \frac{1}{12}(p ∓ 1) − 2 & \frac{1}{8}(p ∓ 1) − 3 & y \\ G_{αβ} & A_{4} & D_{10} & D_{6} & Z_{5} & Z_{3} & Z_{2} & 1 \\ G_{\{α,β\}} & S_{4} & D_{20} & D_{12} & D_{10} & D_{6} & D_{4} & Z_{2} \\ inv(Δ) & 6 & 6 & 4 & 5 & 3 & 2 & 1 \end{matrix}

Since every involution has \frac{1}{4}(p ∓ 1) fixed points, so every involution has

N = \frac{1}{2}(\frac{p^{3} − p}{120} − \frac{p ∓ 1}{4}) = \frac{1}{240}(p^{3} − 31p ± 30)

cycles of length 2. The centralizer of an involution has order p ∓ 1 and so, by Lemma 2.5,

\frac{p^{2} ± p}{2} − 15 = 5 · 1 · 6 + 6 · 1 · 6 + 10 · 1 · 4 + 12 · (\frac{p ∓ 1}{20} − 1) · 5

+ 20 · (\frac{p ∓ 1}{12} − 2) · 3 + 30 · (\frac{p ∓ 1}{8} − 3) · 2 + 60 · y · 1,

whence

y = \{ \begin{matrix}(p^{2} − 30p + 509)/120 & if p ≡ 1 (mod 120), \\ (p^{2} − 32p + 447)/120 & if p ≡ −1 (mod 120). \end{matrix}

Thus the number h = x − y of non-self-paired suborbits of length 60 is

h = \{ \begin{matrix}(p^{3} − 60p^{2} + 1077p − 15418)/7200 & if p ≡ 1 (mod 120), \\ (p^{3} − 60p^{2} + 1197p − 13142)/7200 & if p ≡ −1 (mod 120). \end{matrix}

Now P SL(2, p) has two conjugacy classes of subgroups isomorphic to A_{5} and these are interchanged by P GL(2, p). Hence P GL(2, p) has no subgroup of index d, and by the result of Liebeck, Praeger and Saxl [10], there are no simply primitive groups properly containing P SL(2, p). From these observations it follows that each of the above orbital graphs and digraphs has automorphism group P SL(2, p).

Finally, the same argument as in the proof of Theorem 3 shows that the orbital graphs and digraphs are pairwise non-isomorphic. This completes the proof in this case.

For the other cases, we list the results in Tables 4.1 and 4.2.

Corollary 4.2 Let G and H be the same as in Theorem 4.1. Assume that Δ is an orbital graph of G, or the underlying undirected graph of a non-self-paired orbital digraph. If p > 61, then Δ is not a metacirculant.

Proof. If Δ were a metacirculant, then G would have a metacyclic subgroup M, which is transitive. It follows that d = \frac{1}{120}(p^{3} − p) would divide the order of M. If p > 61, Theorem 2.1 tells us that the only such subgroup of G is G itself. But G is not metacyclic, a contradiction.

Table 4.1 refers to the action of P SL(2, p) on the cosets of A_{5}. In the table K_{i} is a subgroup of A_{5}, k_{i} = | Fix_{Ω}(K_{i})|, and x_{i} is the number of the suborbits with a point stabilizer isomorphic to K_{i}. In all cases x_{6} = 0.

i  1 2  3  4  5  7
K_{i}  A_{4} D_{10} D_{6}  Z_{5}  Z_{3}  Z_{2}
N_{H}(K_{i}) A_{4} D_{10} D_{6}  D_{10}  D_{6}  D_{4}
N_{G}(K_{i}) S_{4} D_{20} D_{12} D_{p∓1}  D_{p∓1}  D_{p∓1}
{p ≡ ±1 \atop (mod 120)}  k_{i}  2 2  2  \frac{p∓1}{10}  \frac{p∓1}{6}  \frac{p∓1}{4}
x_{i}  1 1  1 \frac{p∓1}{20} − 1 \frac{p∓1}{12} − 2 \frac{p∓1}{8} − 3
N_{G}(K_{i}) A_{4} D_{10} D_{12} D_{p∓1}  D_{p±1}  D_{p±1}
{p ≡ ±11 \atop (mod 120)}  k_{i}  1 1  2  \frac{p∓1}{10}  \frac{p±1}{6}  \frac{p±1}{4}
x_{i}  0 0  1 \frac{p∓1}{20} − \frac{1}{2} \frac{p±1}{12} − 1 \frac{p±1}{8} − \frac{3}{2}
N_{G}(K_{i}) S_{4} D_{10} D_{6} D_{p∓1}  D_{p∓1}  D_{p±1}
{p ≡ ±31 \atop (mod 120)}  k_{i}  2 1  1  \frac{p∓1}{10}  \frac{p∓1}{6}  \frac{p±1}{4}
x_{i}  1 0  0 \frac{p∓1}{20} − \frac{1}{2} \frac{p∓1}{12} − \frac{3}{2} \frac{p±1}{8} − 1
N_{G}(K_{i}) S_{4} D_{20} D_{6} D_{p∓1}  D_{p±1}  D_{p∓1}
{p ≡ ±41 \atop (mod 120)}  k_{i}  2 2  1  \frac{p∓1}{10}  \frac{p±1}{6}  \frac{p∓1}{4}
x_{i}  1 1  0 \frac{p∓1}{20} − 1 \frac{p±1}{12} − \frac{3}{2} \frac{p∓1}{8} − 2
N_{G}(K_{i}) A_{4} D_{20} D_{12} D_{p∓1}  D_{p∓1}  D_{p∓1}
{p ≡ ±61 \atop (mod 120)}  k_{i}  1 2  2  \frac{p∓1}{10}  \frac{p∓1}{6}  \frac{p∓1}{4}
x_{i}  0 1  1 \frac{p∓1}{20} − 1 \frac{p∓1}{12} − 1 \frac{p∓1}{8} − \frac{5}{2}
N_{G}(K_{i}) S_{4} D_{10} D_{12} D_{p∓1}  D_{p±1}  D_{p±1}
{p ≡ ±71 \atop (mod 120)}  k_{i}  2 1  2  \frac{p∓1}{10}  \frac{p±1}{6}  \frac{p±1}{4}
x_{i}  1 0  1 \frac{p∓1}{20} − \frac{1}{2} \frac{p±1}{12} − 2 \frac{p±1}{8} − 2
N_{G}(K_{i}) A_{4} D_{10} D_{6} D_{p∓1}  D_{p∓1}  D_{p±1}
{p ≡ ±91 \atop (mod 120)}  k_{i}  1 1  1  \frac{p∓1}{10}  \frac{p∓1}{6}  \frac{p±1}{4}
x_{i}  0 0  0 \frac{p∓1}{20} − \frac{1}{2} \frac{p∓1}{12} − \frac{1}{2} \frac{p±1}{8} − \frac{1}{2}
N_{G}(K_{i}) A_{4} D_{20} D_{6} D_{p∓1}  D_{p±1}  D_{p∓1}
{p ≡ ±101 \atop (mod 120)}  k_{i}  1 2  1  \frac{p∓1}{10}  \frac{p±1}{6}  \frac{p∓1}{4}
x_{i}  0 1  0 \frac{p∓1}{20} − 1 \frac{p±1}{12} − \frac{1}{2} \frac{p∓1}{8} − \frac{3}{2}

Table 4.1: The number x_{i} of non-regular suborbits with stabilizer K_{i}.

Table 4.2 gives the number x of regular suborbits of P SL(2, p) acting on cosets of A_{5}, the rank r, the number y of self-paired regular suborbits, and the number h = x − y of non-self-paired regular suborbits. The number of 2-cycles in each involution is \frac{1}{240}(p^{3} − 31p + 30ε), where ε = ±1 and p ≡ ε (mod 4).

\begin{matrix}{p \atop (mod 120)} & x & r & y & h \\ 1 & \frac{p^{3}−723p+15122}{7200} & \frac{p^{3}+1137p−1138}{7200} & \frac{p^{2}−30p+509}{120} & \frac{p^{3}−60p^{2}+1077p−15418}{7200} \\ −1 & \frac{p^{3}−723p+13678}{7200} & \frac{p^{3}+1137p+1138}{7200} & \frac{p^{2}−32p+447}{120} & \frac{p^{3}−60p^{2}+1197p−13142}{7200} \\ 11 & \frac{p^{3}−723p+6622}{7200} & \frac{p^{3}+1137p+562}{7200} & \frac{p^{2}−32p+231}{120} & \frac{p^{3}−60p^{2}+1197p−7238}{7200} \\ −11 & \frac{p^{3}−723p+7778}{7200} & \frac{p^{3}+1137p−562}{7200} & \frac{p^{2}−30p+269}{120} & \frac{p^{3}−60p^{2}+1077p−8362}{7200} \\ 31 & \frac{p^{3}−723p+7022}{7200} & \frac{p^{3}+1137p−238}{7200} & \frac{p^{2}−32p+271}{120} & \frac{p^{3}−60p^{2}+1197p−9238}{7200} \\ −31 & \frac{p^{3}−723p+7378}{7200} & \frac{p^{3}+1137p+238}{7200} & \frac{p^{2}−30p+269}{120} & \frac{p^{3}−60p^{2}+1077p−8762}{7200} \\ 41 & \frac{p^{3}−723p+11122}{7200} & \frac{p^{3}+1137p−338}{7200} & \frac{p^{2}−30p+389}{120} & \frac{p^{3}−60p^{2}+1077p−12218}{7200} \\ −41 & \frac{p^{3}−723p+10478}{7200} & \frac{p^{3}+1137p+338}{7200} & \frac{p^{2}−32p+367}{120} & \frac{p^{3}−60p^{2}+1197p−11542}{7200} \\ 61 & \frac{p^{3}−723p+11522}{7200} & \frac{p^{3}+1137p−1138}{7200} & \frac{p^{2}−30p+389}{120} & \frac{p^{3}−60p^{2}+1077p−11818}{7200} \\ −61 & \frac{p^{3}−723p+10078}{7200} & \frac{p^{3}+1137p+1138}{7200} & \frac{p^{2}−32p+327}{120} & \frac{p^{3}−60p^{2}+1197p−9542}{7200} \\ 71 & \frac{p^{3}−723p+10222}{7200} & \frac{p^{3}+1137p+562}{7200} & \frac{p^{2}−32p+351}{120} & \frac{p^{3}−60p^{2}+1197p−10838}{7200} \\ −71 & \frac{p^{3}−723p+11378}{7200} & \frac{p^{3}+1137p−562}{7200} & \frac{p^{2}−30p+389}{120} & \frac{p^{3}−60p^{2}+1077p−11962}{7200} \\ 91 & \frac{p^{3}−723p+3422}{7200} & \frac{p^{3}+1137p−238}{7200} & \frac{p^{2}−32p+151}{120} & \frac{p^{3}−60p^{2}+1197p−5638}{7200} \\ −91 & \frac{p^{3}−723p+3778}{7200} & \frac{p^{3}+1137p+238}{7200} & \frac{p^{2}−30p+149}{120} & \frac{p^{3}−60p^{2}+1077p−5162}{7200} \\ 101 & \frac{p^{3}−723p+7522}{7200} & \frac{p^{3}+1137p−338}{7200} & \frac{p^{2}−30p+269}{120} & \frac{p^{3}−60p^{2}+1077p−8618}{7200} \\ −101 & \frac{p^{3}−723p+6878}{7200} & \frac{p^{3}+1137p+338}{7200} & \frac{p^{2}−32p+247}{120} & \frac{p^{3}−60p^{2}+1197p−7942}{7200} \end{matrix}

Table 4.2: The number h of non-self-paired regular sub-orbits.

References

[1] B. Alspach, D. Marušič and L. Nowitz, \frac{1}{2}-arc-transitive graphs, 1991, preprint.

[2] B. Alspach and T. D. Parsons, A construction for vertex-transitive graphs, Canad. J. Math. 34 (1982), 307–318.

[3] B. Alspach and M.-Y. Xu, \frac{1}{2}-transitive graphs of order 3p, 1991, preprint.

[4] N. Biggs, Finite Groups of Automorphisms, London Mathematical Society Lecture Note Series, 6, Cambridge University Press, 1971.

[5] I. Z. Bouwer, Vertex and edge-transitive but not 1-transitive graphs, Canad. Math. Bull. 13 (1970), 231–237.

[6] L. E. Dickson, Linear Groups with an exposition of the Galois field theory, Leipzig, 1901; Dover Publ. 1958.

[7] D. F. Holt, A graph which is edge transitive but not arc-transitive, J. Graph Theory 5 (1981), 201–204.

[8] D. Holton, Research Problem 9, Discrete Math. 38(1982), 125-126.

[9] B. Huppert, Endliche Gruppen I, Springer-Verlag, 1967.

[10] M. W. Liebeck, C. E. Praeger and J.Saxl, A classification of the maximal subgroups of the finite alternating and symmetric groups, J. Algebra 111(1987), 365–383.

[11] C. E. Praeger and M.-Y. Xu, Vertex primitive graphs of order a product of two distinct primes, submitted to J. Combin. Theory Ser. B.