Cayley Graph and Cayley Digraph

Question

I am trying to understand the definition of a Cayley graph of a group $G$:

1. Is Cayley graph and Cayley Digraph the same thing?
2. If Cayley graph and digraph have the same meaning, then can we define an Undirected Cayley graph for any group $G$ and a generating set $S$ of $G$?
3. Let $G$ be a group and $S$ be a generating set of $G$. Then what can you say about the Cayley digraph of $(G, S)$, $(G, S^{-1})$ and $(G, S\cup S^{-1})$? Do they make any difference?

Answer 1

I think the answer depends on which author you're reading. The short answer is "no - they are not necessarily the same thing". The tl;dr is that some authors use Cayley Graph to mean a directed graph, and others use it to mean an undirected graph, and will use Cayley Digraph explicitly when they want to allow directed edges. Unfortunately, there is no getting around this.

To answer your 3 points, then:

1. It depends who you are reading. If your author only deals with undirected graphs, it is likely that "Cayley Graph" will mean undirected, and should the need for a directed version arises, they will note it explicitly by writing "Cayley DiGraph". If instead your author permits directed graphs, then it is likely that "Cayley Graph" will be directed by default, and you will have to explicitly symmetrize it if you want to work with an undirected version. Naturally some authors of the second type will use "Cayley Digraph" throughout anyways, in the interest of avoiding potential misunderstanding when talking to authors of the first type.

2. Yes. If you are an author of the second type, and want to talk about a undirected Cayley Graph, you might explicitly call it an "Undirected Cayley Graph" to avoid this confusion. You have already found out how to do this, in your next question.

3. The Cayley Digraph given by $S$ is the same as the digraph given by $S^{-1}$ but with all the arrows reversed. If both $s, s^{-1} \in S$ then we often write a single, undirected edge. So the set $\overline{S} = S \cup S^{-1}$ is called the Symmetrized version of $S$, and working with $\overline{S}$ gives the same graph, but forces it to be undirected. Often authors of the first kind will write $\Gamma_S$ where an author of the second kind would explicitly write $\Gamma_{\overline{S}}$.

Sorry there's no "correct" answer here. Math is full of these small ambiguities, which are mostly harmless, but you need to be careful that you know the quirks of each author (sometimes each paper!) when reading.

---

I hope this helps ^_^

Answer 2

As often happens in mathematics, the terminology here is somewhat fuzzy, and (as sometimes happens) there is an explanation for that. The word graph has a more general meaning than the word digraph and refers (among other things) to a discrete geometric object "made of vertices and edges (joining vertices)". This includes different situations, in particular:

1. the edges do not have any direction. These are precisely called undirected graphs, but it is common to refer to them simply as graphs.
2. every edge has a direction (to one of its endpoints). These are called directed graphs (digraphs for short), but if no ambiguity appears they are sometimes also called graphs to lighten terminology.

Hence, the answer to your first question is NO (as long as when you say "graphs" you refer to "undirected graphs"): digraphs have directed edges and graphs don't.

Now, given a group $G$ and a set $X$ of generators for $G$, you can define the Cayley digraph of $G$ w.r.t. $X$ as the directed graph with vertices the elements of $G$, and for each $g \in G$ and each $x\in X$, an edge from $g$ to $gx$ labeled by $x$.

The point is that if you choose a symmetrized generating set $X = X \cup X^{-1}$ (which is quite usual), then the edge direction is sort of redundant: as far as you know that the endpoints are $g$ and $h$, the label of the corresponding edge must either be $g^{-1} h$ or $h^{-1} g$ (if you go in the opposite direction). Hence you can avoid de direction (making it an undirected graph) and just deduce de direction from the labeling. This is why some people don't care much about the direction in Cayley (di)graphs. I think that this last paragraph, besides trying to explain the ambiguity and why it is not important, answers your second and third questions.