|
|
A361202
|
|
Maximum product of the vertex arboricities of a graph of order n and its complement.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|