„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) |
||
36. sor:
<math>v_1-u_2-v_3-u_4-v_5-u_6-...-u_{m-1}-v_m-u_1-w-u_m-v_{m-1}-u_{m-2}-v_{m-3}-u_{m-4}-...-u_3-v_2-v_1</math>
Ennek a felsorolásnak az első és utolsó csúcsa megegyezik, továbbá minden csúcsot pontosan egyszer tartalmaz, tehát Hamilton-kör. A felsorolás helyességéhez az is kell, hogy <math>M_k</math> páratlan számú csúcsot tartalmazzon, ez a konstrukcióból adódóan teljesül is.
==A konstrukció iterációja==
[[Image:Mycielski graphs.svg|thumb|360px|Az ''M''<sub>2</sub>, ''M''<sub>3</sub> és ''M''<sub>4</sub> Mycielski-gráfok]]
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 × 2<sup>''i''−2</sup> − 1{{OEIS|id=A083329}}. Az ''M''<sub>''i''</sub> éleinek számát (kis ''i''-kre) a következő sorozat adja:
:0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... {{OEIS|id=A122695}}.
==Kapcsolódó témák==
| |||