login
A123304
Number of edge covers for the circular ladder (n-prism graph) C_n X K_2.
4
4, 5, 43, 263, 1699, 10895, 69943, 448943, 2881699, 18497135, 118730023, 762108143, 4891844659, 31399932335, 201550911703, 1293721577903, 8304182337859, 53303156937455, 342144045482503, 2196165379031663, 14096818096762579, 90485116626705455, 580808823292457143
OFFSET
0,1
COMMENTS
An edge covering for a graph is a set of edges so that every vertex is adjacent to at least one edge of this set.
The number of edge coverings for the circle C_n for n>0 is the n-th Lucas number.
LINKS
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4
Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Prism Graph
FORMULA
a(n) = 5*a(n-1) +9*a(n-2) +a(n-3) -2*a(n-4).
G.f.: (4-15*x-18*x^2-x^3) / ((1+x)*(1-6*x-3*x^2+2*x^3)).
MATHEMATICA
a[0] = 4; a[1] = 5; a[2] = 43; a[3] = 263; a[n_] := a[n] = 5a[n - 1] + 9a[n - 2] + a[n - 3] - 2a[n - 4]; Table[a[n], {n, 0, 19}] (* Robert G. Wilson v, Sep 26 2006 *)
CoefficientList[ Series[(4 - 15x - 18x^2 - x^3)/((1 + x)*(1 - 6x - 3x^2 + 2x^3)), {x, 0, 19}], x] (* Robert G. Wilson v, Sep 26 2006 *)
Table[(-1)^n + RootSum[2 - 3 # - 6 #^2 + #^3 &, #^n &], {n, 0, 20}] (* Eric W. Weisstein, Mar 29 2017 *)
LinearRecurrence[{5, 9, 1, -2}, {5, 43, 263, 1699}, {0, 20}] (* Eric W. Weisstein, Aug 09 2017 *)
PROG
(PARI) x='x+O('x^99); Vec((4-15*x-18*x^2-x^3)/((1+x)*(1-6*x-3*x^2+2*x^3))) \\ Altug Alkan, Aug 10 2017
CROSSREFS
Sequence in context: A241279 A245696 A317139 * A270129 A271293 A256290
KEYWORD
nonn,easy
AUTHOR
Roberto Tauraso, Sep 24 2006
STATUS
approved