No tengo conocimiento en el área de la teoría de la complejidad que involucra grupos, así que me disculpo si este es un resultado bien conocido.
Pregunta 1. Sea una simple gráfica no dirigida de orden n . ¿Cuál es la complejidad computacional (en términos de n ) de determinar si G es transitivo de vértice?
Recuerde que una gráfica es transitiva de vértice si A u t ( G ) actúa transitivamente en V ( G ) .
No estoy seguro de si la definición anterior permite un algoritmo de tiempo polinómico, ya que puede ser que el orden de sea exponencial.
Sin embargo, los gráficos transitivos de vértice tienen algunas otras propiedades estructurales que podrían explotarse para poder determinarlas de manera eficiente, por lo que no estoy seguro de cuál es el estado de la pregunta anterior.
Otra subclase interesante de gráficos transitivos de vértices que tiene aún más estructura es la clase de gráficos de Cayley . Por lo tanto, es natural plantear también la siguiente pregunta relacionada
Pregunta 2. ¿Cuál es la complejidad computacional de determinar si un gráfico es un gráfico de Cayley?
Respuestas:
No tengo una respuesta completa, pero creo que ambos problemas están abiertos.
El artículo de Jajcay, Malnič, Marušič [3] está relacionado con su primera pregunta. Proporcionan algunas herramientas para probar la transitividad de los vértices. Dicen en la introducción que:
Tenga en cuenta que la prueba de transitividad de vértices se puede hacer probando el isomorfismo gráfico veces. Haga dos copias G y G ' de su gráfico, con anclajes especiales (como trazados de longitud n + 1 ) en u ∈ V ( G ) y v ∈ V ( G ' ) . Hay un isomorfismo entre G y G ' si y solo si el gráfico original tiene un mapeo de automorfismo u a v . Por lo tanto, puede probar la tansitividad de vértices arreglando un vérticen - 1 sol sol′ n + 1 u ∈ V( G ) v ∈ V( G′) sol sol′ tu v , y comprobando que hay mapeos de automorfismos x a todos los otros vértices.X X
También tenga en cuenta que si la prueba de transitividad de vértices se puede hacer en tiempo polinómico, entonces también lo es la prueba de isomorfismo para gráficos transitivos de vértices. Esto se debe a que dos gráficos transitivos de vértice son isomórficos si y solo si su unión disjunta es transitiva de vértice. Creo que se desconoce la complejidad del isomorfismo gráfico para los gráficos transitivos de vértices.
Para la segunda pregunta, encontré un resultado parcial. Un gráfico circulante es un gráfico de Cayley en un grupo cíclico. Evdokimov y Ponomarenko [2] muestran que el reconocimiento de los gráficos circulantes se puede hacer en tiempo polinómico. También el capítulo del libro de Alspach [1, Capítulo 6: Gráficos de Cayley, Sección 6.2: Reconocimiento] sería interesante para usted, aunque dice que:
fuente