# Circulant graph

Перейти к:навигация, поиск

Circulant graphциркулянтный граф.

1. Let $\,p$ be a positive integer and $\,S$ be a subset of $\{1,2, \ldots, p-1\}$, such that $i \in S$ implies $p-i \in S$. A circulant graph $\,G(p,S)$ has vertices $0,1, \ldots, p-1$ and two vertices $\,i$ and $\,j$ are adjacent if and only if $i - j \in S$, where subtraction is carried out modulo $\,p$. The adjacency matrix of a circulant graph is a symmetric circulant.

2. (A circulant graph $\,G(n,d)$). The circulant graph $\,G(n,d)$ with $d \geq 2$ is defined as follows. The vertex set is $V = \{0,1,2, \ldots, n-1\}$, and the edge set is $E = \{(u,v)| \exists i, 0 \leq i \leq \lceil \log_{d}(n)\rceil - 1$, such that $u + d^{i} \equiv v\pmod{n}\}$.

3. (A circulant graph $\,G(cd^{m},d)$). The circulant graph $\,G(cd^{m},d)$ has $\,cd^{m}$ vertices $\,(0 < c < d)$. $V = \{0, \ldots, cd^{m} - 1\}$ is the set of vertices, and $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}}\}.$ An edge between $v$ and $w = v \pm d^{i}$ will have the label $d^{i}$. It is easy to see that $\,G(cd^{m},d)$ is a Cayley graph defined on an abelian group.

## Литература

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