Encontrar Automorfismos de Grafos Irregulares a través de Subgrafos Regulares.

Question

Objetivo : Encontrar un conjunto de permutaciones para un grafo irregular que sea también un conjunto de automorfismos. Este proceso de búsqueda utiliza permutaciones de 2 subgrafos regulares del grafo dado.

Descripción y notación :

$G$ es un gráfico irregular, $k$ conectado (no es un gráfico de ciclo completo). $\alpha$ es el conjunto de permutaciones de $G$ (tiene todos los automorfismos).

$G$ tiene 2 tipos de vértices, vértices de $r_1$ grado que crean un $t_1$ subgráfico regular $C$ y vértices de $r_2$ grado que crean un $t_2$ subgráfico regular $D$ .

$C,D$ no son completas / gráfico de ciclo.

$C_1, D_1,A_x$ son matrices de grafos $C,D,G$ respectivamente .

$$ A_x = \left( \begin{array}{ccc} C_1 & E_1 \\ E_1^{T} & D_1 \\ \end{array} \right) $$

$\alpha_1 , \alpha_2 $ son el conjunto de permutaciones de $C_1 , D_1$ respectivamente. $\alpha_1 , \alpha_2 $ incluyen todas las permutaciones posibles necesarias para el automorfismo de $C_1 , D_1$ . Dado que cada uno de $\alpha_1 , \alpha_2 $ tiene $T(m)\leq m^{log_2(m)}$ permutaciones / elementos.

Proceso: Para encontrar un elemento de $\alpha$ , pruebe cada una de las posibles $(P_1,P_2)$ donde $P_1 \in \alpha_1; P_2 \in \alpha_2 $ .

Es necesario comprobar si $E_1,C_1,D_1$ se mantienen sin cambios o no para cada posible $(P_1,P_2)$ . definamos conjunto $\alpha_3$ que tiene todas las $(P_1,P_2)$ para lo cual $E_1,C_1,D_1$ no se modifican.

Preguntas :

1) ¿Es este un proceso / algoritmo correcto para encontrar todos los elementos de $\alpha$ de $(P_1,P_2)$ donde $P_1 \in \alpha_1; P_2 \in \alpha_2 $ es decir $\alpha_3$ tiene todos los elementos de $\alpha$ ?

2) Complejidad de este proceso/algo: es $ T^2(m)$ (complejidad temporal), ¿es ésta una estimación correcta?

Gracias, por favor informe si algo no está claro / indefinido .

Answer 1

Es cierto que cualquier automorfismo de $G$ debe estabilizar ambos subgrafos $C$ y $D$ . Digamos que $C$ tiene $c$ vértices y $D$ tiene $d$ vértices. Así que se pueden encontrar grupos de automorfismo de $C$ y $D$ entonces si $a_{1}$ es un automorfismo de $c$ y $a_{2}$ es un automorfismo de $D$ puede comprobar si $a_{1}a_{2}$ es un automorfismo de $G$ .

Una forma (muy ineficiente pero que no conozco mejor de antemano) de encontrar el grupo de automorfismos de $C$ es probar permutaciones. Digamos $C_{1}$ es la matriz del grafo $C$ y $g$ es una permutación de $\{1,2,\ldots,c\}$ . Convertimos $g$ a una matriz de permutación $G$ a continuación, compruebe si $G C_{1} G^{T} = C_{1}$ . Si es así $g$ es un automorfismo de $C_{1}$ (al igual que todas las potencias de $g$ ).

Al encontrar automorfismos, todos los productos de los automorfismos vuelven a ser automorfismos, por lo que puede ser complicado ser inteligente sobre qué permutaciones probar y en qué orden (no necesariamente quieres probar cada permutación, pero al mismo tiempo puede ser costoso computacionalmente determinar qué permutaciones no necesitas probar). Espero que alguien más listo que yo pueda aportar algoritmos mejores.

Ahora bien, una vez que se tienen grupos de automorfismo de $C$ y $D$ no se le garantiza que $g_{1} \in \alpha_{1}$ , $g_{2} \in \alpha_{2}$ implica que $g_{1}g_{2} \in \alpha$ necesita comprobar que $\begin{bmatrix} G_{1} & 0\\0 &G_{2} \end{bmatrix} \begin{bmatrix} C_{1} & E_{1}^{T}\\E_{1} & D_{1} \end{bmatrix} \begin{bmatrix} G_{1}^{T} & 0\\0&G_{2}^{T} \end{bmatrix} = \begin{bmatrix}C_{1}&E_{1}^{T}\\E_{1}&D_{1}\end{bmatrix}$ .