login
Number of minimum dominating sets in the n-cycle complement graph.
1

%I #20 Feb 16 2025 08:34:02

%S 1,4,5,9,14,20,27,35,44,54,65,77,90,104,119,135,152,170,189,209,230,

%T 252,275,299,324,350,377,405,434,464,495,527,560,594,629,665,702,740,

%U 779,819,860,902,945,989,1034,1080,1127,1175,1224,1274,1325,1377,1430

%N Number of minimum dominating sets in the n-cycle complement graph.

%H John Konvalina, <a href="https://doi.org/10.1016/0097-3165(81)90006-6">On the number of combinations without unit separation</a>, Journal of Combinatorial Theory, Series A 31.2 (1981): 101-107. See Table II, row k=2.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CycleComplementGraph.html">Cycle Complement Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MinimumDominatingSet.html">Minimum Dominating Set</a>

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

%F a(n) = n*(n - 3)/2 for n > 4.

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

%F From _Stefano Spezia_, Sep 08 2021: (Start)

%F E.g.f.: x*(12 + 6*exp(x)*(x - 2) + 6*x + 2*x^2 + x^3)/12.

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

%t Join[{1, 4}, Table[n(n-3)/2, {n, 5, 20}]]

%t CoefficientList[Series[x^3(-1 - x + 4 x^2 - 5 x^3 + 2 x^4)/(-1 + x)^3, {x, 0, 20}], x]

%Y Essentially the same as A000096.

%K nonn,easy,changed

%O 3,2

%A _Eric W. Weisstein_, Sep 06 2021