Circulant graph

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

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.