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

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

Links

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

Formula

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

Example

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)

Mathematica

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

Prog

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

Crossrefs

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

Apart from initial term, duplicate of A267528.

Sequence in context: A195123 A248758 A267528 * A045506 A007494 A258575

Adjacent sequences: A294729 A294730 A294731 * A294733 A294734 A294735

Keyword

nonn,easy

Author

Hugo Pfoertner, Dec 13 2017

Extensions

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

Status

approved