Körgráf

Körgráf
6 csúcsú körgráf
Csúcsok száma	n
Élek száma	n
Átmérő	$\left\lfloor n/2\right\rfloor$
Derékbőség	n
Kromatikus szám	2, ha n páros 3, ha n páratlan
Élkromatikus szám	2, ha n páros 3, ha n páratlan
Automorfizmusok	2n (darab)
Spektrum	{2 cos(2 k π / n); k=1, ... ,n}
Egyéb	2-reguláris
Jelölés	$C_{n}$

A körgráf egy olyan gráf, amely egy körből áll, és más élt nem tartalmaz. Az $n$ csúcsú körgráfot $C_{n}$ szimbólummal szokás jelölni. Az élek száma megegyezik a csúcsok számával, és minden csúcs fokszáma 2.

Tulajdonságok

Minden körgráf

• összefüggő.
• 2-reguláris.
• tartalmaz Hamilton-kört.
• tartalmaz Euler-kört.
• 1-szívós
• kromatikus száma páros $n$ esetén 2, egyébként 3
• élkromatikus száma páros $n$ esetén 2, egyébként 3
• lerajzolható egység hosszúságú élekkel, gyufagráf
• csúcstranzitív
• csillagkromatikus száma $\chi _{s}(G)=4$, ha n=5, egyébként $\chi _{s}(G)=3$.

Alkalmazások

Számítógép-hálózatok topológiájaként választják bizonyos esetekben a körgráfot. Ilyen kontextusban beszélnek gyűrű topológiáról is.