Circulant graph
Circulant graph — циркулянтный граф.
1. Let [math]\displaystyle{ \,p }[/math] be a positive integer and [math]\displaystyle{ \,S }[/math] be a subset of [math]\displaystyle{ \{1,2, \ldots, p-1\} }[/math], such that [math]\displaystyle{ i \in S }[/math] implies [math]\displaystyle{ p-i \in S }[/math]. A circulant graph [math]\displaystyle{ \,G(p,S) }[/math] has vertices [math]\displaystyle{ 0,1, \ldots, p-1 }[/math] and two vertices [math]\displaystyle{ \,i }[/math] and [math]\displaystyle{ \,j }[/math] are adjacent if and only if [math]\displaystyle{ i - j \in S }[/math], where subtraction is carried out modulo [math]\displaystyle{ \,p }[/math]. The adjacency matrix of a circulant graph is a symmetric circulant.
2. (A circulant graph [math]\displaystyle{ \,G(n,d) }[/math]). The circulant graph [math]\displaystyle{ \,G(n,d) }[/math] with [math]\displaystyle{ d \geq 2 }[/math] is defined as follows. The vertex set is [math]\displaystyle{ V = \{0,1,2, \ldots, n-1\} }[/math], and the edge set is [math]\displaystyle{ E = \{(u,v)| \exists i, 0 \leq i \leq \lceil \log_{d}(n)\rceil - 1 }[/math], such that [math]\displaystyle{ u + d^{i} \equiv v\pmod{n}\} }[/math].
3. (A circulant graph [math]\displaystyle{ \,G(cd^{m},d) }[/math]). The circulant graph [math]\displaystyle{ \,G(cd^{m},d) }[/math] has [math]\displaystyle{ \,cd^{m} }[/math] vertices [math]\displaystyle{ \,(0 \lt c \lt d) }[/math]. [math]\displaystyle{ V = \{0, \ldots, cd^{m} - 1\} }[/math] is the set of vertices, and [math]\displaystyle{ E = \{(v,w), v, w \in V/\exists i, 0 \leq i \leq \lceil \log_{d}cd^{m}\rceil - 1, v \pm d^{i} \equiv w\pmod{cd^{m}}\}. }[/math] An edge between [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w = v \pm d^{i} }[/math] will have the label [math]\displaystyle{ d^{i} }[/math]. It is easy to see that [math]\displaystyle{ \,G(cd^{m},d) }[/math] is a Cayley graph defined on an abelian group.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.
