A361202 Maximum product of the vertex arboricities of a graph of order n and its complement.

1, 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 16, 18, 20, 22, 25, 27, 30, 33, 36, 39, 42, 45, 49, 52, 56, 60, 64, 68, 72, 76, 81, 85, 90, 95, 100, 105, 110, 115, 121, 126, 132, 138, 144, 150, 156, 162, 169, 175, 182, 189, 196, 203, 210, 217, 225, 232, 240, 248

Offset

1,3

Comments

The vertex arboricity is the minimum number of sets into which the vertices of a graph G can be partitioned so that each set induces a forest.

The extremal graphs (for n == 1 (mod 4)) are characterized in Bickle (2023).

References

D. R. Lick and A. T. White, Point-partition numbers of complementary graphs, Math. Japonicae 19 (1974), 233-237.

Links

Table of n, a(n) for n=1..60.

Allan Bickle, Extremal Decompositions for Nordhaus-Gaddum Theorems, Discrete Math, 346 7 (2023), 113392.

J. Mitchem, On the point-arboricity of a graph and its complement, Canad. J. Math. 23 (1971), 287-292.

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

Formula

a(n) = floor(((n+3)/2)^2 / 4).

G.f.: (1 - x + x^2)/((1 - x)^3*(1 + x)*(1 + x^2)*(1 + x^4)). - Stefano Spezia, Apr 22 2023

Example

A 5-cycle has vertex arboricity 2, and its complement is also a 5-cycle, so a(5) is at least 2*2 = 4.

Mathematica

LinearRecurrence[{2, -1, 0, 0, 0, 0, 0, 1, -2, 1}, {1, 1, 2, 3, 4, 5, 6, 7, 9, 10}, 60] (* Harvey P. Dale, Jul 30 2023 *)

Crossrefs

Cf. A002620 (maximum product of the chromatic numbers of a graph of order n-1 and its complement).

Sequence in context: A165763 A178877 A011870 * A284831 A261040 A087950

Adjacent sequences: A361199 A361200 A361201 * A361203 A361204 A361205

Keyword

nonn,easy

Author

Allan Bickle, Apr 20 2023

Status

approved