To generate the connected k-regular graphs on n vertices call genreg n k. To obtain only those graphs with girth, you must append t as another parameter, therefore genreg n k t. To control the output you may use the following options:
.asc. There is also the girth, a
set of generators of the automorphismgroup and its order specified. For
example when calling genreg 4 3 -a you obtain the file 04_3_3.asc
with the content:
Graph 1: 1 : 2 3 4 2 : 1 3 4 3 : 1 2 4 4 : 1 2 3 Taillenweite: 3 3 : 1 2 4 3 2 : 1 3 2 4 2 : 1 4 3 2 1 : 2 1 3 4 1 : 3 2 1 4 1 : 4 2 3 1 Ordnung: 24At first the adjacencylist is given. In every line there are behind the colon the neighbours of the vertex in front of the colon. Then we have the girth and afterwards in every line an automorphism µ. Before the colon there is min{ j | µ(j) != j } and behind we have at i-th position µ(j). The given generators are representatives of the left cosets of a centralizer chain of the automorphismgroup (Sims chain). The number behind "Ordnung" is the size of the graph's automorphismgroup.
If you declare an additional integer x, only the first x
graphs are put on the file. In this case the file will probably not
contain all the Graphs for given n, k and t.
Therefore the filename is marked by an additional -U
(for unfinished), e.g. with genreg 6 3 -a 1 you obtain
the file 06_3_3-U.asc.
If the option -a is followed by stdout, the output is not written to a file, but to stdout.
.scd. The following coding (shortcode) is used:
One after the other all vertices 1,...,n are regarded. Only adjacent vertices with larger number than the regarded vertex itself are added to the code. Thus we have for every edge of the graph exactly one entry in the code. For the example above (n=4, k=3) you get
2 3 4 3 4 4
as code. To achieve a further compression of the data, we compare the code of the next graph to be constructed with the preceeding and find out, in how many entries at the begining the two codes are equal. Instead of writing the common pieces twice on the file, we only store its length and then the differing entries. Thus as first entry of the file we always have zero. The 4-regular graphs on 7 vertices have the codes
2 3 4 5 3 4 5 6 7 6 7 6 7 7 and
2 3 4 5 3 4 6 5 7 6 7 6 7 7
The file 07_4_3.scd consists of
0 2 3 4 5 3 4 5 6 7 6 7 6 7 7 6 6 5 7 6 7 6 7 7
and has length of 24 byte. This kind of comprimation gains effectivity for big n or t>3. The program readscd.c shows easy funktions, which are able to read shortcode-files.
Even this option can be followed by an integer or stdout if only a certain number of graphs shall be stored or you want to use stdout.
.erg. Call of genreg 21 4 5 -e produces a
file named 21_4_5.erg containing
GENREG - Generator fuer regulaere Graphen
21 Knoten, Grad 4, Taillenweite mind. 5
Erzeugung gestartet...
8 Graphen erzeugt.
Laufzeit:20.9s 0.4 Repr./s As long as the construction is not
finished, this file has the name
21_4_5-U.erg (and of course the last two lines are
missing).
If option -e is not used, GENREG writes these informations to stderr.
.erg-File.
In cases of very big problems to be computed, the following modulo-option is available to split the problem into several jobs, therewith it can be worked parallel on different machines.
20_3_3-1.scd.
When the generation is finished, it is renamed to 20_3_3#1.scd.
The remaining graphs can be computed with genreg 20 3 -s -m 2 2.
Remarks: