login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Colin Barker, Table of n, a(n) for n = 0..1000

J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3: 161-162, 1955.

Eric Weisstein's World of Mathematics, Maximal Clique

Eric Weisstein's World of Mathematics, Maximum Clique

Eric Weisstein's World of Mathematics, Mycielski Graph

Index entries for linear recurrences with constant coefficients, signature (6, -11, 6).

FORMULA

a(n) = 3*a(n-1) + 3*2^(n-2) - 1.

From Colin Barker, Mar 07 2012 and Jan 16 2016: (Start)

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

Cf. A083329.

Sequence in context: A036683 A054444 A121332 * A269914 A066822 A137212

Adjacent sequences:  A122692 A122693 A122694 * A122696 A122697 A122698

KEYWORD

easy,nonn,changed

AUTHOR

David Eppstein, Oct 29 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 12 18:33 EST 2017. Contains 295954 sequences.