|
|
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
|
|
|
FORMULA
|
a(n) = (6*n - 11 - (-1)^n)/4 for n > 2.
a(n) = a(n-2) + 3 for n > 4. (End)
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)
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.
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
|
|
|
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.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|