A296525 -id:A296525 - cp's OEIS frontend

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.

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.

A294732 Maximal diameter of the connected cubic graphs on 2*n vertices.

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 17, 18, 20, 21, 23, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 41, 42, 44, 45, 47, 48, 50, 51, 53, 54, 56, 57, 59, 60, 62, 63, 65, 66, 68, 69, 71, 72, 74, 75, 77, 78, 80, 81, 83, 84, 86, 87, 89, 90, 92, 93, 95, 96, 98, 99

Offset: 2

Hugo Pfoertner, Dec 13 2017

			a(5)=5 because there exists a unique graph (up to permutations) on 2*5=10 nodes, given by the following adjacency matrix
.
      1 2 3 4 5 6 7 8 9 10
   1  . 1 1 1 . . . . . .
   2  1 . 1 1 . . . . . .
   3  1 1 . . 1 . . . . .
   4  1 1 . . 1 . . . . .
   5  . . 1 1 . 1 . . . .
   6  . . . . 1 . 1 1 . .
   7  . . . . . 1 . . 1 1
   8  . . . . . 1 . . 1 1
   9  . . . . . . 1 1 . 1
  10  . . . . . . 1 1 1 .
.
that requires a shortest possible walk using 5 edges to get from node 1 to node 9.
From _Andrew Howroyd_, Dec 15 2017: (Start)
The following constructions are optimal (see theorem 5 of Caccetta et al.).
Pattern for odd n >= 10. Each additional 4 nodes increases diameter by 3.
      o         o         o         o
    / | \     / | \     / | \     / | \
   o--o  o---o  |  o---o  |  o---o  o--o
    \ | /     \ | /     \ | /     \ | /
      o         o         o         o
Pattern for even n >= 12. Each additional 4 nodes increases diameter by 3.
      o--o         o         o         o
    / |  | \     / | \     / | \     / | \
   o--o  |  o---o  |  o---o  |  o---o  o--o
    \ |  | /     \ | /     \ | /     \ | /
      o--o         o         o         o
(End)

Colin Barker, Table of n, a(n) for n = 2..1000
L. Caccetta and W. F. Smyth, Graphs of maximum diameter, Discrete Mathematics, Volume 102, Issue 2, 20 May 1992, Pages 121-141.
Gordon Royle, Cubic Graphs, October 1996. [Broken link]
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A002851, A204329, A296525, A114119, A045506, A007494.

Apart from initial term, duplicate of A267528.

Prepend[LinearRecurrence[{1, 1, -1}, {2, 3, 5}, 100], 1] (* Jean-François Alcover, Dec 27 2017 *)

Vec(x^2*(1 + x + x^3) / ((1 - x)^2*(1 + x)) + O(x^100)) \\ Colin Barker, Dec 16 2017

From Andrew Howroyd, Dec 15 2017: (Start)
a(n) = (6*n - 11 - (-1)^n)/4 for n > 2.
a(n) = a(n-2) + 3 for n > 4. (End)
From Colin Barker, Dec 16 2017: (Start)
G.f.: x^2*(1 + x + x^3) / ((1 - x)^2*(1 + x)).
a(n) = a(n-1) + a(n-2) - a(n-3) for n > 5. (End)
a(n) = A267528(n-1). - Hugo Pfoertner, Oct 10 2018
E.g.f.: (6 + 2*x + x^2 + 3*(x - 2)*cosh(x) + (3*x - 5)*sinh(x))/2. - Stefano Spezia, Feb 20 2023

Terms a(12) and beyond from Andrew Howroyd, Dec 15 2017

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

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 4, 2, 2, 1, 5, 4, 2, 2, 1, 6, 5, 2, 2, 2, 1, 7, 6, 4, 2, 2, 2, 1, 8

Offset: 1

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   4   6   8  10  12  14  16
n= 3  : 1
n= 5  : 2   1
n= 7  : 3   2   1
n= 9  : 4   2   2   1
n=11  : 5   4   2   2   1
n=13  : 6   5   2   2   2   1
n=15  : 7   6   4   2   2   2   1
n=17  : 8 >=7 >=4   2   2   2   2   1

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, A296524, A296525, A296526.

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.

Original entry on oeis.org

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.

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

A296621 Number of 5-regular (quintic) connected graphs on 2*n nodes with diameter k written as irregular triangle T(n,k).

Original entry on oeis.org

1, 0, 3, 0, 60, 0, 5457, 2391, 0, 258474, 3200871, 37, 1, 0, 1041762, 2583730089, 364670, 154, 0

Offset: 3

Hugo Pfoertner, Dec 19 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: 0       1
   8: 0       3
  10: 0      60
  12: 0    5457       2391
  14: 0  258474    3200871     37   1
  16: 0 1041762 2583730089 364670 154
.
The adjacency matrix of the unique 5-regular graph on 14 nodes with diameter 5 is provided as example in A296526.

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

Cf. A006821 (row sums), A068934, A204329, A296525 (number of terms in each row), A296526, A296620.

cp's OEIS Frontend

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

A294732 Maximal diameter of the connected cubic graphs on 2*n vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

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

A296621 Number of 5-regular (quintic) connected graphs on 2*n nodes with diameter k written as irregular triangle T(n,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.

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

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.