¿Es$K_n\times K_n$ una gráfica de Cayley?

Question

Deje que$K_n\times K_n$ sea el producto cartesiano de dos gráficos completos.

Es$K_n\times K_n$ es el gráfico de Cayley o no?

Sé que tengo que usar este lema:

Un gráfico conectado$G$ es Cayley si y solo si existe un subgrupo$H\subset\operatorname{Aut}(G)$ que actúa simplemente de forma transitiva (regularmente) en$V (G)$.

pero no se como

Por favor aconsejame.

Answer 1

En primer lugar, se observa que el $K_n$ es un grafo de Cayley. Considerar el grupo cíclico $C_n$. Si tomamos como un set de generación de energía a todos los de $C_n$, el resultado de Cayley gráfico es $K_n$. Tenga en cuenta que $C_n$ actúa simplemente transitivamente en el gráfico: si $g$ es un generador de $C_n$, y los vértices están etiquetados $g^k$, la acción es la multiplicación (y dado que es un grupo abelian, no tenemos que especificar en qué lado).

Ahora, considere la posibilidad de la acción de la $C_n\times C_n$$K_n\times K_n$. Es directa que si $G$ actúa en $X$ $H$ actúa en $Y$, $G\times H$ actúa en $X\times Y$. Por otra parte, si las acciones son transitivos o libre, por lo que es el producto resultante de la acción. Por lo tanto, el producto de dos grafos de Cayley es de nuevo un grafo de Cayley.