Cayley graph

Cayley graph — граф Кэли.

1. Let [math]\displaystyle{ Z_{n} = \{0, 1, \ldots, n-1\} }[/math] be an additive abelian group of integers modulo [math]\displaystyle{ \,n }[/math], and [math]\displaystyle{ \,H }[/math] be a subset of [math]\displaystyle{ \,Z_{n} }[/math] with [math]\displaystyle{ 0 \not \in H }[/math]. Then the Cayley graph [math]\displaystyle{ C_{Z_{n},H} }[/math] is an undirected graph with [math]\displaystyle{ V(C_{Z_{n},H}) = Z_{n} }[/math], and [math]\displaystyle{ E(C_{Z_{n},H}) = \{(x,x+y): \; x \in Z_{n}, y \in H }[/math] and the addition is taken modulo [math]\displaystyle{ \,n\} }[/math]. The adjacency matrix of [math]\displaystyle{ C_{Z_{n},H} }[/math] is [math]\displaystyle{ n \times n }[/math] symmetric circulant with entries 0 and 1.

2. Let [math]\displaystyle{ \,\Gamma }[/math] be a finite group and [math]\displaystyle{ \,S }[/math] be a symmetric generator set of [math]\displaystyle{ \,\Gamma }[/math], i.e. [math]\displaystyle{ \langle S \rangle = \Gamma, \; s \in S \Rightarrow s^{-1} \in S\mbox{ and }1_{\Gamma} \not \in S }[/math]. The Cayley graph [math]\displaystyle{ \,G_{S}(\Gamma) }[/math] is defined as an undirected graph with its vertex set [math]\displaystyle{ \,V = \Gamma }[/math] and edge set [math]\displaystyle{ E = \{(g,h)| \; g^{-1}h \in S\} }[/math].

Литература

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