|
|
A122695
|
|
Number of edges in the n-th Mycielski graph.
|
|
2
|
|
|
0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, 203600, 613871, 1847756, 5555555, 16691240, 50122871, 150466916, 451597355, 1355185280, 4066342271, 12200599676, 36604944755, 109821125720, 329475960071, 988453046036, 2965409469755, 8896329072560
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
The Mycielski graphs are formed, starting from the empty graph, by repeatedly applying a construction of Mycielski for generating triangle-free graphs with arbitrarily large chromatic number.
The number of vertices in the Mycielski graphs is given by sequence A083329.
Also the number of maximal and maximum cliques in the n-Mycielski graph for n > 1. - Eric W. Weisstein, Dec 01 2017
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 3*a(n-1) + 3*2^(n-3) - 1 for n > 2. [corrected by Moeez Muhammad, Apr 17 2021]
a(n) = (18-27*2^n+14*3^n)/36 for n>1.
a(n) = 6*a(n-1)-11*a(n-2)+6*a(n-3) for n>4.
G.f.: x^2*(1-x+x^2) / ((1-x)*(1-2*x)*(1-3*x)).
(End)
|
|
EXAMPLE
|
The first few graphs in the sequence of Mycielski graphs are the null graph, K1, K2, C5 and the Graezsch graph with 11 vertices and 20 edges. Thus the first entries in this sequence are 0, 0, 1, 5 and 20.
|
|
MATHEMATICA
|
Table[If[n < 2, 0, (18 - 27 2^n + 14 3^n)/36], {n, 0, 10}] (* Eric W. Weisstein, Dec 01 2017 *)
Join[{0, 0}, LinearRecurrence[{6, -11, 6}, {1, 5, 20}, 20]] (* Eric W. Weisstein, Dec 01 2017 *)
ientList[Series[x^2 (1 - x + x^2)/(1 - 6 x + 11 x^2 - 6 x^3), {x, 0, 20}], x] (* Eric W. Weisstein, Dec 01 2017 *)
|
|
PROG
|
(PARI) concat(vector(2), Vec(x^2*(1-x+x^2)/((1-x)*(1-2*x)*(1-3*x)) + O(x^40))) \\ Colin Barker, Jan 16 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|