A350327 Maximum domination number of connected graphs with n vertices and minimum degree 2.

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

Table of n, a(n) for n=3..50.

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.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1).

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

Adjacent sequences: A350324 A350325 A350326 * A350328 A350329 A350330

Keyword

nonn,easy

Author

Allan Bickle, Dec 24 2021

Status

approved