A296525 Maximal diameter of connected k-regular graphs on 2*n nodes written as array T(n,k), 2 <= k < 2*n.

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

Author

Hugo Pfoertner, Dec 14 2017

Keywords

• nonn
• tabf
• more
• hard

Comments

The results were found by applying the Floyd-Warshall algorithm to the output of Markus Meringer's GenReg program.

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A068934, A294732 (2nd column of table), A294733, A296524, A296526, A296621.

Extensions

a(46) corresponding to the quintic graph on 16 nodes from Hugo Pfoertner, Dec 19 2017