automorfismos en gráficas vértice-transitivas

Question

Alguien sabe si hay una caracterización para los grupos de automorfismos de gráficas vértice-transitivas? El teorema de Frucht dice que todo grupo es grupo de automorfismos de alguna gráfica, pero su construcción casi nunca da gráficas vértice transitivas.

Answer 1

Yo que tú me daría un chapuzón en el "Algebraic graph theory" de Godsyl. Por ejemplo, puedes encontrar lo siguiente:

Si X es una gráfica vértice-transitiva con un número primo de vértices, entonces X es un core.

Un core en una gráfica tal que cualquier homomorfismo de ella en sí misma es una biyección, o equivalentemente, su "monoide de endomorfismos" es igual a su "grupo de automorfismos".

No creo que haya una caracterización completa como la que pides, pero si bajo ciertas hipótesis... pero si lo que quieres obtener son gráficas vértice-transitivas, Las gráficas de Cayley son vértice transitivas. 

Me pregunto si ¿la gráfica de líneas de una gráfica arista-transitiva es vértice-transitiva?

Ojalá te ayude mi respuesta.

Comments

Gracias por el tip. Lo que quiero en realidad es probar una conjetura que tengo acerca de un teorema de Sabidoussi. El teorema es equivalente a esto:

Una gráfica X es gráfica de Cayley de su propio grupo de automorfismos si y sólo si Aut(X) actúa regularmente en los vértices.

Tengo la conjetura de que sólo hay 3 gráficas que cumplen esto (las gráficas con 1 o 2 vértices), pero no tengo idea de como probarlo (o refutarlo). Encontré un artículo aquí: www.ams.org/journals/proc/...0/S0002-9939-1964-0159321-0.pdf‎
en el que se acercan a mi resultado, pero me di cuenta que su demostración está mal, así que sigo en ceros.

---

Buscando ese paper en mathscinet he encontrado algunos otros que te puedan interesar, por ejemplo:
- Khosravi, Behnam; Khosravi, Bahman, A characterization of Cayley graphs of Brandt semigroups. Bull. Malays. Math. Sci. Soc. (2) 35 (2012), no. 2, 399–410.
-  Zgrablić, Boris On quasiabelian Cayley graphs and graphical doubly regular representations. Algebraic and topological methods in graph theory (Lake Bled, 1999). Discrete Math. 244 (2002), no. 1-3, 495–519.