This is a text file explaining the Census of all connected arc-transitive digraphs of out-valence and in-valence 2 on at most 1.000 vertices.
It turns out that there are 26457 such digraphs.
More information on how the census was obtained and about the meaning of the parameters in the csv files can be found in the paper:
P. Potocnik, P. Spiga, G. Verret, "A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two", Ars Mathematica Contemporanea, special issue for 60th birthday of Dragan Marušič vol. 8 (2015)
If you use the census for academic purposes, you should acknowledge its use by citing this paper. If you use the census for commercial purposes, contact one of the authors by email. Any unauthorised use of the census for commercial purposes without prior consent of the authors is prohibited.
Besides the file "Census-ATD-1k-README.txt" file, there are 9 more files included in this package:
Census-ATD-1k.mgm
Census-ATD-1k.txt
Census-ATD-1k-data.csv
Census-GHAT-1k.mgm
Census-GHAT-1k.txt
Census-GHAT-1k-data.csv
Census-HAT-1k.mgm
Census-HAT-1k.txt
Census-HAT-1k-data.csv
The first three files are about the arc-transitive digraphs.
Connected balanced arc-transitive digraphs of out-valence 2 can be of two type: generalized wreath digraphs, GWDs for short, and those that are not GWDs. For the definition of the GWDs, see the paper mentioned above. The GWDs are denoted by GWD(m,k) where m and k are positive integers, m at least 3, k at most m-1. The digraph GWD(m,k) has m*2^k vertices and the full automorphism group G of order m*2^m. The vertex-stabiliser G_v is elementary abelian of order 2^(m-k). Since these groups tend to be very large, generalized wreath digraphs are very difficult to handle computationally whenever the computations involve the automorphism group.
There is 25496 non-GWDs and 961 GWDs, all together 26457 connected arc-transitive digraphs of in-valence and out-valence 2 on up to 1.000 vertices.
The file "Census-ATD-1k.mgm" is a magma file, which, upon loading, creates a double sequence ATD of length 1.000, where ATD[n,i] contains the i-th non-generalised-wreath digraph of order n. In the literature, we'll call this digraph simply ATD[n,i]. For example ATD[9,1] is the unique dart-transitive digraph with 9 vertices. It also builds the double list GWD, where GWD[n,i] is the i-th generalized wreath digraph of order n. The complete list of arc-transitive digraphs can be obtained by merging these two double sequences. This merging can be obtained by calling the procedure AddGWD(~ATD,GWD). This call will result in amending the sequence ATD to contain the GWDs as well. The latter will, for each n, appear in the sequence ATD[n] after the original digraphs from ATD.
The file "Census-ATD-1k.txt" is a text file containing the actual digraphs, where each digraph is represented by two lines. The first line of the part representing ATD[n,i] is of the form "n|i|GrphDir", and the second line has the form [s_1, s_2, …, s_m], where each s_i is of the form {v_1,v_2} where v_1 and v_2 are the out-neighbours of the vertex i. This file is needed by the magma file "Census-ATD-1k.mgm", so it has to be present in the same directory as the magma file.
The file "Census-ATD-1k-data.csv" is a csv file (excel will open it) and contains a spreadsheet with some data about the digraphs in the census. Each row has 19 fields with the meanings as listed below.
Name: the name of the digraph, i.e. ATD[9,1];
|V|: the number of vertices of the digraph;
SelfOpp: "yes" if the digraph is isomorphic to it's opposite digraph and "no" otherwise;
Opp: the name of the opposite digraph (the same as "Name" if the digraph is self-opposite;
IsUndAT "yes" if the undirected graph is arc-transitive, "no" otherwise;
UndGrph the name of the opposite underlying graph, as given in the files "Census-HAT-1k-data.csv" and "Census-GHAT-1k-data.csv" --
if the underlying graph is generalized wreath, then this is indicated by, say, "GWD(m,k)" where m and k are the defining parameters.
s: the largest integer s, such that the digraph is s-arc-transitive;
GvAb: "Ab" if the vertex-stabiliser G_v in the full automorphism group G of the digraph is abelian, otherwise "n-Ab";
|Tv:Gv|: the index of G in the smallest arc-transitive group T of the underlying graph that contains G -- if there's no such group T, then "0";
|Av:Gv|: the index of G in the automorphism group of the underlying graph;
Solv: this field contains "solve" if G is solvable and "n-solv" otherwise;
Rad: the next four fields are about alternating cycles - this one is half of the length of the alternating cycle
AtNo: this one is the size of the intersection of two intersecting alternating cycles
AtTy: "loose" if AtNo=1, "antipodal" if AtNo=2, and "tight" if AtNo=rad, otherwise "---";
|AltCyc|: the number of alternating cycles;
AltExp: the next three fields are about the alter-relations -- this one the alter-exponent;
Altper: this one is the alter-perimeter;
AltSeq: this one is the alter-sequence;
IsGWD: "yes" if the digraph is generalized wreath, and "no" otherwise;
The rest of the files are about the underlying (undirected) graphs of the digraphs from "Census-ATD-1k-data.csv". These can be either arc-transitive or half-arc-transitive, depending on whether there is an automorphism of the underlying graph that reverses an arc of the digraph. The former are also called arc-transitive G-half-arc-transitive graphs, or GHATs for short.
The first three files are about the corresponding arc-transitive underlying graphs. Those can be of two types: the underlying graphs of the generalized wreath digraphs (called GWGs) and those that are not such (non-GWDs). There are precisely 7734 G-half-arc-transitive non-GWGs with at most 1.000 vertices in the census, and 961 GWGs -- 8695 graphs all together.
The file "Census-GHAT-1k.mgm" is a magma file, which, upon loading, creates a double sequence GHAT of length 1.000, where GHAT[n,i] is the i-th non-GWG GHAT of order n. In the literature, we'll call this graph GHAT[n,i]. For example GHAT[9,1] is the cartesian product of C_3 by C_3. The file also builds the double list GWG, where GWG[n,i] is the i-th generalized wreath graph of order n. The complete list of GHATs can be obtained by merging these two double sequences. This merging can be performed by calling the procedure AddGWG(~GHAT,GWG). This call will result in enlarging the sequence GHAT to contain the generalised wreath graphs as well. The latter will, for each n, appear in the sequence GHAT[n] after the original graphs from GHAT.
The file "Census-GHAT-1k.txt" is a text file containing the actual graphs, where each graph is represented by two lines. The first line of the part representing GHAT[n,i] is of the form "n|i", and the second line has the form [s_1, s_2, …, s_m], where each s_i is of the form {v_1,v_2,v_3,v_4} where v_1, …, v_4 are neighbours of the vertex i. This file is needed by the magma file Census-GHAT-1k.mgm, so it has to be present in the same directory as the magma file.
The file "Census-GHAT-1k-data.csv" is a csv file (excel will open it) and contains a spreadsheet with some data about the non-GWG GHATs in the census. Beware: the csv file does not contain the GWGs! Each row in the spreadsheet has 9 fields with the meanings as listed below.
name: the name of the graph, i.e. GHAT[9,1];
|V|: the number of vertices of the graph;
gir: the girth of the graph;
bip: this field contains "b" if the graph is bipartite and "nb" otherwise;
CayTy: this field contains "Circ" if the graph is a circulant, "AbCay" if the graph is Coyley on abelian group, but not a circulant,
"Cay" if it is Cayley but not on an abelian group, and "n-Cay" otherwise;
|A_v|: the order of the vertex-stabiliser A_v in the full automorphism group A of the graph;
|G_v|: a sequence of the orders of vertex-stabilisers G_v of the the maximal half-arc-transitive subgroups G of A -- up to conjugacy in A;
solv: this field contains "solve" if A is solvable and "n-solv" otherwise;
[|ConCyc|]: the sequence of the lengths of A-consistent directed cycles of the graph (one cycle per each A-orbit) --
the symbols "s" and "c" indicate whether the corresponding cycle is chiral or symmetric.
Finally, the last three files are about connected tetravalent half-arc-transitive graphs of order at most 1.000. It turns out that there are 3246 such graphs.
The file "Census-HAT-1k.mgm" is a magma file, which, upon loading, creates a double sequence HAT of length 1.000, where HAT[n,i] contains the i-th graph of order n. In the literature, we'll call this graph simply HAT[n,i]. For example H[27,1] is the Doyle-Holt graph, the smallest tetravalent half-arc-transitive graph.
The file "Census-HAT-1k.txt" is a text file containing the actual graphs, where each graph is represented by two lines. The first line of the part representing HAT[n,i] is of the form "n|i", and the second line has the form [s_1, s_2, …, s_m], where each s_i is of the form {v_1,v_2,v_3,v_4} where v_1, …, v_4 are neighbours of the vertex i. This file is needed by the magma file Census-HAT-1k.mgm, so it has to be present in the same directory as the magma file.
The file "Census-HAT-1k-data.csv" is a csv file (excel will open it) and contains a spreadsheet with some data about the graph in the census. Each row has 16 fields with the meanings as listed below.
name: the name of the graph, i.e. HAT[27;1];
|V|: the number of vertices of the graph;
gir: the girth of the graph;
bip: this field contains "b" if the graph is bipartite and "nb" otherwise;
IsCay: this field contains "Cay" if the graph is Cayley and "n-Cay" otherwise;
|G_v|: the order of the vertex-stabiliser in the full automorphism group G of the graph;
solve: this field contains "solve" if G is solvable and "n-solv" otherwise;
rad, the next three fields are about alternating cycles - this one is half of the length of the alternating cycle
AtNo, this one is the size of the intersection of two intersecting alternating cycles
AtTy, "loose" if AtNo=1, "antipodal" if AtNo=2, and "tight" if AtNo=rad -- otherwise "---";
exp, the next three fields are about the alter-relations -- this one the alter-exponent;
per, this one is the alter-perimeter;
AltS, this one is the alter-sequence;
CCa, the next two lines are lengths of G-consistent cycles in X, by theory there's only two orbits of such;
CCb, the length of the longest G-consistent cycle
MetaCircCl "{}" if the graph is not a weak meta-circulant; otherwise a set of classes of weak meta-circulants that can represent X.