Turán-gráf

A $T_m(n)$ n csúcsú, m osztályos Turán-gráf alatt a következő gráfot értjük:

Az ilyen egy-egy osztályban a csúcsok függetlenek, tehát nem fut közöttük él. Viszont egy csúcs minden egyéb csúccsal össze van kötve a saját osztályán kívül (ezt jelzik a dupla párhuzamos vonalak). A pontok, annyira amennyire lehetséges, egyenletesen vannak szétosztva az osztályok között, vagyis bármely két osztály elemszámának eltérése legfeljebb 1.

A Turán-gráfoknak az a különleges tulajdonsága, hogy a Turán-tétel szerint ezek a legtöbb élt tartalmazó olyan $n$ csúcsú gráfok, amelyek nem tartalmaznak m+1 csúcsú klikket. Vagyis, ha G egy n csúcsú, m+1 csúcsú klikket nem tartalmazó gráf, akkor $|E(G)|\le |E(T_m(n))|$.

A Turán-gráfok teljes többrészes gráfok.

Tulajdonságai

A $T_m(n)$ Turán-gráf minden csúcsa $n-\lceil n/r\rceil$ vagy $n-\lfloor n/r\rfloor$ élű, éleinek teljes száma

$\frac{1}{2}(n^2-(nmodm)\lceil n/m{\rceil }^2-(r-(nmodm))\lfloor n/m{\rfloor }^2)\le (1-\frac{1}{m})\frac{n^2}{2}.$

Reguláris gráf, ha m|n (m osztja n-et).

Minden Turán-gráf kográf, azaz megalkotható különálló csúcsokból komplementer és diszjunkt unió műveletek elvégzésével. Ez a következő módon történhet: minden osztályt előállítunk különálló pontok halmazaként, majd ennek vesszük a komplementerét. Ezután ezen gráfok uniójának komplementere épp a Turán-gráfot adja.

Chao és Novacky 1982-ben bizonyították, hogy a Turán-gráfok kromatikusan egyediek, azaz nincs más olyan gráf, melyek kromatikus polinomja megegyezik valamely Turán-gráféval.

Fordítás

• Sablon:Fordítás