Cyclic graph

Материал из WEGA
Перейти к навигации Перейти к поиску

Cyclic graphциклический граф.

The cyclic graph [math]\displaystyle{ \,C(n,k) }[/math] have a point set [math]\displaystyle{ \,V = \{0,1,\ldots,n-1\} }[/math] and lines [math]\displaystyle{ \,\{i,i+1\}\pmod{n} }[/math] and [math]\displaystyle{ \,\{i,i+k\}\pmod{n} }[/math] ([math]\displaystyle{ \,i = 1,\ldots,n }[/math]), where [math]\displaystyle{ \,k }[/math] is an integer with [math]\displaystyle{ \,2 \leq k \leq n-2 }[/math]. If [math]\displaystyle{ \,G(n,k) }[/math] is a circulant graph, then [math]\displaystyle{ \,C(n,k) \simeq G(n,S) }[/math] with [math]\displaystyle{ \,S = \{1, \ldots,\min\{k,n-k\}\} }[/math]. The graph [math]\displaystyle{ \,C(n,k) }[/math] are point-transitive [math]\displaystyle{ \,3 }[/math]-regular if [math]\displaystyle{ \,n = 2k }[/math], and [math]\displaystyle{ \,4 }[/math]-regular otherwise.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.