Cayley digraphs of a group

116 Views Asked by At

I could not find an answer to the questions online. How many loopless Cayley digraphs of a group G there are? How many loopless Cayley graphs of a group G there are if |G| = n and G has i self-inverse elements? Could someone advise a literature regarding this topic or explain an answer?

My thoughts about it

The answer to the first question is $2^{|G|-1}$, since its the number of the subsets not containing identity elements. The answer to the second question is $2^{({n-i}/2)+i}$ since if the element is not self-inverse element we pair them up and either include both or none, so its ${n-i}/2$ and $+i$ since I elements are self inverse.

1

There are 1 best solutions below

4
On

Once you fix a finite group $G$, a Cayley di/graph $\Gamma = \Gamma(G, S)$ depends only on a generating set $S$ of $G$. What you missed is $S$ must generates the whole group $G$, as in the definition of the Cayley di/graph.

A loop in a Cayley di/graph $\Gamma$ corresponds to the identity $1 \in S$. So your first question asks the number of generating sets $S$ of $G$ with $1 \not\in S$. (This equals the half of the number of generating sets of $G$.) It sounds hard problem and I don't know the answer. Anyway, it must not be $2^{\lvert G \rvert - 1}$ in general.

Your second question sounds just wrong. It doesn't make sense to me. Why involutions (self-inverses) matter?