login
A350327
Maximum domination number of connected graphs with n vertices and minimum degree 2.
0
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, 13, 13, 14, 14, 14, 15, 15, 16, 16, 16, 17, 17, 18, 18, 18, 19, 19, 20
OFFSET
3,2
COMMENTS
McCuaig and Shepherd characterized the extremal graphs (see link below).
For n=4, the exceptional graph is the 4-cycle.
For n=7, there are six exceptional graphs, one of which is the 7-cycle.
REFERENCES
M. Blank, An estimate of the external stability number of a graph without suspended vertices. Prikl. Math, i Programmirovanie Vyp. 10 (1973), 3-11.
LINKS
W. McCuaig and B. Shepherd, Domination in graphs with minimum degree two, J Graph Theory 13 (1989), 749-762.
Laura Sanchis, Bounds related to domination in graphs with minimum degree two, J Graph Theory 25 2 (1997), 139-152.
FORMULA
a(n) = floor(2/5*n) = A057354(n) except for n=4,7.
From Stefano Spezia, Dec 25 2021: (Start)
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)).
a(n) = a(n-1) + a(n-5) - a(n-6) for n > 13. (End)
EXAMPLE
The domination number of a 5-cycle is 2.
CROSSREFS
Cf. A057354.
Sequence in context: A099199 A172474 A062276 * A053264 A343347 A079440
KEYWORD
nonn,easy
AUTHOR
Allan Bickle, Dec 24 2021
STATUS
approved