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$
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)
Egyéb	2-reguláris

A körgráf egy olyan gráf, amely egy körből áll, és más élet 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.
• 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
• csúcstranzitív

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.