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

Author

Hugo Pfoertner, Dec 17 2017

Keywords

• nonn
• tabf

Comments

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

Examples

			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 .
		

Links

• M. Meringer, GenReg, Generation of regular graphs.
• Wikipedia, Distance (graph theory).
• Wikipedia, Floyd-Warshall algorithm.

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