¿Cómo calcular el número de automorfismos de un grafo dado?

Question

¿Cómo se determina el número de isomorfismos que tiene un grafo consigo mismo?

Por ejemplo, supongamos que tenemos el siguiente gráfico:

¿Cómo puedo determinar cuántos isomorfismos hay a partir de la propia G?

Answer 1

Aquí están todos 48 automorfismos generados por Salvia :

$$\begin{gathered} {\text{() }} \hfill \\ {\text{(d f)(e g)(h k) }} \hfill \\ {\text{(d e) }} \hfill \\ {\text{(a b) }} \hfill \\ {\text{(b m) }} \hfill \\ {\text{(f g) }} \hfill \\ {\text{(a m b) }} \hfill \\ {\text{(a b)(f g) }} \hfill \\ {\text{(a b)(d f)(e g)(h k) }} \hfill \\ {\text{(a b m) }} \hfill \\ {\text{(b m)(d e) }} \hfill \\ {\text{(d e)(f g) }} \hfill \\ {\text{(b m)(d f)(e g)(h k) }} \hfill \\ {\text{(d g e f)(h k) }} \hfill \\ {\text{(d f e g)(h k) }} \hfill \\ {\text{(b m)(f g) }} \hfill \\ {\text{(a b)(d e) }} \hfill \\ {\text{(d g)(e f)(h k) }} \hfill \\ {\text{(a m) }} \hfill \\ {\text{(a m b)(f g) }} \hfill \\ {\text{(b m)(d e)(f g) }} \hfill \\ {\text{(a m b)(d f)(e g)(h k) }} \hfill \\ {\text{(a b)(d f e g)(h k) }} \hfill \\ {\text{(a m b)(d e) }} \hfill \\ {\text{(a b m)(d f)(e g)(h k) }} \hfill \\ {\text{(b m)(d f e g)(h k) }} \hfill \\ {\text{(a b m)(d e) }} \hfill \\ {\text{(a b)(d e)(f g) }} \hfill \\ {\text{(b m)(d g e f)(h k) }} \hfill \\ {\text{(a b m)(f g) }} \hfill \\ {\text{(a b)(d g e f)(h k) }} \hfill \\ {\text{(a b m)(d g e f)(h k) }} \hfill \\ {\text{(a b)(d g)(e f)(h k) }} \hfill \\ {\text{(a m b)(d e)(f g) }} \hfill \\ {\text{(a m b)(d f e g)(h k) }} \hfill \\ {\text{(a b m)(d f e g)(h k) }} \hfill \\ {\text{(a m)(d f)(e g)(h k) }} \hfill \\ {\text{(a m)(d e) }} \hfill \\ {\text{(b m)(d g)(e f)(h k) }} \hfill \\ {\text{(a m b)(d g e f)(h k) }} \hfill \\ {\text{(a m)(f g) }} \hfill \\ {\text{(a b m)(d e)(f g) }} \hfill \\ {\text{(a m b)(d g)(e f)(h k) }} \hfill \\ {\text{(a m)(d e)(f g) }} \hfill \\ {\text{(a m)(d f e g)(h k) }} \hfill \\ {\text{(a b m)(d g)(e f)(h k) }} \hfill \\ {\text{(a m)(d g e f)(h k) }} \hfill \\ {\text{(a m)(d g)(e f)(h k)}} \hfill \\ \end{gathered}$$

Answer 2

Esperemos que alguien conozca una forma mejor de hacerlo, pero en realidad es posible simplemente contarlos.

¿A cuántos lugares se puede asignar c? ¿Y a, m y b? etc.

El teorema del estabilizador orbital (si lo conoces) facilita un poco las cosas. Yo lo aplicaría a

una de d, e, f o g.

Answer 3

A mano no es fácil. Puede hacerse para grafos pequeños como éste. Observa los vértices que son "diferentes" de los demás. Por ejemplo, cualquier automorfismo debe fijar $c$ porque $c$ es el único vértice cuyos vecinos tienen grado $1$ . $a$ , $b$ y $m$ puede permutarse libremente, esto da automorfismos $(a \ b), (a \ m), (b \ m), (a \ b \ m), (a \ m \ b)$ . También tiene seis vértices de grado $3$ ¿cómo pueden permutarse? ¿Cómo pueden distinguirse entre sí?

Cuento 48 automorfismos.

Answer 4

Considerando el hecho de que el grafo isomorfo $H$ difiere del gráfico inicial $G$ por una permutación de las columnas de la matriz de adyacencia, podemos tener posiblemente $n!$ de tales permutaciones, donde $n$ es un número de vértices de ambos grafos.