Digraphs

This page contains some catalogues of directed graphs prepared by Brendan McKay.

Digraphs

Here are the digraphs up to 6 vertices with loops either not allowed or allowed. The format is digraph6.

Loops not allowed

1 vertex (1)
2 vertices (3)
3 vertices (16)
4 vertices (218)
5 vertices (9608)
6 vertices (1540944)

Loops allowed

1 vertex (2)
2 vertices (10)
3 vertices (104)
4 vertices (3044)
5 vertices (291968)
6 vertices (96928992, gzipped)

Oriented graphs

By an oriented graph we mean a digraph with no cycles of length 2. Here are the oriented graphs up to 7 vertices with loops not allowed and 6 vertices with loops allowed. The format is digraph6.

Loops not allowed

1 vertex (1)
2 vertices (2)
3 vertices (7)
4 vertices (42)
5 vertices (582)
6 vertices (21480)
7 vertices (2142288, gzipped)

Loops allowed

1 vertex (2)
2 vertices (7)
3 vertices (44)
4 vertices (558)
5 vertices (16926)
6 vertices (1319358)

Tournaments

Here are the non-isomorphic tournaments up to 10 vertices. Each is given as the upper triangle of the adjacency matrix in row order, on one line without spaces.

2 vertices (1)
3 vertices (2)
4 vertices (4)
5 vertices (12)
6 vertices (56)
7 vertices (456)
8 vertices (6880)
9 vertices (191536)
10 vertices (gzipped) (9733056)

Self-converse Tournaments

Here are the non-isomorphic self-converse tournaments (self-complementary oriented graphs) up to 13 vertices. Each is given as the upper triangle of the adjacency matrix in row order, on one line without spaces.

2 vertices (1)
3 vertices (2)
4 vertices (2)
5 vertices (8)
6 vertices (12)
7 vertices (88)
8 vertices (176)
9 vertices (2752)
10 vertices (8784)
11 vertices (279968)
12 vertices (gzipped) (1492288)
13 vertices (gzipped) (95458560)

Regular and Semi-regular Tournaments

A tournament of odd order n is regular if the out-degree of each vertex is (n-1)/2. A tournament of even order n is semi-regular if the out-degree of each vertex is n/2-1 or n/2. Here are the regular and semi-regular tournaments of order up to 13.

Each is given as the upper triangle of the adjacency matrix in row order, on one line without spaces.

3 vertices (1)
4 vertices (1)
5 vertices (1)
6 vertices (5)
7 vertices (3)
8 vertices (85)
9 vertices (15)
10 vertices (13333)
11 vertices (1223)
12 vertices (gzipped) (19434757): Part a  Part b  (these unpack to 1.3GB altogether)
13 vertices (gzipped) (1495297)

A regular tournament is doubly-regular if each pair of vertices is jointly connected to exactly (n-3)/4 others. The order must be one less than a multiple of 4. These tournaments are related to skew Hadamard matrices. Ted Spence was the first to find them up to 27 vertices but I have recomputed them. The incomplete lists on larger sizes were computed using skew Hadamard matrices from Christos Koukouvinos's catalogue.

3 vertices (1)
7 vertices (1)
11 vertices (1)
15 vertices (2)
19 vertices (2)
23 vertices (37)
27 vertices (722)
31 vertices (5 incomplete)
35 vertices (486 incomplete)
39 vertices (1560 incomplete)
43 vertices (2178 incomplete)
47 vertices (3 incomplete)
51 vertices (gzipped) (36350 incomplete)

Locally-transitive Tournaments

A tournament is locally-transitive if, for each vertex v, the in-neighbourhood and the out-neighbourhood of v are both transitive tournaments.

Here are the non-isomorphic locally-transitive tournaments up to 20 vertices. Each is given as the upper triangle of the adjacency matrix in row order, on one line without spaces.

3 vertices (2)
4 vertices (2)
5 vertices (4)
6 vertices (6)
7 vertices (10)
8 vertices (16)
9 vertices (30)
10 vertices (52)
11 vertices (94)
12 vertices (172)
13 vertices (316)
14 vertices (586)
15 vertices (1096)
16 vertices (gzipped) (2048)
17 vertices (gzipped) (3856)
18 vertices (gzipped) (7286)
19 vertices (gzipped) (13798)
20 vertices (gzipped) (26216)

Acyclic digraphs

Here are the acyclic digraphs up to 8 vertices. Each is given as the upper triangle of the adjacency matrix in row order, on one line without spaces. The lower triangle is zero; that is, the points are in topological order.

2 vertices (2)
3 vertices (6)
4 vertices (31)
5 vertices (302)
6 vertices (5984)
7 vertices (gzipped) (243668)
8 vertices (gzipped)  part 1  part 2  part 3  part 4  (20286025)

Eulerian digraphs

Here are the connected Eulerian digraphs up to 8 vertices. There are no loops. The format is digraph6.

2 vertices (1)
3 vertices (3)
4 vertices (12)
5 vertices (90)
6 vertices (2162)
7 vertices (179098)
8 vertices (51110788, gzipped)

Here are the connected Eulerian oriented graphs up to 9 vertices. There are no loops. These differ from the previous list in that 2-cycles are forbidden. The format is digraph6.

3 vertices (1)
4 vertices (1)
5 vertices (4)
6 vertices (16)
7 vertices (175)
8 vertices (5274)
9 vertices (434017)

Partially-ordered sets (posets)

Here are the Hasse diagrams of posets up to 10 points. There is one poset per line in a format like "10 4 56 57 78 79". This means there are 10 points 0..9, and 4 covering relations that are 5<6, 5<7, 7<8 and 7<9. The full poset is the reflexive transitive closure of the Hasse diagram. A program is available that can make larger sizes, but the numbers grow very quickly.

1 point (1)
2 points (2)
3 points (5)
4 points (16)
5 points (63)
6 points (318)
7 points (2045)
8 points (16999)
9 points (183231, gzipped)
10 points (2567284, gzipped)

Ramsey tournaments

See the Ramsey page.

Vertex-transitive tournaments

Here are all the tournaments up to 49 vertices whose automorphism groups act transitively on the vertex set. Since all automorphisms of a tournament have odd order, the tournament must also have odd order. First we will give the circulant tournaments, which are those having (0 1 ... n-1) as an automorphism. Then we will give the vertex-transitive tournaments up to 49 vertices that are not circulant.

Thanks to Gordon Royle for helping with the permutation groups.

Circulant tournaments

1 vertex (1 tournament)
3 vertices (1 tournament)
5 vertices (1 tournament)
7 vertices (2 tournaments)
9 vertices (3 tournaments)
11 vertices (4 tournaments)
13 vertices (6 tournaments)
15 vertices (16 tournaments)
17 vertices (16 tournaments)
19 vertices (30 tournaments)
21 vertices (88 tournaments)
23 vertices (94 tournaments)
25 vertices (205 tournaments)
27 vertices (457 tournaments)
29 vertices (586 tournaments)
31 vertices (1096 tournaments)
33 vertices (3280 tournaments)
35 vertices (5472 tournaments)
37 vertices (7286 tournaments)
39 vertices (21856 tournaments)
41 vertices (26216 tournaments)
43 vertices (49940 tournaments, gzipped)
45 vertices (174848 tournaments, gzipped)
47 vertices (182362 tournaments, gzipped)
49 vertices (399472 tournaments, gzipped)

Vertex-transitive but not circulant tournaments

21 vertices (22 tournaments)
25 vertices (9 tournaments)
27 vertices (237 tournaments)
39 vertices (3350 tournaments)
45 vertices (21776 tournaments)
49 vertices (8384 tournaments)

Nonreconstructable digraphs

The deck of a digraph G is the multiset of its vertex-deleted subdigraphs G-v. The elements of the deck are specified only up to isomorphism. We say that G is reconstructable (also, reconstructible) if G is uniquely determined by its deck. Here we give all the known simple digraphs which are not reconstructable, starting at 3 vertices.

3 vertices 2 pairs, 2 triples
4 vertices 8 pairs
5 vertices 9 pairs
6 vertices 9 pairs
On 7 vertices, all digraphs are reconstructable.
8 vertices 5 pairs
Those files are complete. From 9 vertices onwards, all known nonreconstructable digraphs lie in one of the infinite families found by Paul Stockmeyer. There are 4 pairs for each order which is a power of 2, and 6 pairs for each order which is the sum of two distinct powers of 2. stock.c is a program in standard C that writes the digraphs. Run it with one argument which is the number of vertices.

The reduced deck of a digraph G is the same as the deck except that isomorphs have been removed. Thus, the reduced deck tells you which graphs appear in the deck up to isomorphism but not how many times they appear. When only the reduced deck is available, additional digraphs are not uniquely determined. The following collection is complete up to 8 vertices.

3 vertices two sets of size 4
4 vertices one triple
5 vertices one pair
7 vertices 3 pairs

For more information: see this paper.

 


Page Master: Brendan McKay, brendan.mckay@anu.edu.au and https://users.cecs.anu.edu.au/~bdm.

Up to the combinatorial data page