A367644 Number of maximal independent vertex sets and minimal vertex covers in the n-trapezohedral graph.

3, 3, 6, 11, 18, 30, 52, 91, 159, 278, 487, 854, 1498, 2628, 4611, 8091, 14198, 24915, 43722, 76726, 134644, 236283, 414647, 727654, 1276943, 2240878, 3932466, 6900996, 12110403, 21252275, 37295142, 65448411, 114853954, 201554638, 353703732, 620706779

Offset: 1

Author

Eric W. Weisstein, Nov 25 2023

Keywords

• nonn
• easy

Comments

Extended to n=1 using the formula/recurrence.

Links

• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
• Eric Weisstein's World of Mathematics, Minimal Vertex Cover
• Eric Weisstein's World of Mathematics, Trapezohedral Graph
• Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-1).

Crossrefs

Cf. A001608, A109377.

Programs

Mathematica

Table[1 + RootSum[-1 + # - 2  #^2 + #^3 &, #^n &], {n, 0, 20}]
LinearRecurrence[{3, -3, 2, -1}, {3, 3, 6, 11}, 20]
CoefficientList[Series[(3 - 6 x + 6 x^2 - 4 x^3)/(1 - 3 x + 3 x^2 - 2 x^3 + x^4), {x, 0, 20}], x]

Formula

a(n) = A001608(2n) + 1.

a(n) = A109377(n+2) + 1.

a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3) - a(n-4).

G.f.: x*(3-6*x+6*x^2-4*x^3)/(1-3*x+3*x^2-2*x^3+x^4).