Edge-primitive graphs

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 G\leqslant Aut(\Gamma) acts primitively on the set of edges of a connected graph \Gamma. If G is not transitive on vertices then \Gamma is the star K_{1,n}. If  G is vertex-transitive but not arc-transitive then \Gamma 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 \Gamma. 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),
  • \Gamma is a spread of another G-edge-primitive graph \Sigma which is G-locally primitive (that is,  for each vertex v of \Gamma, the vertex stabiliser  G_v acts transitively on the set of vertices of \Gamma adjacent to  v ).

Given a graph \Gamma with partition \mathcal{B} of the vertices, the quotient graph of \Gamma with respect to \mathcal{B} is the graph with vertex set the parts of \mathcal{B} and two parts  B, C are adjacent if there exists v\in B and w\in C such that v is adjacent to C in \Gamma. We say that \Gamma is a spread of  \Gamma_{\mathcal{B}} if  \{v,w\} is the only edge of \Gamma 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 \mathrm{soc}(G)=\mathrm{PSL}(2,q). We see that either \Gamma 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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Up ↑

%d bloggers like this: