A296525
Maximal diameter of connected k-regular graphs on 2*n nodes written as array T(n,k), 2 <= k < 2*n.
Original entry on oeis.org
2, 1, 3, 2, 2, 1, 4, 3, 2, 2, 2, 5, 5, 3, 2, 2, 2, 2, 1, 6, 6, 4, 3, 2, 2, 2, 2, 2, 1, 7, 8, 5, 5, 3, 2, 2, 2, 2, 2, 2, 1, 8, 9, 7, 5
Offset: 2
Table starts:
Degree = 2 3 4 5 6 7 8 9
n= 4 : 2 1
n= 6 : 3 2 2 1
n= 8 : 4 3 2 2 2 1
n=10 : 5 5 3 2 2 2 2 1
...
See example in A296526 for a complete illustration of the irregular table.
- L. Caccetta, W. F. Smyth Graphs of maximum diameter, Discrete Mathematics, Volume 102, Issue 2, 20 May 1992, Pages 121-141.
- M. Meringer, Regular Graphs.
- M. Meringer, GenReg, Generation of regular graphs.
- StackOverflow, Algorithm for diameter of graph?.
- Wikipedia, Distance (graph theory).
- Wikipedia, Floyd-Warshall algorithm.
a(46) corresponding to the quintic graph on 16 nodes from
Hugo Pfoertner, Dec 19 2017
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.
Original entry on oeis.org
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
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).
- See A296525 for references and links.
Showing 1-2 of 2 results.
Comments