Nombre d'automorphismes d'un graphique pour l'isomorphisme du graphique

Soit $G$ et $H$ deux graphes connectés $r$ réguliers de taille $n$ . Soit $A$ l'ensemble des permutations $P$ tel que $PGP^{-1}=H$ . Si $G=H$ alors $A$ est l'ensemble des automorphismes de $G$ .

Quelle est la limite supérieure la plus connue sur la taille de $A$ ?
Y a-t-il des résultats pour des classes de graphiques particulières (ne contenant pas de graphiques complets / de cycle)?

Remarque: La construction du groupe d'automorphisme est au moins aussi difficile (en termes de complexité de calcul) que la résolution du problème d'isomorphisme du graphe. En fait, le simple comptage des automorphismes équivaut en temps polynomial à l'isomorphisme des graphes, cf. R. Mathon, "Une note sur le problème de comptage des isomorphismes des graphes".

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

$G$ $3$ $G$ $3n\cdot 2^n$ $3$ $k$

$F$ $n$ $\mod k$ $k$ $G(F)$ $O(k^2\cdot n)$ $F$ $G(F)$ $k^n$ $k$

Mateus de Oliveira Oliveira
la source

Veuillez considérer le graphique suivant, 1. Le graphique régulier et le graphique régulier (aucun d'entre eux n'est complet ou graphique de cycle) sont joints l'un à l'autre par le nombre E d'arêtes, disons que ce graphique joint est un graphique irrégulier 2. chaque sommet de graphique régulier a des bords avec le graphique régulier . Il n'y a pas deux sommets du graphique régulier , qui ont le même nombre d'arêtes que le graphique régulier . L'automorphisme de G peut-il être exponentiel?

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

Oui. Le graphe G2 peut avoir un nombre exponentiel d'automorphismes. Soit H1 n'importe quel graphe r1 régulier avec n sommets, numérotés 1 ... n Soit H2 un graphe obtenu par le processus suivant (divisé en 3 commentaires). Soit D le graphe en losange, c'est-à-dire un cycle à 4 avec une arête reliant deux sommets précédemment non adjacents. Disons que ces deux sommets sont les sommets internes de D. Les deux autres sommets sont les sommets externes de D. Il y a clairement un automorhpisme qui permute les deux sommets internes et laisse les sommets externes intacts.

Mateus de Oliveira Oliveira

Considérons maintenant l'union disjointe de deux cycles C1 et C2 avec n (n + 1) / 2 sommets numérotés de 1 à n (n + 1) / 2. Considérez également n (n + 1) / 2 copies du graphe diamod. Maintenant, pour chaque i, connectez l'un des sommets externes de D_i au i-ème sommet de C1 et l'autre sommet externe au i-ème sommet de C2. Alors le graphe H2 obtenu par ce processus est 3-régulier, et a un nombre exponentiel d'automorhpismes, puisque les sommets internes de chaque D_i peuvent être échangés séparément.

Mateus de Oliveira Oliveira

Maintenant, pour chaque sommet v_j de H1, nous ajoutons 2j bords de v_j aux sommets internes des diamants de telle manière que les deux sommets internes d'un diamant D_i soient connectés au même sommet dans H1. Cela garantit que les sommets internes du diamant peuvent toujours être échangés, et donc le nombre total d'automorphismes dans le graphe G2 est exponentiel.

Mateus de Oliveira Oliveira

Il est facile de montrer qu'un graphe connexe d'ordre et de valence maximale a un groupe d'ordre d'automorphisme au plus . Trouvez un ordre des sommets tel que, en commençant par le second, chaque sommet soit adjacent à au moins un sommet précédent. Soit le sous-groupe fixant les premiers sommets. Il s'agit d'une chaîne descendante de sous-groupes, avec et . Il suit le théorème de l'orbite-stabilisateur que et pour .

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$

| 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

Nombre d'automorphismes d'un graphique pour l'isomorphisme du graphique

Réponses: