## A census of cubic vertex-transitive graphs

Gabriel Verret (Primorska), P. Potoˇcnik and P. Spiga

Queenstown, February 16th, 2012 (SODO)

## Vertex-transitive graphs

All graphs considered will be finite and simple (undirected, loopless, no multiple edges).

A graph Γ is calledvertex-transitive ifAut(Γ) acts transitively on V(Γ) (and G-vertex-transitiveifG ≤Aut(Γ) acts

transitively onV(Γ)).

WLOG, we may assume connectedness.

## Vertex-transitive graphs

All graphs considered will be finite and simple (undirected, loopless, no multiple edges).

A graph Γ is calledvertex-transitive ifAut(Γ) acts transitively on V(Γ) (and G-vertex-transitiveifG ≤Aut(Γ) acts

transitively onV(Γ)).

WLOG, we may assume connectedness.

## Vertex-transitive graphs

All graphs considered will be finite and simple (undirected, loopless, no multiple edges).

A graph Γ is calledvertex-transitive ifAut(Γ) acts transitively on V(Γ) (and G-vertex-transitiveifG ≤Aut(Γ) acts

transitively onV(Γ)).

WLOG, we may assume connectedness.

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!) Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

Using some new theoretical results and a few tricks, we construced all cubic vertex-transitive graphs of order at most1280.

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!)

Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

Using some new theoretical results and a few tricks, we construced all cubic vertex-transitive graphs of order at most1280.

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!) Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

Using some new theoretical results and a few tricks, we construced all cubic vertex-transitive graphs of order at most1280.

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!) Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

## Three natural cases

Let Γ be a cubicG-vertex-transitive graph and letm bethe number
of orbitsof Gv^{Γ(v)} (the permutation group induced by the action of
a vertex-stabiliserGv in its action on the neighbourhood Γ(v)).

By vertex-transitivity,m is equal to the number of orbits ofG in its action on the arcs of Γ (anarc is an ordered pair of adjacent vertices).

Since Γ is cubic,m∈ {1,2,3}.

We deal with each of these separately.

## Three natural cases

Let Γ be a cubicG-vertex-transitive graph and letm bethe number
of orbitsof Gv^{Γ(v)} (the permutation group induced by the action of
a vertex-stabiliserGv in its action on the neighbourhood Γ(v)).

By vertex-transitivity,m is equal to the number of orbits ofG in its action on the arcs of Γ (anarc is an ordered pair of adjacent vertices).

Since Γ is cubic,m∈ {1,2,3}.

We deal with each of these separately.

## Three natural cases

Let Γ be a cubicG-vertex-transitive graph and letm bethe number
of orbitsof Gv^{Γ(v)} (the permutation group induced by the action of
a vertex-stabiliserGv in its action on the neighbourhood Γ(v)).

By vertex-transitivity,m is equal to the number of orbits ofG in its action on the arcs of Γ (anarc is an ordered pair of adjacent vertices).

Since Γ is cubic,m∈ {1,2,3}.

We deal with each of these separately.

## Three natural cases

^{Γ(v)} (the permutation group induced by the action of
a vertex-stabiliserGv in its action on the neighbourhood Γ(v)).

Since Γ is cubic,m∈ {1,2,3}.

We deal with each of these separately.

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare
known (the structure ofGv and G_{{}uv}).

To find all the graphs up to a certain order, it suﬃces to :

� Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

� Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare
known (the structure ofGv and G_{{}uv}).

To find all the graphs up to a certain order, it suﬃces to :

� Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

� Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare
known (the structure ofGv and G_{{uv}_{}}).

To find all the graphs up to a certain order, it suﬃces to :

� Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

� Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare
known (the structure ofGv and G_{{uv}_{}}).

To find all the graphs up to a certain order, it suﬃces to :

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare
known (the structure ofGv and G_{{uv}_{}}).

To find all the graphs up to a certain order, it suﬃces to :

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

_{{uv}_{}}).

To find all the graphs up to a certain order, it suﬃces to :

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

_{{uv}_{}}).

To find all the graphs up to a certain order, it suﬃces to :

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

## m = 3 (Cayley graphs)

Ifm= 3, thenGv = 1 andG acts regularly on the vertex-set.

In particular,|G| ≤1280 and Γ∼=Cay(G,S) is a Cayley graph for G.

Naive method : consider all groupsG of order at most 1280 and, for eachG, all possible3-connection sets.

Computationally infeasible.

## m = 3 (Cayley graphs)

Ifm= 3, thenGv = 1 andG acts regularly on the vertex-set.

In particular,|G| ≤1280 and Γ∼=Cay(G,S) is a Cayley graph for G.

Naive method : consider all groupsG of order at most 1280 and, for eachG, all possible3-connection sets.

Computationally infeasible.

## m = 3 (Cayley graphs)

Ifm= 3, thenGv = 1 andG acts regularly on the vertex-set.

In particular,|G| ≤1280 and Γ∼=Cay(G,S) is a Cayley graph for G.

Naive method : consider all groupsG of order at most 1280 and, for eachG, all possible 3-connection sets.

Computationally infeasible.

## m = 3 (Cayley graphs)

Ifm= 3, thenGv = 1 andG acts regularly on the vertex-set.

In particular,|G| ≤1280 and Γ∼=Cay(G,S) is a Cayley graph for G.

Naive method : consider all groupsG of order at most 1280 and, for eachG, all possible 3-connection sets.

Computationally infeasible.

## A few tricks

Lemma

G/G^{�} is isomorphic to one ofZ^{3}2,Z^{2}×Z^{r}, or Z^{r}.

Reduces drastically the number of groups we need to consider. Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then
Cay(G,S)∼=Cay(G,S^{φ}).

Only need to consider connection setsup to conjugacy in Aut(G). These simple tricks are enough to make them= 3 case

computationally feasible, except whenG has order 512 or 1024 (too many groups).

## A few tricks

Lemma

G/G^{�} is isomorphic to one ofZ^{3}2,Z^{2}×Z^{r}, or Z^{r}.

Reduces drastically the number of groups we need to consider.

Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then
Cay(G,S)∼=Cay(G,S^{φ}).

Only need to consider connection setsup to conjugacy in Aut(G). These simple tricks are enough to make them= 3 case

computationally feasible, except whenG has order 512 or 1024 (too many groups).

## A few tricks

Lemma

G/G^{�} is isomorphic to one ofZ^{3}2,Z^{2}×Z^{r}, or Z^{r}.

Reduces drastically the number of groups we need to consider.

Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then
Cay(G,S)∼=Cay(G,S^{φ}).

Only need to consider connection setsup to conjugacy in Aut(G). These simple tricks are enough to make them= 3 case

computationally feasible, except whenG has order 512 or 1024 (too many groups).

## A few tricks

Lemma

G/G^{�} is isomorphic to one ofZ^{3}2,Z^{2}×Z^{r}, or Z^{r}.

Reduces drastically the number of groups we need to consider.

Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then
Cay(G,S)∼=Cay(G,S^{φ}).

Only need to consider connection setsup to conjugacy in Aut(G).

These simple tricks are enough to make them= 3 case computationally feasible, except whenG has order 512 or 1024 (too many groups).

## A few tricks

Lemma

G/G^{�} is isomorphic to one ofZ^{3}2,Z^{2}×Z^{r}, or Z^{r}.

Reduces drastically the number of groups we need to consider.

Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then
Cay(G,S)∼=Cay(G,S^{φ}).

Only need to consider connection setsup to conjugacy in Aut(G).

These simple tricks are enough to make them= 3 case computationally feasible, except whenG has order 512 or 1024 (too many groups).

## 2-groups

Forn a power of 2, let Rn be the class of groups which have order n and admit a generating set consisting of3 involutionsor of 2 elements, one of which is an involution.

Lemma

Let G ∈R_{2}^{i+1} and let C be a central subgroup of G of order 2.
Then G/C ∈R_{2}^{i}.

Using this Lemma, we can constructRi by induction on i. (Repeated central extensions.)

Once we have constructedR512 and R1024, we apply to the groups in these classes the same procedure which we used for other orders.

## 2-groups

Forn a power of 2, let Rn be the class of groups which have order n and admit a generating set consisting of3 involutionsor of 2 elements, one of which is an involution.

Lemma

Let G ∈R_{2}^{i+1} and let C be a central subgroup of G of order 2.

Then G/C ∈R_{2}^{i}.

Using this Lemma, we can constructRi by induction on i. (Repeated central extensions.)

Once we have constructedR512 and R1024, we apply to the groups in these classes the same procedure which we used for other orders.

## 2-groups

Forn a power of 2, let Rn be the class of groups which have order n and admit a generating set consisting of3 involutionsor of 2 elements, one of which is an involution.

Lemma

Let G ∈R_{2}^{i+1} and let C be a central subgroup of G of order 2.

Then G/C ∈R_{2}^{i}.

Using this Lemma, we can constructRi by induction on i.

(Repeated central extensions.)

Once we have constructedR512 and R1024, we apply to the groups in these classes the same procedure which we used for other orders.

## 2-groups

Lemma

Let G ∈R_{2}^{i+1} and let C be a central subgroup of G of order 2.

Then G/C ∈R_{2}^{i}.

Using this Lemma, we can constructRi by induction on i.

(Repeated central extensions.)

## m = 2

The most diﬃcult case. The main problem in this case is that a vertex-stabiliser can be arbitrarily large. (In fact, very large with respect to|V(Γ)|).

Note thatGv fixes a unique neighbour ofv. This induces a perfect matchingin Γ.

We define an auxiliary graph, which is 4-valent,G-arc-transitive and has half the order. We also get aG-arc-transitive cycle decomposition of this new graph.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions. By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

## m = 2

The most diﬃcult case. The main problem in this case is that a vertex-stabiliser can be arbitrarily large. (In fact, very large with respect to|V(Γ)|).

Note thatGv fixes a unique neighbour ofv. This induces aperfect matchingin Γ.

We define an auxiliary graph, which is 4-valent,G-arc-transitive and has half the order. We also get aG-arc-transitive cycle decomposition of this new graph.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions. By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

## m = 2

The most diﬃcult case. The main problem in this case is that a vertex-stabiliser can be arbitrarily large. (In fact, very large with respect to|V(Γ)|).

Note thatGv fixes a unique neighbour ofv. This induces aperfect matchingin Γ.

We define an auxiliary graph, which is 4-valent,G-arc-transitive and has half the order. We also get aG-arc-transitive cycle decomposition of this new graph.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions. By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

## m = 2

Note thatGv fixes a unique neighbour ofv. This induces aperfect matchingin Γ.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions.

By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

## m = 2

Note thatGv fixes a unique neighbour ofv. This induces aperfect matchingin Γ.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions.

By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

## 4-valent arc-transitive graphs

Because Γ admits an arc-transitive cycle-decomposition, we have
Gv^{Γ(v)} ∼=Z^{4},Z^{2}2 or D_{4}.

IfGv^{Γ(v)} ∼=Z^{4} or Z^{2}2, then |Gv|= 4 and we can use the amalgam
method.

(In the caseGv^{Γ(v)} ∼=Z^{2}2, these correspond to maps and were
provided by Conder.)

Otherwise,Gv^{Γ(v)} ∼=D4 (and|Gv|can be arbitrarily large).
We characterised the graphs for which|Gv|is “very large” with
respect to the the order of the graph.

## 4-valent arc-transitive graphs

Because Γ admits an arc-transitive cycle-decomposition, we have
Gv^{Γ(v)} ∼=Z^{4},Z^{2}2 or D_{4}.

IfGv^{Γ(v)} ∼=Z4 or Z^{2}2, then |Gv|= 4 and we can use the amalgam
method.

(In the caseGv^{Γ(v)} ∼=Z^{2}2, these correspond to maps and were
provided by Conder.)

Otherwise,Gv^{Γ(v)} ∼=D4 (and|Gv|can be arbitrarily large).
We characterised the graphs for which|Gv|is “very large” with
respect to the the order of the graph.

## 4-valent arc-transitive graphs

Because Γ admits an arc-transitive cycle-decomposition, we have
Gv^{Γ(v)} ∼=Z^{4},Z^{2}2 or D_{4}.

IfGv^{Γ(v)} ∼=Z4 or Z^{2}2, then |Gv|= 4 and we can use the amalgam
method.

(In the caseGv^{Γ(v)} ∼=Z^{2}2, these correspond to maps and were
provided by Conder.)

Otherwise,Gv^{Γ(v)} ∼=D4 (and|Gv|can be arbitrarily large).
We characterised the graphs for which|Gv|is “very large” with
respect to the the order of the graph.

## 4-valent arc-transitive graphs

^{Γ(v)} ∼=Z^{4},Z^{2}2 or D_{4}.

IfGv^{Γ(v)} ∼=Z4 or Z^{2}2, then |Gv|= 4 and we can use the amalgam
method.

(In the caseGv^{Γ(v)} ∼=Z^{2}2, these correspond to maps and were
provided by Conder.)

Otherwise,Gv^{Γ(v)} ∼=D_{4} (and|Gv|can be arbitrarily large).

We characterised the graphs for which|Gv|is “very large” with respect to the the order of the graph.

## 4-valent arc-transitive graphs

^{Γ(v)} ∼=Z^{4},Z^{2}2 or D_{4}.

IfGv^{Γ(v)} ∼=Z4 or Z^{2}2, then |Gv|= 4 and we can use the amalgam
method.

(In the caseGv^{Γ(v)} ∼=Z^{2}2, these correspond to maps and were
provided by Conder.)

Otherwise,Gv^{Γ(v)} ∼=D_{4} (and|Gv|can be arbitrarily large).

We characterised the graphs for which|Gv|is “very large” with respect to the the order of the graph.

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

� Γ∼=C(r,s),

� (Γ,G)is one of 18 exceptions,

� |VΓ| ≥2|Gv|log_{2}(|Gv|/2). Moreover, the graphs for which
equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG. Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”.
TheD_{4} amalgams were determined by Djokovi´c.

This allows us to use the amalgam method (construct the amalgams and find all normal subgroups up to a certain index).

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

� Γ∼=C(r,s),

� (Γ,G)is one of 18 exceptions,

� |VΓ| ≥2|Gv|log_{2}(|Gv|/2). Moreover, the graphs for which
equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”.
TheD_{4} amalgams were determined by Djokovi´c.

This allows us to use the amalgam method (construct the amalgams and find all normal subgroups up to a certain index).

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

� Γ∼=C(r,s),

� (Γ,G)is one of 18 exceptions,

� |VΓ| ≥2|Gv|log_{2}(|Gv|/2). Moreover, the graphs for which
equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”.

TheD_{4} amalgams were determined by Djokovi´c.

This allows us to use the amalgam method (construct the amalgams and find all normal subgroups up to a certain index).

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

� Γ∼=C(r,s),

� (Γ,G)is one of 18 exceptions,

� |VΓ| ≥2|Gv|log_{2}(|Gv|/2). Moreover, the graphs for which
equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”.

TheD_{4} amalgams were determined by Djokovi´c.

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

� Γ∼=C(r,s),

� (Γ,G)is one of 18 exceptions,

� |VΓ| ≥2|Gv|log_{2}(|Gv|/2). Moreover, the graphs for which
equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”.

TheD_{4} amalgams were determined by Djokovi´c.

## Census complete!

To avoid memory issues when running

LowIndexNormalSubgroups, we sometimes need to do some theoretical analysis and “split” the amalgam into cases by adding certain relations.

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

Side note : by combining our data with the census of small 2-arc-transitive 4-valent graphs (Potoˇcnik), we get all 4-valent arc-transitive graphs of order at most 640.

## Census complete!

To avoid memory issues when running

LowIndexNormalSubgroups, we sometimes need to do some theoretical analysis and “split” the amalgam into cases by adding certain relations.

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

Side note : by combining our data with the census of small 2-arc-transitive 4-valent graphs (Potoˇcnik), we get all 4-valent arc-transitive graphs of order at most 640.

## Census complete!

To avoid memory issues when running

LowIndexNormalSubgroups, we sometimes need to do some theoretical analysis and “split” the amalgam into cases by adding certain relations.

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

Side note : by combining our data with the census of small 2-arc-transitive 4-valent graphs (Potoˇcnik), we get all 4-valent arc-transitive graphs of order at most 640.

## Census complete!

To avoid memory issues when running

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

## Census complete!

To avoid memory issues when running

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

## Number of graphs of order up to n

In gray is the graph of the functionn�→n^{2}/15. In an upcoming
paper, we prove that log(f(n))∈Θ((logn)^{2}).

## Number of graphs of order up to n

In gray is the graph of the functionn�→n^{2}/15. In an upcoming
paper, we prove that log(f(n))∈Θ((logn)^{2}).

## Graphs of order at most 1280 by type

m= 1 m= 2 m= 3 Total Cayley 386 11853 97687 109926

Non-Cayley 96 1338 0 1434

Total 482 13191 97687 111360

Most graphs are Cayley and most of those are GRRs. This seems to be part of a trend.

## Graphs of order at most 1280 by type

m= 1 m= 2 m= 3 Total Cayley 386 11853 97687 109926

Non-Cayley 96 1338 0 1434

Total 482 13191 97687 111360

Most graphs are Cayley and most of those are GRRs.

This seems to be part of a trend.

## Graphs of order at most 1280 by type

m= 1 m= 2 m= 3 Total Cayley 386 11853 97687 109926

Non-Cayley 96 1338 0 1434

Total 482 13191 97687 111360

Most graphs are Cayley and most of those are GRRs.

This seems to be part of a trend.

## Proportion of graphs of diﬀerent types

It is conjectured that almost all vertex-transitive graphs are Cayley (McKay and Praeger). It seems reasonable to conjecture that this is also true for any given valencyk ≥3.

## Proportion of graphs of diﬀerent types

It is conjectured that almost all vertex-transitive graphs are Cayley (McKay and Praeger). It seems reasonable to conjecture that this is also true for any given valencyk ≥3.

## Proportion of graphs of diﬀerent types

It is conjectured that almost all vertex-transitive graphs are Cayley (McKay and Praeger). It seems reasonable to conjecture that this is also true for any given valencyk ≥3.

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Asymptotic enumeration of k-valent vertex-transitive graphs (arc-transitive graphs, Cayley graphs, GRRs).

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs? Challenge

Census of4-valent vertex-transitive graphs of order up to 200? 300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Asymptotic enumeration of k-valent vertex-transitive graphs (arc-transitive graphs, Cayley graphs, GRRs).

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs? Challenge

Census of4-valent vertex-transitive graphs of order up to 200? 300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Asymptotic enumeration of k-valent vertex-transitive graphs (arc-transitive graphs, Cayley graphs, GRRs).

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs?

Challenge

Census of4-valent vertex-transitive graphs of order up to 200? 300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs?

Challenge

Census of4-valent vertex-transitive graphs of order up to 200?

300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs?

Challenge

Census of4-valent vertex-transitive graphs of order up to 200?

300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/