OFFSET
5,5
COMMENTS
The results were found by applying the Floyd-Warshall algorithm to the output of Markus Meringer's GenReg program.
LINKS
M. Meringer, GenReg, Generation of regular graphs.
Wikipedia, Distance (graph theory).
Wikipedia, Floyd-Warshall algorithm.
EXAMPLE
Triangle begins:
Diameter
n/ 1 2 3 4 5 6 7
5: 1
6: 0 1
7: 0 2
8: 0 6
9: 0 16
10: 0 24 35
11: 0 37 227 1x
12: 0 26 1502 16
13: 0 10 10561 202 5
14: 0 1x 84103 4006 58
15: 0 1x 722252 82726 493 19
16: 0 0 6383913 1647078 6224 202 1x
17: 0 0 55831405 30291536 96504 2156 33
.
x indicates provision of adjacency information below.
Examples of unique 4-regular graphs with minimum diameter:
Adjacency matrix of the graph of diameter 2 on 14 nodes:
1 2 3 4 5 6 7 8 9 0 1 2 3 4
1 . 1 1 1 1 . . . . . . . . .
2 1 . . . . 1 1 1 . . . . . .
3 1 . . . . 1 1 1 . . . . . .
4 1 . . . . . . . 1 1 1 . . .
5 1 . . . . . . . . . . 1 1 1
6 . 1 1 . . . . . 1 . . 1 . .
7 . 1 1 . . . . . . 1 . . 1 .
8 . 1 1 . . . . . . . 1 . . 1
9 . . . 1 . 1 . . . . . . 1 1
10 . . . 1 . . 1 . . . . 1 . 1
11 . . . 1 . . . 1 . . . 1 1 .
12 . . . . 1 1 . . . 1 1 . . .
13 . . . . 1 . 1 . 1 . 1 . . .
14 . . . . 1 . . 1 1 1 . . . .
.
Adjacency matrix of the graph of diameter 2 on 15 nodes:
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
1 . 1 1 1 1 . . . . . . . . . .
2 1 . 1 . . 1 1 . . . . . . . .
3 1 1 . . . . . 1 1 . . . . . .
4 1 . . . . . . . . 1 1 1 . . .
5 1 . . . . . . . . . . . 1 1 1
6 . 1 . . . . . . . 1 1 . 1 . .
7 . 1 . . . . . . . . . 1 . 1 1
8 . . 1 . . . . . . 1 . 1 . 1 .
9 . . 1 . . . . . . . 1 . 1 . 1
10 . . . 1 . 1 . 1 . . . . . . 1
11 . . . 1 . 1 . . 1 . . . . 1 .
12 . . . 1 . . 1 1 . . . . 1 . .
13 . . . . 1 1 . . 1 . . 1 . . .
14 . . . . 1 . 1 1 . . 1 . . . .
15 . . . . 1 . 1 . 1 1 . . . . .
.
Examples of unique graphs with maximum diameter:
Adjacency matrix of the graph of diameter 4 on 11 nodes:
1 2 3 4 5 6 7 8 9 0 1
1 . 1 1 1 1 . . . . . .
2 1 . 1 1 1 . . . . . .
3 1 1 . 1 1 . . . . . .
4 1 1 1 . . 1 . . . . .
5 1 1 1 . . 1 . . . . .
6 . . . 1 1 . 1 1 . . .
7 . . . . . 1 . . 1 1 1
8 . . . . . 1 . . 1 1 1
9 . . . . . . 1 1 . 1 1
10 . . . . . . 1 1 1 . 1
11 . . . . . . 1 1 1 1 .
.
Adjacency matrix of the graph of diameter 7 on 16 nodes:
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
1 . 1 1 1 1 . . . . . . . . . . .
2 1 . 1 1 1 . . . . . . . . . . .
3 1 1 . 1 1 . . . . . . . . . . .
4 1 1 1 . . 1 . . . . . . . . . .
5 1 1 1 . . 1 . . . . . . . . . .
6 . . . 1 1 . 1 1 . . . . . . . .
7 . . . . . 1 . 1 1 1 . . . . . .
8 . . . . . 1 1 . 1 1 . . . . . .
9 . . . . . . 1 1 . 1 1 . . . . .
10 . . . . . . 1 1 1 . 1 . . . . .
11 . . . . . . . . 1 1 . 1 1 . . .
12 . . . . . . . . . . 1 . . 1 1 1
13 . . . . . . . . . . 1 . . 1 1 1
14 . . . . . . . . . . . 1 1 . 1 1
15 . . . . . . . . . . . 1 1 1 . 1
16 . . . . . . . . . . . 1 1 1 1 .
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Hugo Pfoertner, Dec 17 2017
STATUS
approved