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

%I #40 Feb 21 2023 10:38:22

%S 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,

%T 38,39,41,42,44,45,47,48,50,51,53,54,56,57,59,60,62,63,65,66,68,69,71,

%U 72,74,75,77,78,80,81,83,84,86,87,89,90,92,93,95,96,98,99

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

%H Colin Barker, <a href="/A294732/b294732.txt">Table of n, a(n) for n = 2..1000</a>

%H L. Caccetta and W. F. Smyth, <a href="https://doi.org/10.1016/0012-365X(92)90047-J">Graphs of maximum diameter</a>, Discrete Mathematics, Volume 102, Issue 2, 20 May 1992, Pages 121-141.

%H Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/cubics/index.html">Cubic Graphs</a>, October 1996. [Broken link]

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1).

%F From _Andrew Howroyd_, Dec 15 2017: (Start)

%F a(n) = (6*n - 11 - (-1)^n)/4 for n > 2.

%F a(n) = a(n-2) + 3 for n > 4. (End)

%F From _Colin Barker_, Dec 16 2017: (Start)

%F G.f.: x^2*(1 + x + x^3) / ((1 - x)^2*(1 + x)).

%F a(n) = a(n-1) + a(n-2) - a(n-3) for n > 5. (End)

%F a(n) = A267528(n-1). - _Hugo Pfoertner_, Oct 10 2018

%F E.g.f.: (6 + 2*x + x^2 + 3*(x - 2)*cosh(x) + (3*x - 5)*sinh(x))/2. - _Stefano Spezia_, Feb 20 2023

%e a(5)=5 because there exists a unique graph (up to permutations) on 2*5=10 nodes, given by the following adjacency matrix

%e .

%e 1 2 3 4 5 6 7 8 9 10

%e 1 . 1 1 1 . . . . . .

%e 2 1 . 1 1 . . . . . .

%e 3 1 1 . . 1 . . . . .

%e 4 1 1 . . 1 . . . . .

%e 5 . . 1 1 . 1 . . . .

%e 6 . . . . 1 . 1 1 . .

%e 7 . . . . . 1 . . 1 1

%e 8 . . . . . 1 . . 1 1

%e 9 . . . . . . 1 1 . 1

%e 10 . . . . . . 1 1 1 .

%e .

%e that requires a shortest possible walk using 5 edges to get from node 1 to node 9.

%e From _Andrew Howroyd_, Dec 15 2017: (Start)

%e The following constructions are optimal (see theorem 5 of Caccetta et al.).

%e Pattern for odd n >= 10. Each additional 4 nodes increases diameter by 3.

%e o o o o

%e / | \ / | \ / | \ / | \

%e o--o o---o | o---o | o---o o--o

%e \ | / \ | / \ | / \ | /

%e o o o o

%e Pattern for even n >= 12. Each additional 4 nodes increases diameter by 3.

%e o--o o o o

%e / | | \ / | \ / | \ / | \

%e o--o | o---o | o---o | o---o o--o

%e \ | | / \ | / \ | / \ | /

%e o--o o o o

%e (End)

%t Prepend[LinearRecurrence[{1, 1, -1}, {2, 3, 5}, 100], 1] (* _Jean-François Alcover_, Dec 27 2017 *)

%o (PARI) Vec(x^2*(1 + x + x^3) / ((1 - x)^2*(1 + x)) + O(x^100)) \\ _Colin Barker_, Dec 16 2017

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

%Y Apart from initial term, duplicate of A267528.

%K nonn,easy

%O 2,2

%A _Hugo Pfoertner_, Dec 13 2017

%E Terms a(12) and beyond from _Andrew Howroyd_, Dec 15 2017