Chapter 5
Quotients of vertex-transitive graphs

This chapter will study some operations on vertex-transitive graphs.

5.1  Quotient graphs

Let G = (V,E) be a digraph. For a partition B of V, the quotient G_B is defined as the digraph with vertex set B such that, for any two vertices B,C Î B, B is connected to C if and only if there exist u Î B and v Î C which are adjacent in G.

It is clear that a quotient of a connected graph is connected.

Proposition 1 A graph is connected if and only if it is a quotient of a cycle.

Let G = (V,E) be a vertex-transitive graph. Assume that G £ Aut G is transitive on V. If B is a G-invariant partition of V, then the quotient G_B is called an imprimitive quotient (relative to G). In the case, G is called an extension of G_B; if in addition G and G_B have the same valency then G is called an imprimitive cover of G_B.

Proposition 2 Let G = C_n be a cycle of size n. Then G has a non-trivial imprimitive quotient if and only if n is not a prime. Each of imprimitive quotients of G is a cycle or a single edge graph K₂.

Example 3

Let G = 6K₂, 6 disjoint copies of K₂.

There is a group X £ Aut G such that X @ Z₆×Z₂ is transitive on V. There exists an X-partition B with two blocks of size 6, such that G_B @ K₂.

There exists a group Y £ Aut G such that Y @ D₁₂ is transitive on V, and there exists an X-partition B¢ with 6 blocks of size 2 such that G_B¢ @ C₆.

Let Z = A₄, acting on {1,2,3,4}. Let g = (12)(34). Then it is easily shown that G @ Cay(Z,{g}). Thus Z acts on V regularly. Let H < Z be isomorphic to Z₃, and let B¢¢ be the set of right cosets of H in Z. Then G_B¢¢ @ K₄.

Therefore, the disconnected graph G has connected imprimitive quotient graphs isomorphic to K₂, K₃, K₄, C₆.

Exercise 4

Let G = 6K₂. Find all imprimitive quotients of G.

5.2  Imprimitive quotients of Cayley graphs

Let G be Petersen graph. Then G can be represented as a coset graph of A₅. Let G @ A₅ act on W = {1,2,3,4,5}. Let H = á(123),(23)(45)ñ, and let g = (24)(35). Then

G @ G(G,H,HgH).

It is known that G is not a Cayley graph. However, we will see that G is an imprimitive quotient of a Cayley graph, for example, the Cayley graph Cay(G,{g}).

Theorem 5 Each vertex-transitive graph is an imprimitive quotient of a Cayley graph.

PROOF. Let G = (V,E) be a vertex-transitive graph, and assume that G £ Aut G is transitive on V. Then there exist a subgroup H < G and a subset S Ì G such that

G = G(G,H,HSH).

Let R be a subset of G such that S Í R Í HSH. Let

S = Cay(G,R).

Let B = [G:H]. We claim that

G @ SB.

First we notice that G and S_B have the same vertex set [G:H]. We need to prove that for any Hx,Hy Î [G:H],

Hx is connected in G to Hy if and only if Hx is connected in SB to Hy.

Assume that Hx is connected in G to Hy. By definition, yx^-1 Î HSH, so that yx^-1 = h₁sh₂ for some h₁,h₂ Î H and some s Î S. Thus (h₁^-1y)(h₂x)^-1 = s Î S Í R, so the vertex h₂x is connected in S to the vertex h₁^-1y. As h₂x Î Hx and h₁^-1y Î Hy, by definition, Hx is connected in S_B to Hy.

Assume now that Hx is connected in S_B to Hy. Then there exists some h₁x Î Hx which is connected in S to some h₂y Î Hy. By definition, (h₂y)(h₁x)^-1 Î R Í HSH. It follows that yx^-1 Î HSH, and hence Hx is connected in G to Hy.

Therefore, G @ S_B, as desired. ^[¯]

Exercise 6

(1)

Prove that Petersen graph is an imprimitive quotient of a connected arc-transitive Cayley graph.


(2) Prove that the complete graph K₆ is an imprimitive quotient of the icosahedron.

5.3  Normal quotients

Let G = (V,E), and assume that G £ Aut G is transitive on V. Let N be a normal subgroup of G which is intransitive on V, and let B be the set of N-orbits in V. Then B is a partition of V. Denote by G_N the quotient graph G_B.

Lemma 7 Using notation defined above,

$(1)$ B is a G-invariant partition;


$(2)$ for any B,C Î B, the vertex B is connected in G_N to the vertex C if and only if each u Î B is connected in G to some v Î C.

PROOF. Suppose that, for some B Î B and some g Î G, B^g ¹ B. Then there exist some u Î B and some C Î B such that u^g Î C ¹ B. Hence C = (u^g)^N = (u^N)^g = B^g, and so B is G-invariant.

Assume that the vertex B Î B is connected in G_N to the vertex C Î B. Then some u Î B is connected in G to v Î C. Since N is transitive on B, for any u¢ Î B, there exists g Î N such that u^g = u¢. Since g fixes C (setwise), we have v^g Î C. Thus u¢ is connected to v^g. ^[¯]

The quotient G_N is called a normal quotient induced by N. In particular, a normal quotient is an imprimitive quotient. The property given in Lemma 5.7 (2) is not shared byimprimitive quotient, for example, 6K₂ is A₄-vertex-transitive, and has an imprimitive quotient isomorphic to K₄.

It is known that imprimitive quotients of arc-transitive graphs are arc-transitive. For normal quotients, we have a stronger result, given in the next section.

5.4  Normal quotients of s-arc-transitive graphs

Recall that a graph G = (V,E) is said to be (G,s)-arc-transitive if G £ Aut G is transitive on the set of all s-arcs of G. For example, complete graphs and hypercubes are 2-arc-transitive but not 3-arc-transitive; while regular complete bipartite graphs and odd graphs are 3-arc-transitive but not 4-arc-transitive.

Exercise 8

Let G be a Cayley graph of an abelian group. Prove that G is not 4-arc-transitive unless G is a cycle.

A graph G is said to be G-locally-primitive if G £ Aut G acts transitive on VG and G_a acts primitively on G(a).

Lemma 9 Let G be a G-locally-primitive graph. Then for any intransitive normal subgroup N of G, either N has exactly two orbits in VG and G_N @ K₂, or G is a cover of G_N, G_N is (G/N)-locally-primitive, and G/N £ Aut G_N.

PROOF. Let B be the set of N-orbits in VG, and let K be the kernel of G acting on B. Then N £ K, and K\lhd G. Thus K_a\lhd G_a, where a Î VG. Since G is (G,2)-arc-transitive, G_a acts 2-transitively on the neighborhood G(a). So K_a acts on G(a) either trivially or transitively. Suppose that K_a ¹ 1. It then follows that K_a acts non-trivially on G(a), so that K_a acts on G(a) transitively. Thus the valency of G_N is equal to 1, and so G_N @ K₂, which is a contradiction since N has at least 3 orbits in V. Therefore, K_a = 1, that is, K acts semiregularly on V. In particular, K = N, that is, N is the kernel of G acting on V. Hence G/N may be identified with a subgroup of Aut G_N, and so G_N is (G/N)-locally-primitive. ^[¯]

Perhaps the most important property of taking normal quotients of graphs is that the s-arc-transitivity of a graph is inherited by normal quotients.

Theorem 10 (Praeger 1992) Let G be a connected (G,s)-arc-transitive graph for some s ³ 2. Assume that N is a normal subgroup of G which has at least three orbits in V. Then the normal quotient G_N is a (G/N,s)-arc transitive graph.

PROOF. Let B₀,B₁,...,B_s and C₀,C₁,...,C_s be two s-arcs of the normal quotient graph G_N. Then for each i with 0 £ i £ s-1, B_i is adjacent to B_i+1 and C_i is adjacent to C_i+1, in G_N. By Lemma 5.7, there exist u₀,u₁,...,u_s and v₀,v₁,...,v_s such that for each i Î {0,1,...,s-1}, u_i Î B_i is adjacent to u_i+1 Î B_i+1, and v_i Î C_i adjacent to v_i+1 Î C_i+1. Since G is (G,s)-arc-transitive, there exists g Î G such that u_i^g = v_i for all i Î {0,1,...,s}. Since B is G-invariant, we have B_i^g = C_i, and hence g maps the s-arc: B₀,B₁,...,B_s to the s-arc: C₀,C₁,...,C_s. Thus G induces a transitive action on the set of s-arcs of G_N. By Lemma 5.9, G/N may be identified with a subgroup of Aut G_N. ^[¯]

Exercise 11

Let G = Cay(G,S) be connected and undirected. Assume that Aut(G,S) is 2-transitive on S. Prove

(i) G is 2-arc-transitive,


(ii) all elements of S have order 2,


(iii) if in addition G is abelian, then G is an elementary abelian 2-group.

Theorem 5.10 suggests to study `minimal' s-arc-transitive graphs,that is, s-arc-transitive graphs which have no non-trivial normal quotients.

Let G be connected and undirected. Suppose that G is (G,s)-arc-transitive for some G £ Aut G, and assume further that G is a minimal s-arc-transitive graph with respect to G. Then either

(1) each non-trivial normal subgroup of G is transitive on VG, that is, G is quasiprimitive on VG; or


(2) some non-trivial normal subgroup of G has exactly two orbits in VG, that is, G is bi-quasiprimitive on VG.

5.5  Quasiprimitive 2-arc-transitive graphs

Let G be a quasiprimitive permutation group on W, and let N = soc(G), the socle of G. Let M₁,...,M_k be all minimal normal subgroups of G. It is easily shown that

N = M1×...×Mk,

for some k ³ 1.

Suppose that k ³ 2. Then since M_i is transitive, we have that M_i is nonabelian. Let L = M₂×...×M_k. Then N = M₁×L. Since M₁ is transitive on W, for any b Î W, there exists x Î M₁ such that b = a^x. Therefore,

Lb = Lax = x-1Lax = La,

so that L_a fixes all points of W. Hence L_a = 1. As L is transitive on W, we obtain that L is regular. Since each M_i is transitive, it follows that L = M₂ and k = 2. Similarly, M₁ is regular on W. Therefore, N = M₁×M₂ such that M_i is nonabelian and regular on W; in particular, |M₁| = |M₂| = |W|.

Since N is transitive on W, it follows that |N_a| = |M₁|. An element of N_a may be written as xx¢, where x Î M₁ and x¢ Î M₂. Suppose that for some x Î M₁, there exist two different elements x¢,y¢ Î M₂ such that xx¢, xy¢ Î N_a. Then M₂ has a non-identity element x¢(y¢)^-1 = xx¢(xy¢)^-1 Î N_a, which is a contradiction since M₂ is regular on W. Further, since |N_a| = |M₁|, for each element x Î M₁, there exists exactly one element x¢ Î M₂ such that xx¢ Î N_a. Let s be a map from M₁ to M₂ defined:

x® x¢,   where x Î M1 and xx¢ Î Na.

Then it is easily shown that s is an isomorphism from M₁ to M₂. In particular, M₁ @ M₂. Thus we have

Lemma 12 Let G be a quasiprimitive permutation group on W. Then either soc(G) is a minimal normal subgroup of G, or soc(G) = M₁×M₂ such that M₁ @ M₂, and the M_i are nonabelian and regular on W.

The next lemma characterizes minimal normal subgroups of a group.

Lemma 13 If M is a minimal normal subgroup of a group G, then M = T₁×...×T_k such that T₁ @ ... @ T_k is a simple group.

In particular, if G is a quasiprimitive permutation group, then soc(G) = T₁×...×T_l @ T, where l ³ 1 and T₁ @ ... @ T_l is a simple group. Quasiprimitive permutation groups G are categorized into 8 types by O'Nan-Scott's theorem (Praeger 1992), where N = soc(G):

• N is abelian  (HA),

• N is non-abelian,
  • N = M₁×M₂,
    • M_i is simple  (HS),

    • M_i is non-simple  (HC),

  • N is a minimal normal subgroup of G,
    • N is regular  (TW),

    • N is non-regular,
      • N is simple  (AS),

      • N is non-simple,
        
        $\bullet$ N_a\not @ T^r  (PA),

        
        $\bullet$ N_a @ T^r,

        
        - r = 1  (SD),

        
        - r > 1  (CD).

Theorem 14 (Praeger 1992) Let G be a connected undirected graph, and assume further that G £ Aut G is quasiprimitive on VG and that G is (G,2)-arc-transitive. Then G is of type HA, TW, AS or PA.