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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A122695 Number of edges in the n-th Mycielski graph. This sequence of graphs is formed, starting from the empty graph, by repeatedly applying a construction of Mycielski for generating triangle-free graphs with arbitrarily large chromatic number. 0
0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, 203600, 613871, 1847756, 5555555, 16691240, 50122871, 150466916, 451597355, 1355185280, 4066342271, 12200599676, 36604944755 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

The number of vertices in the Mycielski graphs is given by sequence A083329.

REFERENCES

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

LINKS

Table of n, a(n) for n=0..23.

Mycielski Graph

FORMULA

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

Empirical G.f.: x^2*(1-x+x^2)/((1-x)*(1-2*x)*(1-3*x)). [Colin Barker, Mar 07 2012]

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.

CROSSREFS

Cf. A083329.

Sequence in context: A036683 A054444 A121332 * A066822 A137212 A118049

Adjacent sequences:  A122692 A122693 A122694 * A122696 A122697 A122698

KEYWORD

easy,nonn

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 18 05:34 EDT 2014. Contains 240688 sequences.