4 votos

¿EsKn×KnKn×Kn una gráfica de Cayley?

Deje queKn×Kn sea el producto cartesiano de dos gráficos completos.

EsKn×Kn es el gráfico de Cayley o no?

Sé que tengo que usar este lema:

Un gráfico conectadoG es Cayley si y solo si existe un subgrupoHAut(G) que actúa simplemente de forma transitiva (regularmente) enV(G).

pero no se como

Por favor aconsejame.

1voto

Andy Puntos 21

En primer lugar, se observa que el Kn es un grafo de Cayley. Considerar el grupo cíclico Cn. Si tomamos como un set de generación de energía a todos los de Cn, el resultado de Cayley gráfico es Kn. Tenga en cuenta que Cn actúa simplemente transitivamente en el gráfico: si g es un generador de Cn, y los vértices están etiquetados gk, 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 Cn×CnKn×Kn. Es directa que si G actúa en X H actúa en Y, G×H actúa en X×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.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X