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,4

References

See A296525 for references and links.

Links

Table of n, a(n) for n=2..47.

Example

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

Crossrefs

Cf. A068934, A204329, A294733, A296524, A296525, A296621.

Sequence in context: A326323 A368119 A257493 * A362377 A259844 A112707

Adjacent sequences: A296523 A296524 A296525 * A296527 A296528 A296529

Keyword

nonn,tabf,hard,more

Author

Hugo Pfoertner, Dec 14 2017

Status

approved