4
$\begingroup$

Let $K_n\times K_n$ be the Cartesian product of two complete graphs.

Is $K_n\times K_n$ is Cayley graph or not?

I know that I have to use this lemma:

A connected graph $G$ is Cayley if and only if there exists a subgroup $H\subset\operatorname{Aut}(G)$ which acts simply transitively(regularly) on $V (G)$.

but I don't know how?

Please advise me.

1 Answers 1

1

First, we observe that $K_n$ is a Cayley graph. Consider the cyclic group $C_n$. If we take as a generating set all of $C_n$, the resulting Cayley graph is $K_n$. Note that $C_n$ acts simply transitively on the graph: if $g$ is a generator for $C_n$, and the vertices are labeled $g^k$, the action is just multiplication (and since it is an abelian group, we don't have to specify on which side).

Now, consider the action of $C_n\times C_n$ on $K_n\times K_n$. It is straight forward that if $G$ acts on $X$ and $H$ acts on $Y$, then $G\times H$ acts on $X\times Y$. Moreover, if the actions are transitive or free, so is the resulting product action. Therefore, the product of two Cayley graphs is again a Cayley graph.