login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A294732 Maximal diameter of the connected cubic graphs on 2*n vertices. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
2,2
LINKS
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]
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
Apart from initial term, duplicate of A267528.
Sequence in context: A195123 A248758 A267528 * A045506 A007494 A258575
KEYWORD
nonn,easy
AUTHOR
Hugo Pfoertner, Dec 13 2017
EXTENSIONS
Terms a(12) and beyond from Andrew Howroyd, Dec 15 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:02 EDT 2024. Contains 371235 sequences. (Running on oeis4.)