A296526 Number of connected k-regular graphs on 2*n nodes with maximal diameter D(n,k) A296525 written as array T(n,k), 2 <= k < 2*n.
1, 1, 1, 2, 1, 1, 1, 3, 6, 3, 1, 1, 1, 1, 35, 60, 21, 5, 1, 1, 1, 2, 16, 2391, 7849, 1547, 94, 9, 1, 1, 1, 1, 58, 1, 2757433, 21609301, 3459386, 88193, 540, 13, 1, 1, 1, 4, 1, 154
Offset: 2
Examples
Degree r
2 3 4 5 6 7 8 9 10 11 12 13 14 15
n ------------------------------------------------------------------
4 | 2 1 Diameter A296525
| 1 1 Number of graphs with this diameter (this sequence)
|
6 | 3 2 2 1
| 1 2 1 1
|
8 | 4 3 2 2 2 1
| 1 3 6 3 1 1
|
10 | 5 5 3 2 2 2 2 1
| 1 1 35 60 21 5 1 1
|
12 | 6 6 4 3 2 2 2 2 2 1
| 1 2 16 2391 7849 1547 94 9 1 1
|
14 | 7 8 5 5 3 2 2 2 2 2 2 1
| 1 1 58 1 2757433 21609301 3459386 88193 540 13 1 1
| lower bounds
16 | 8 9 7 5 >=4 >=3 2 2 2 2 2 2 2 1
| 1 4 1 154 ? ? ? ? ? ?4207 21 1 1
| lower bounds
18 | 9 11 >=8 >=6 >=4 >=4 >=3 2 2 2 2 2 2 2
| 1 1 ? ? ? ? ? ? ? ? ? ?42110 33
.
a(35)=1 corresponds to the only 5-regular graph on 14 nodes with diameter 5.
Its adjacency matrix is
.
1 2 3 4 5 6 7 8 9 0 1 2 3 4
1 . 1 1 1 1 1 . . . . . . . .
2 1 . 1 1 1 1 . . . . . . . .
3 1 1 . 1 1 . 1 . . . . . . .
4 1 1 1 . . 1 1 . . . . . . .
5 1 1 1 . . 1 1 . . . . . . .
6 1 1 . 1 1 . 1 . . . . . . .
7 . . 1 1 1 1 . 1 . . . . . .
8 . . . . . . 1 . 1 1 1 1 . .
9 . . . . . . . 1 . 1 1 . 1 1
10 . . . . . . . 1 1 . . 1 1 1
11 . . . . . . . 1 1 . . 1 1 1
12 . . . . . . . 1 . 1 1 . 1 1
13 . . . . . . . . 1 1 1 1 . 1
14 . . . . . . . . 1 1 1 1 1 .
.
A shortest walk along 5 edges is required to reach node 13 from node 1.
All others of the A068934(97)=3459383 5-regular graphs on 14 nodes have smaller diameters, i.e., 258474 with diameter 2, 3200871 with diameter 3, and 37 with diameter 4 (see A296621).
References
- See A296525 for references and links.