Graph symmetry II

October 23, 2010

In my previous post I discussed various measures of symmetry of the vertex set of a graph. The main terms introduced were vertex-transitive, vertex-primitive, vertex-quasiprimitive, vertex-biprimitive and vertex-biquasiprimitive. It was also seen that the class of vertex-transitive graphs was very large and so we often place further symmetry conditions on our graphs so that we can obtain interesting results. In this post I wish to discuss conditions on the symmetry of the edge set ${E\Gamma}$ and arc set ${A\Gamma}$ .

A graph ${\Gamma}$ is called edge-transitive if ${\mathrm{Aut}(\Gamma)}$ acts transitively on the set of edges of ${\Gamma}$ and is called arc-transitive if ${\mathrm{Aut}(\Gamma)}$ acts transitively on the set of arcs. As long as there are no isolated vertices (that is vertices with no neighbours) then an arc-transitive graph will also be vertex-transitive and edge-transitive. Such graphs are often called symmetric.

I will first discuss how to construct all arc-transitive graphs. Let ${G}$ be a transitive permutation group on a set ${\Omega}$ . The orbits of ${G}$ on ${\Omega\times\Omega}$ are called orbitals. An orbital ${\mathcal{O}}$ is called self-paired if for all ${(\alpha,\beta)\in \mathcal{O}}$ the element ${(\beta,\alpha)}$ also lies in ${\mathcal{O}}$ . This is equivalent to there being an element ${g\in G}$ that interchanges ${\alpha}$ and ${\beta}$ . For each self-paired orbital we can construct a graph ${\Gamma}$ with vertex set ${\Omega}$ and edges ${\{\alpha,\beta\}}$ for all ${(\alpha,\beta)\in \mathcal{O}}$ . The group ${G}$ is an arc-transitive group of automorphisms of ${\Gamma}$ . Moreover, all arc-transitive graphs arise in this way.

The orbitals of ${G}$ correspond to the orbits of ${G_{\alpha}}$ on ${\Omega}$ . These orbits are called suborbits and we call a suborbit self-paired if its corresponding orbital is self-paired. The length of the suborbit is equal to the valency of the corresponding orbital graph. Thus studying arc-transitive graphs of valency ${d}$ is the same as the study of transitive permutation groups with a self-paired suborbit of size ${d}$ .

If we assume that an arc-transitive graph is also vertex-primitive then it is possible to deduce a few things. The Sim’s conjecture (proved by Cameron, Praeger, Saxl and Seitz with the aid of the Classification of Finite Simple Groups) states that there exists a function ${f}$ such that given a primitive group ${G}$ with a suborbit of size ${d}$ , the order of the point stabiliser ${G_{\alpha}}$ has order at most ${f(d)}$ . So the order of a vertex stabiliser for a vertex-primitive, arc-transitive graph is bounded. This gives us some hope of classifying all vertex-primitive, arc-transitive graphs of a given valency. Indeed in 1967, Wong showed that there is one infinite family and 4 sporadic examples of vertex-primitive, arc-transitive graphs of valency 3. More recently in 2004, Cai Heng Li, Zai Ping Lu and Dragan Marusi\v{c} showed that there are 5 infinite families and 5 sporadic examples of vertex-primitive, arc-transitive graphs of valency 4.

Now not every edge-transitive and vertex-transitive graph is also arc-transitive. Edge-transitive, vertex-transitive but not arc-transitive graphs are called half-arc-transitive or sometimes half-transitive. Such graphs have been the focus of a large amount of research. The smallest one is the Holt graph on 27 vertices and valency 4. Half-arc-transitive graphs must have even valency and in 1970, Bouwer showed that one exists for every even valency ${d\geq 4}$ . Given a transitive group ${G}$ with a nonself-paired orbital we can construct a graph ${\Gamma}$ upon which ${G}$ is vertex- and edge-transitive but not arc-transitive on ${\Gamma}$ by taking the edges to the be pairs ${\{\alpha,\beta\}}$ such that ${(\alpha,\beta)}$ or ${(\beta,\alpha)}$ lies in the orbital. However, ${G}$ may not be the full automorphism group of ${\Gamma}$ and so ${\Gamma}$ may be arc-transitive. Thus finding half-arc-transitive graphs is more complicated than just finding transitive groups with a nonself-paired orbital.

Whereas every connected arc-transitive graph is vertex-transitive, not every edge-transitive graph is vertex-transitive. For example, the Gray graph. If a graph is edge- but not vertex-transitive then the automorphism group has two orbits on vertices and the graph is bipartite with the two bipartite halves being the two orbits. Such graphs need not be regular but if they are we call them semisymmetric. The Gray graph is semisymmetric. Again semisymmetric graphs have been a focus of much investigation and are comparatively rare. Ivanov and Iofinova determined all semisymmetric graphs of valency three whose automorphism group acts primitively on each of its orbits on vertices in 1985. There are only 6 such graphs.

Every edge-transitive bipartite graph can be constructed as follows: Let ${G}$ be a group with subgroups ${L}$ and ${R}$ . The vertices will be the cosets of ${L}$ in ${G}$ and the cosets of ${R}$ in ${G}$ . The edges are the pairs ${\{Lx,Ry\}}$ such that ${Lx\cap Ry\neq \varnothing}$ . The group ${G}$ acts by right multiplication on both sets of cosets and maps edges to edges so induces a group of automorphisms of ${\Gamma}$ that has two orbits on vertices. Moreover, ${G}$ is edge-transitive since if ${g\in Lx\cap Ry}$ then ${g}$ maps the edge ${\{L,R\}}$ to ${\{Lx,Ry\}}$ . Now not all automorphisms of ${\Gamma}$ may be induced by ${G}$ . Indeed if ${\Gamma}$ is regular there are often automorphisms that interchange the bipartite halves. Trying to prevent the existence of such automorphisms is what makes it harder to construct semisymmetric graphs.

I can now give the Venn diagram for this post.

To end this post I will say a few words about local symmetry properties. Given some symmetry propery ${X}$ , we say that a graph ${\Gamma}$ is locally ${X}$ if for each vertex ${v}$ , the vertex stabiliser ${\mathrm{Aut}(\Gamma)_v}$ has property ${X}$ in its action on the set ${\Gamma(x)}$ of neighbours of ${x}$ . For example, we say that a graph ${\Gamma}$ is locally transitive if for all vertices ${v}$ , ${\mathrm{Aut}(\Gamma)_v}$ acts transitively on ${\Gamma(v)}$ . If ${\Gamma}$ is connected then every locally transitive graph is edge-transitive. Not every edge-transitive graph is locally transitive, for example half-arc-transitive graphs are edge-transitive but not locally transitive.

Another useful local property is being locally primitive. This property is important when studying quotients of graphs. Moreover, since any transitive group on a prime number of points is primitive, any arc-transitive graph of prime valency is locally primitve.

Given a graph ${\Gamma}$ and a partition ${\mathcal{B}}$ of the vertex set then the quotient graph ${\Gamma_{\mathcal{B}}}$ is the graph with vertex set the parts of ${\mathcal{B}}$ and two parts ${B_1,B_2}$ are adjacent if there exists ${v_1\in B_1}$ and ${v_2\in B_2}$ such that ${v_1}$ and ${v_2}$ are adjacent in ${\Gamma}$ . If ${\mathcal{B}}$ is preserved by ${\mathrm{Aut}(\Gamma)}$ then ${\mathrm{Aut}(\Gamma)}$ induces automorphisms of ${\mathcal{B}}$ . Moreover, if ${\Gamma}$ is locally primitive then ${\Gamma}$ is a cover of ${\Gamma_{\mathcal{B}}}$ , that is for each pair of adjacent parts of the partition the subgraph of ${\Gamma}$ induced between them is a perfect matching. This implies that ${\Gamma_{\mathcal{B}}}$ has the same valency as ${\Gamma}$ . Furthermore, the covering property often implies that a family of graphs in preserved under the quotienting operation, that is ${\Gamma_{\mathcal{B}}}$ inherits particular symmetry properties of ${\Gamma}$ . This provides a strategy for studying the orginal family, that is, first study all “basic graphs” in the family (those with no meaningful quotients) and then study how to lift these basic graphs to other graphs in the family.

Vertex-transitive, locally quasiprimitive graphs have received some attention (particularly in a paper by Cai Heng Li, Cheryl Praeger, Akshay Venkatesh and Sanming Zhou). The quotienting process for these graphs is not quite as advantageous as here ${\Gamma}$ is merely a multicover of ${\Gamma_{\mathcal{B}}}$ , that is, instead of a perfect matching between adjacent blocks we get a regular bipartite graph.

I plan one more post in this series where I will discuss some of the more restrictive graph symmetry properties such as distance-transitive and ${s}$ -arc transitive.

Like this:

Be the first to like this post.

No comments yet

	Peter Cameron on Science without stats
	Michael Giudici on Symmetries of Discrete Ob…
	Gordon Royle on Symmetries of Discrete Ob…
	Gordon Royle on Science without stats
	John Bamberg on Science without stats

just another maths blog

Graph symmetry II

Like this:

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Tags

Categories

Blogroll

Feeds

Visitors

Follow “SymOmega”