Körgráf

Körgráf
6 csúcsú körgráf
Csúcsok száma	n
Élek száma	n
Átmérő	${\displaystyle \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}[1]
Egyéb	2-reguláris
Jelölés	${\displaystyle C_{n}}$

A körgráf egy olyan gráf, amely egy körből áll, és más élt nem tartalmaz. Az ${\displaystyle n}$ csúcsú körgráfot ${\displaystyle 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 ${\displaystyle n}$ esetén 2, egyébként 3
• élkromatikus száma páros ${\displaystyle n}$ esetén 2, egyébként 3
• lerajzolható egység hosszúságú élekkel, gyufagráf
• csúcstranzitív
• csillagkromatikus száma ${\displaystyle \chi _{s}(G)=4}$, ha n=5, egyébként ${\displaystyle \chi _{s}(G)=3}$.[2]

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.

Jegyzetek

1. Some simple graph spectra. win.tue.nl
2. Fertin, Guillaume; Raspaud, André & Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, DOI 10.1002/jgt.20029