|
Search: id:A122695
|
|
|
| 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
1
|
|
| 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; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
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
|
Mycielski Graph
|
|
FORMULA
|
a(i) = 3a(i-1) + 3*2^(i-2) - 1
|
|
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 this_sequence A066822 A137212 A118049
Adjacent sequences: A122692 A122693 A122694 this_sequence A122696 A122697 A122698
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
David Eppstein (eppstein(AT)ics.uci.edu), Oct 29 2006
|
|
|
Search completed in 0.002 seconds
|
