„Mycielski-konstrukció” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Syp (vitalap | szerkesztései) |
Syp (vitalap | szerkesztései) |
||
41. sor:
Ha a két csúcsból és egyetlen élből álló gráfból kiindulva ismételten alkalmazzuk a Mycielski-konstrukciót, gráfok ''M''<sub>''i''</sub> = μ(''M''<sub>''i''-1</sub>) sorozatát kapjuk, ezeket Mycielski-gráfoknak is nevezzük. A sorozat első néhány eleme az ''M''<sub>2</sub> = ''K''<sub>2</sub>, ami két csúcsból és egy élből áll, az ''M''<sub>3</sub> = ''C''<sub>5</sub> [[körgráf]] és a 11 csúcsból és 20 élből álló [[Grötzsch-gráf]].
Általában véve a sorozat ''M''<sub>''i''</sub> gráfjairól elmondható, hogy [[háromszögmentes gráf|háromszögmentesek]], (''i''-1)-[[k-szorosan összefüggő gráf|szeresen összefüggőek]] és ''i''-[[kromatikus szám|kromatikusak]]. Az ''M''<sub>''i''</sub> csúcsainak száma 3 &
:0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... {{OEIS|id=A122695}}.
| |||