A294733 -id:A294733 - cp's OEIS frontend

A296524 Number of connected (2k)-regular graphs on 2n+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

Hugo Pfoertner, Dec 14 2017

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
2 3 4 5 6 7 8 9 0 1 2 3 4 5
. 1 1 1 1 1 1 . . . . . . . .
1 . 1 1 1 1 1 . . . . . . . .
1 1 . 1 1 1 1 . . . . . . . .
1 1 1 . 1 1 1 . . . . . . . .
1 1 1 1 . 1 1 . . . . . . . .
1 1 1 1 1 . . 1 . . . . . . .
1 1 1 1 1 . . 1 . . . . . . .
. . . . . 1 1 . 1 1 1 1 . . .
. . . . . . . 1 . 1 1 . 1 1 1
. . . . . . . 1 1 . . 1 1 1 1
. . . . . . . 1 1 . . 1 1 1 1
. . . . . . . 1 . 1 1 . 1 1 1
. . . . . . . . 1 1 1 1 . 1 1
. . . . . . . . 1 1 1 1 1 . 1
. . . . . . . . 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

			                 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.

For references see A294733.

M. Meringer, GenReg, Generation of regular graphs.

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

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

Original entry on oeis.org

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

Hugo Pfoertner, Dec 14 2017

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

			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.

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.

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

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

A296526 Number of connected k-regular graphs on 2n nodes with maximal diameter D(n,k) A296525 written as array T(n,k), 2 <= k < 2n.

Original entry on oeis.org

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

Hugo Pfoertner, Dec 14 2017

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

See A296525 for references and links.

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

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

Original entry on oeis.org

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

Hugo Pfoertner, Dec 17 2017

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

			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 .

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A296526 Number of connected k-regular graphs on 2n nodes with maximal diameter D(n,k) A296525 written as array T(n,k), 2 <= k < 2n.

Views

Author

Keywords

Examples

References

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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.

Views

Author

Keywords

Examples

References

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

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

A296526 Number of connected k-regular graphs on 2n nodes with maximal diameter D(n,k) A296525 written as array T(n,k), 2 <= k < 2n.