A123304 Number of edge covers for the circular ladder (n-prism graph) C_n X K_2.

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

Author

Roberto Tauraso, Sep 24 2006

Keywords

• nonn
• easy

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
• Index entries for linear recurrences with constant coefficients, signature (5,9,1,-2).

Programs

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

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

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