Número de automorfismos de um gráfico para isomorfismo de gráfico

Sejam $G$ e $H$ dois gráficos conectados em $r$ de tamanho . Vamos ser o conjunto de permutações tal que . Se então é o conjunto de automorphisms de . $n$ $A$ $P$ $PGP^{-1}=H$ $G=H$ $A$ $G$

Qual é o limite superior mais conhecido no tamanho de $A$ ?
Existem resultados para classes gráficas específicas (que não contêm gráficos completos / de ciclo)?

Nota: A construção do grupo automorfismo é pelo menos tão difícil (em termos de complexidade computacional) quanto a solução do problema de isomorfismo gráfico. De fato, apenas contar os automorfismos equivale a tempo polinomial ao isomorfismo do gráfico, cf. R. Mathon, "Uma observação no problema de contagem do isomorfismo gráfico".

reference-request graph-theory co.combinatorics graph-isomorphism gr.group-theory Jim
fonte

Wormald mostrou que, se é um gráfico regular conectado com 2n vértices, o número de automorfismos de divide . Em particular, isso fornece um limite superior exponencial não trivial para o caso regular. Talvez haja resultados nesta linha para gráficos gerais em geral . $G$ $3$ $G$ $3n\cdot 2^n$ $3$ $k$

Para um limite inferior, considere a fórmula com entradas cujos portões são adicionais $F$ $n$ portas do ventilador-em 2. Em seguida, usando uma resut deToranpode-se construir um gráfico -Regular com vértices cujo grupo automorphism codifica todas as avaliações possíveis de . Isso implica que o número de automorfismos de é pelo menos . Isso mostra que existe um limite inferior exponencial para o número de automorfismos degráficos regulares em função do número de vértices. $\mod k$ $k$ $G(F)$ $O(k^2\cdot n)$ $F$ $G(F)$ $k^n$ $k$

Mateus de Oliveira Oliveira
fonte

Por favor, considere o gráfico a seguir: 1.

gráfico regular e

gráfico regular (nenhum deles está completo ou gráfico de ciclo) são unidos entre si pelo número E de arestas, digamos que este gráfico unido seja um gráfico irregular

2. cada o vértice do gráfico regular

tem arestas com o gráfico regular

. Não há dois vértices do gráfico regular

, que possuem o mesmo número de arestas com o gráfico regular

. O automorfismo de G pode ser exponencial?

r_{1}

$r_1$

r_{2}

$r_2$

G

$G$

r_{1}

$r_1$

r_{2}

$r_2$

r_{1}

$r_1$

r_{2}

$r_2$

Jim

sim. O gráfico G2 pode ter um número exponencial de automorfismos. Seja H1 qualquer gráfico regular r1 com n vértices, numerados 1 ... n.Deixe H2 ser um gráfico obtido pelo seguinte processo (dividido em 3 comentários). Seja D o gráfico de diamantes, isto é, um ciclo de 4 com uma aresta conectando dois vértices anteriormente não adjacentes. Diga que esses dois vértices são os vértices internos de D. Os outros dois vértices são os vértices externos de D. Claramente, existe um automorpismo que troca ambos os vértices internos e deixa os vértices externos intocados.

Mateus de Oliveira Oliveira

Agora, considere a união disjunta de dois ciclos C1 e C2 com n (n + 1) / 2 vértices numerados de 1 a n (n + 1) / 2. Considere também n (n + 1) / 2 cópias do gráfico diamod. Agora, para cada i, conecte uma das partes externas de D_i ao i-ésimo vértice de C1 e o outro vértice externo ao i-ésimo vértice de C2. Então o gráfico H2 obtido por esse processo é 3-regular e possui um número exponencial de automorfismos, uma vez que os vértices internos de cada D_i podem ser trocados separadamente.

Mateus de Oliveira Oliveira

Agora, para cada vértice v_j de H1, adicionamos 2j arestas de v_j aos vértices internos de diamantes, de maneira que ambos os vértices internos de um diamante D_i sejam conectados ao mesmo vértice em H1. Isso garante que os vértices internos do diamante ainda possam ser trocados e, portanto, o número total de automorfismos no gráfico G2 é exponencial.

Mateus de Oliveira Oliveira

É fácil mostrar que um gráfico conectado de ordem

e de máxima valência

tem um grupo de automorfismo de ordem no máximo

. Encontre uma ordem dos vértices de forma que, começando com o segundo, cada vértice seja adjacente a pelo menos um vértice que veio antes. Seja

o subgrupo que fixa os primeiros

vértices. Esta é uma cadeia descendente de subgrupos, com

n

$n$

k

$k$

n k (k - 1)^{n - 2}

$nk(k-1)^{n-2}$

G_{i}

$G_i$

i

$i$

| G : G_{1} | \leq n

$|G:G_1|\leq n$

G_{n} = 1

$G_n=1$ . Segue pelo teorema do estabilizador de órbita que

para

| G_{1} : G_{2} | \leq k

$|G_1:G_2|\leq k$

| G_{i} : G_{i + 1} | \leq k - 1

$|G_i:G_{i+1}|\leq k-1$

i \in {2, \dots, n - 1}

$i\in\{2,\ldots,n-1\}$

Verret

Número de automorfismos de um gráfico para isomorfismo de gráfico

Respostas: