Page 90 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 90
3.2 Basic notions and examples
Every red directed edge between x k and x k +1 resembles the fact that x k +1 = x · x k . If we
take S = {x , x 2}, the corresponding graph is a directed circulant graph with jumps 1 and 2.
Here is the diagram for n = 5:
1
x4 x
x3 x2
If we take S = {x ±1, x ±2} then we get an undirected circulant graph with jumps 1 and 2.
It turns out that undirected circulant graphs are precisely Cayley graphs of cyclic groups
with respect to symmetric generating sets.
Example 3.2.38 The dihedral group of order 8 has a presentation D8 = 〈x , y | x 4 = y 2 =
1, x y = x −1〉. The Cayley graph Cay(D8, {x , y }) looks as follows:
yx yx2
x x2
1 x3
y yx3
The red arrows represent multiplication by x from the left, and the blue edges represent
multiplication by y ; since y = y −1, the blue edges are undirected. The dihedral group of
order 8 can be also given by the following presentation: D8 = 〈a ,b | a 2 = b 2 = 1, (a b )2 =
(b a )2〉. In this case, Cay(D8, {a ,b }) is as follows:
Every red directed edge between x k and x k +1 resembles the fact that x k +1 = x · x k . If we
take S = {x , x 2}, the corresponding graph is a directed circulant graph with jumps 1 and 2.
Here is the diagram for n = 5:
1
x4 x
x3 x2
If we take S = {x ±1, x ±2} then we get an undirected circulant graph with jumps 1 and 2.
It turns out that undirected circulant graphs are precisely Cayley graphs of cyclic groups
with respect to symmetric generating sets.
Example 3.2.38 The dihedral group of order 8 has a presentation D8 = 〈x , y | x 4 = y 2 =
1, x y = x −1〉. The Cayley graph Cay(D8, {x , y }) looks as follows:
yx yx2
x x2
1 x3
y yx3
The red arrows represent multiplication by x from the left, and the blue edges represent
multiplication by y ; since y = y −1, the blue edges are undirected. The dihedral group of
order 8 can be also given by the following presentation: D8 = 〈a ,b | a 2 = b 2 = 1, (a b )2 =
(b a )2〉. In this case, Cay(D8, {a ,b }) is as follows:
