En la página de Wikipedia del grafo de Petersen se menciona que no es un grafo de Cayley.
¿Cómo se prueba esto?
Honestamente ni siquiera sé por dónde empezar. El único criterio que se me ocurre es que todos los vértices deben tener el mismo grado. Además, el grado siendo impar debería implicar que un generador del grupo tiene orden 2. ¿Pero entonces cómo procedo?
Editar: Como ya se mencionó en los comentarios, el enlace no respondió a mi pregunta.
$G = C_{10}$ es abeliano, y si $a$ y $b$ son dos de los generadores en el grafo de Cayley entonces $a^{-1}b^{-1}ab$ da un ciclo de longitud $4$, pero el grafo de Petersen no tiene ninguno.
Entonces supongamos que $G= D_{10}$. Como dices, al menos uno de los generadores, digamos $a$ debe tener orden $2$. Si hay un generador $b$ de orden $5$, entonces $(ab)^2 = 1$, así que de nuevo deberíamos tener un ciclo de longitud $4$, pero no hay ninguno.
La única otra posibilidad es que todos los generadores tengan orden $2$, pero entonces no hay un producto de $5$ generadores igual a la identidad. Pero el grafo de Petrsen sí tiene ciclos de longitud $5$, contradicción.
Gracias por tu respuesta. ¿Qué quieres decir con "la otra posibilidad"? ¿Te refieres a otro grupo con 10 elementos en esta parte? Además, ¿por qué dices "al menos uno de los generadores debe tener orden 2"? Está claro que hay elementos de orden 2, pero ¿por qué debo tomar tal elemento como un generador?
El tercer párrafo sigue asumiendo que $G = D_{10}$ (que a menudo se denota confusamente como $D_5$). Cuando mencioné "la única otra posibilidad" quería decir que si no hay ningún generador de orden $5$, entonces todos los generadores deben tener orden $2. Como tú mismo dijiste, el hecho de que el grado sea impar implica que al menos uno de los generadores tiene orden $2$.
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.
0 votos
Supongo que debería haber usado la función de búsqueda
0 votos
Es una buena pregunta, si ya se ha hecho: math.stackexchange.com/questions/348779/… - aunque la respuesta allí podría mejorarse. Básicamente sólo puede corresponder a un grupo pequeño, de los cuales hay un número limitado, y no lo hace.
1 votos
@Joffan Eché un vistazo a la respuesta, pero realmente no la entiendo. Parece ser un hecho de teoría de grupos (que debo aceptar) que solo hay dos grupos con $10$ elementos, estos son $D_5$ y $\mathbb Z_10$. Para mí está claro que para los conjuntos generadores estándar de estos grupos, los grafos de Cayley difieren. ¿Cómo puedo ver que NO hay un conjunto generador que realice el grafo?
0 votos
$C_{10}$ es cíclico, por lo que claramente no es apropiado. $D_{5}$ tiene un elemento de orden 2 que debería conducir a ciclos pares en el grafo, pero Petersen tiene solo ciclos impares (a diferencia, por ejemplo, del grafo del prisma pentagonal).
0 votos
@Joffan ah, ya veo, en un conjunto generador diferente el elemento de orden 2 sería una $n$-palabra. Esto se traduciría entonces en un ciclo de $2n$. ¿Por qué el caso $C_{10}$ es "claro"?
0 votos
¿Las gráficas de Cayley no siempre son de grado par regular?
0 votos
@HenningMakholm No, revisa el gráfico de Cayley de $\mathbb Z_2$
0 votos
@stacky: Ah, cierto.
0 votos
@Joffan Hay ciertamente ciclos de longitud $6$ en el grafo de Petersen.
0 votos
@DerekHolt cierto... tal vez no haya un argumento tan simple.