Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #14 Feb 05 2022 07:13:00
%S 1,2,2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,
%T 13,13,14,14,14,15,15,16,16,16,17,17,18,18,18,19,19,20
%N Maximum domination number of connected graphs with n vertices and minimum degree 2.
%C McCuaig and Shepherd characterized the extremal graphs (see link below).
%C For n=4, the exceptional graph is the 4-cycle.
%C For n=7, there are six exceptional graphs, one of which is the 7-cycle.
%D M. Blank, An estimate of the external stability number of a graph without suspended vertices. Prikl. Math, i Programmirovanie Vyp. 10 (1973), 3-11.
%H W. McCuaig and B. Shepherd, <a href="https://doi.org/10.1002/jgt.3190130610">Domination in graphs with minimum degree two</a>, J Graph Theory 13 (1989), 749-762.
%H Laura Sanchis, <a href="https://doi.org/10.1002/(SICI)1097-0118(199706)25:2%3C139::AID-JGT6%3E3.0.CO;2-N">Bounds related to domination in graphs with minimum degree two</a>, J Graph Theory 25 2 (1997), 139-152.
%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,1,-1).
%F a(n) = floor(2/5*n) = A057354(n) except for n=4,7.
%F From _Stefano Spezia_, Dec 25 2021: (Start)
%F G.f.: x^3*(1 + x + x^4 - x^5 - x^6 + x^7 - x^9 + x^10)/((1 - x)^2*(1 + x + x^2 + x^3 + x^4)).
%F a(n) = a(n-1) + a(n-5) - a(n-6) for n > 13. (End)
%e The domination number of a 5-cycle is 2.
%Y Cf. A057354.
%K nonn,easy
%O 3,2
%A _Allan Bickle_, Dec 24 2021