A296524 Number of connected (2*k)-regular graphs on 2*n+1 nodes with maximal diameter D(n,k) A294733 written as triangular array T(n,k), 1 <= k <= n.

1, 1, 1, 1, 2, 1, 1, 16, 4, 1, 1, 1, 266, 6, 1, 1, 5, 367860, 10786, 10, 1, 1, 19, 1

Offset: 1

Author

Hugo Pfoertner, Dec 14 2017

Keywords

• nonn
• tabl
• hard
• more

Comments

The next term a(24) corresponding to the 6-regular graphs on 15 nodes is conjectured to be 1. It seems that there exists only one graph with diameter A294733(24)=4. Its adjacency matrix is

1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

1 . 1 1 1 1 1 1 . . . . . . . .

2 1 . 1 1 1 1 1 . . . . . . . .

3 1 1 . 1 1 1 1 . . . . . . . .

4 1 1 1 . 1 1 1 . . . . . . . .

5 1 1 1 1 . 1 1 . . . . . . . .

6 1 1 1 1 1 . . 1 . . . . . . .

7 1 1 1 1 1 . . 1 . . . . . . .

8 . . . . . 1 1 . 1 1 1 1 . . .

9 . . . . . . . 1 . 1 1 . 1 1 1

10 . . . . . . . 1 1 . . 1 1 1 1

11 . . . . . . . 1 1 . . 1 1 1 1

12 . . . . . . . 1 . 1 1 . 1 1 1

13 . . . . . . . . 1 1 1 1 . 1 1

14 . . . . . . . . 1 1 1 1 1 . 1

15 . . . . . . . . 1 1 1 1 1 1 .

The distance of 4 is achieved between nodes 1 and 13. None of the remaining 1470293674 graphs seems to have a diameter > 3.

The conjecture is confirmed using Markus Meringer's GenReg program. Aside from the 1 shown 6-regular graph on 15 nodes with diameter 4 there are 870618932 graphs with diameter 2 and 599674742 graphs with diameter 3. - Hugo Pfoertner, Dec 19 2017

Examples

			                 Degree r
        2   4    6     8    10   12   14  16
   n  --------------------------------------
   3 |  1  Diameter A294733
     |  1  Number of graphs with this diameter (this sequence)
     |
   5 |  2   1
     |  1   1
     |
   7 |  3   2    1
     |  1   2    1
     |
   9 |  4   2    2     1
     |  1  16    4     1
     |
  11 |  5   4    2     2     1
     |  1   1   266    6     1
     |
  13 |  6   5    2     2     2    1
     |  1   5 367860 10786  10    1
     |
  15 |  7   6    4     2     2    2   1
     |  1  19    1     ?     ?   17   1
     |
  17 |  8   7  >=4     2     2    2   2    1
     |  1  33    ?     ?     ?    ?  25    1
.
a(12)=1 corresponds to the only 4-regular graph on 11 nodes with diameter 4.
Its adjacency matrix is
.
      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 .
.
A shortest walk along 4 edges is required to reach node 9 from node 1.
All others of the A068934(60)=265 4-regular graphs on 11 nodes have smaller diameters, i.e., 37 with diameter 2 and 227 with diameter 3.
		

References

• For references see A294733.

Links

• M. Meringer, GenReg, Generation of regular graphs.

Crossrefs

Cf. A068934, A294733, A296525, A296526, A296620.