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.