I have just finished reading the proofs for my paper `On finite edge-primitive and edge-quasiprimitive graphs’ with Cai Heng Li which has just been accepted in JCTB. This paper has been a long time in the making as Li and I started the work in 2002! Usually when I submit a paper to a journal I put a preprint up on my research web page but I should really start uploading them also to the arxiv so I have just done so and it is now available there.
A graph is called edge-primitive if its automorphism group acts primitively on the set of edges. Many famous graphs such as the Heawood graph, Tutte-Coxeter graph, Hoffman-Singleton graph and Higman-Sims graph are edge-primitive. The paper begins a systematic study of edge-primitive and edge-quasiprimitive graphs by analysing the possible actions on vertices and edges.
Suppose acts primitively on the set of edges of a connected graph . If G is not transitive on vertices then is the star . If G is vertex-transitive but not arc-transitive then is as cycle of prime length p and G is the cyclic group of order p. Thus we may suppose that G is transitive on the set of arcs of . We are then able to show that one of the following holds:
- G is primitive on vertices,
- G is biprimitive on vertices (that is, the only system of imprimitivity is the bipartition),
- is a spread of another G-edge-primitive graph which is G-locally primitive (that is, for each vertex v of , the vertex stabiliser acts transitively on the set of vertices of adjacent to v ).
Given a graph with partition of the vertices, the quotient graph of with respect to is the graph with vertex set the parts of and two parts B, C are adjacent if there exists and such that v is adjacent to C in . We say that is a spread of if is the only edge of between vertices of B and C.
The above result leads to an O’Nan-Scott style analysis of the types of edge and vertex actions. We investigate what the vertex action must be if the action on edges is of a given primitive type. We are able to show that the main ones to study are where G is primitive on edges of almost simple or product action type and the action on vertices is either primitive of the same type or biprimitive with the two actions on the bipartite half being primitive of the same type as on edges (Theorem 1.2). Other types of actions can occur but we give a generic construction in such cases. We also do an analysis in the edge-quasiprimitive case.
It appears feasible to determine all edge-primitive graphs for certain almost simple groups. The paper makes a start in this direction by determining all G-edge-primitive graphs with . We see that either is a complete bipartite graph, one of eight exceptional graphs or in one of two infinite families. The exceptional graphs include the Heawood graph, the Tutte-Coxeter graph and the Biggs-Smith graph.