A296620 Number of 4-regular (quartic) connected graphs on n nodes with diameter k written as irregular triangle T(n,k).

1, 0, 1, 0, 2, 0, 6, 0, 16, 0, 24, 35, 0, 37, 227, 1, 0, 26, 1502, 16, 0, 10, 10561, 202, 5, 0, 1, 84103, 4006, 58, 0, 1, 722252, 82726, 493, 19, 0, 0, 6383913, 1647078, 6224, 202, 1, 0, 0, 55831405, 30291536, 96504, 2156, 33

Offset

5,5

Comments

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

Links

Table of n, a(n) for n=5..54.

M. Meringer, GenReg, Generation of regular graphs.

Wikipedia, Distance (graph theory).

Wikipedia, Floyd-Warshall algorithm.

Example

Triangle begins:
                     Diameter
   n/ 1  2        3        4     5    6  7
   5: 1
   6: 0  1
   7: 0  2
   8: 0  6
   9: 0 16
  10: 0 24       35
  11: 0 37      227        1x
  12: 0 26     1502       16
  13: 0 10    10561      202     5
  14: 0  1x   84103     4006    58
  15: 0  1x  722252    82726   493   19
  16: 0  0  6383913  1647078  6224  202  1x
  17: 0  0 55831405 30291536 96504 2156 33
.
x indicates provision of adjacency information below.
Examples of unique 4-regular graphs with minimum diameter:
Adjacency matrix of the graph of diameter 2 on 14 nodes:
      1 2 3 4 5 6 7 8 9 0 1 2 3 4
   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 .
  12  . . . . 1 1 . . . 1 1 . . .
  13  . . . . 1 . 1 . 1 . 1 . . .
  14  . . . . 1 . . 1 1 1 . . . .
.
Adjacency matrix of the graph of diameter 2 on 15 nodes:
      1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
   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 .
  12  . . . 1 . . 1 1 . . . . 1 . .
  13  . . . . 1 1 . . 1 . . 1 . . .
  14  . . . . 1 . 1 1 . . 1 . . . .
  15  . . . . 1 . 1 . 1 1 . . . . .
.
Examples of unique graphs with maximum diameter:
Adjacency matrix of the graph of diameter 4 on 11 nodes:
      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 .
.
Adjacency matrix of the graph of diameter 7 on 16 nodes:
      1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
   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 . . .
  12  . . . . . . . . . . 1 . . 1 1 1
  13  . . . . . . . . . . 1 . . 1 1 1
  14  . . . . . . . . . . . 1 1 . 1 1
  15  . . . . . . . . . . . 1 1 1 . 1
  16  . . . . . . . . . . . 1 1 1 1 .

Crossrefs

Cf. A006820 (row sums), A204329, A294733 (number of terms in each row for odd n), A296525 (number of terms in each row for even n).

Sequence in context: A293935 A285479 A327369 * A263789 A081153 A369278

Adjacent sequences: A296617 A296618 A296619 * A296621 A296622 A296623

Keyword

nonn,tabf

Author

Hugo Pfoertner, Dec 17 2017

Status

approved