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

Author

Allan Bickle, Apr 20 2023

Keywords

• nonn
• easy

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).

Examples

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

References

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

Links

• 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).

Crossrefs

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

Programs

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 *)

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