Complexité de la reconnaissance des graphes vertex-transitifs

Je ne connais pas le domaine de la théorie de la complexité impliquant des groupes, je m'excuse donc si c'est un résultat bien connu.

Question 1. Soit un simple graphe non orienté d'ordre n . Quelle est la complexité de calcul (en termes de n ) pour déterminer si G est transexuel?$G$$n$$n$$G$

Rappelons qu'un graphe est transexuel si A u t ( G ) agit transitivement sur V ( G ) $G$$\mathrm{Aut}(G)$$V(G).$

Je ne suis pas sûr que la définition ci-dessus permette un algorithme de temps polynomial car il se peut que l'ordre de soit exponentiel.$\mathrm{Aut}(G)$

Cependant, les graphes vertex-transitifs ont d'autres propriétés structurelles qui pourraient être exploitées afin de pouvoir les déterminer efficacement, donc je ne sais pas quel est le statut de la question ci-dessus.

Une autre sous-classe intéressante de graphes vertex-transitifs qui a encore plus de structure est la classe des graphes de Cayley . Il est donc naturel de poser également la question connexe suivante

Question 2. Quelle est la complexité de calcul pour déterminer si un graphe est un graphe de Cayley?$G$

Je n'ai pas de réponse complète, mais je pense que les deux problèmes sont ouverts.

L'article de Jajcay, Malnič, Marušič [3] est lié à votre première question. Ils fournissent quelques outils pour tester la transitivité des vertex. Ils disent dans l'introduction que:

Pour un graphe fini donné , il est décidément difficile de déterminer si Γ est vertex-transitif, et la réponse ultime ne vient généralement qu'après qu'une partie substantielle du groupe d'automorphisme complet de Γ a été déterminée.$\Gamma$$\Gamma$$\Gamma$

Notez que le test de transitivité des sommets peut être effectué en testant l'isomorphisme du graphe fois. Faites deux copies G et G ′ de votre graphique, avec des ancres spéciales (comme des chemins de longueur n + 1 ) à u ∈ V ( G ) et v ∈ V ( G ′ ) . Il existe un isomorphisme entre G et G ′ si et seulement si le graphe d'origine a un automorphisme mappant u à v . Vous pouvez ainsi tester la tansitivité des sommets en fixant un sommet$n−1$$G$$G'$$n+1$$u \in V(G)$$v \in V(G')$$G$$G'$$u$$v$ , et vérifier qu'il existe des automorphismes mappant x à tous les autres sommets.$x$$x$

Notez également que si le test de transitivité des sommets peut être effectué en temps polynomial, il en est de même pour le test d'isomorphisme pour les graphes transexuels. En effet, deux graphes vertex-transitifs sont isomorphes si et seulement si leur union disjointe est vertex-transitive. Je crois que la complexité de l'isomorphisme des graphes pour les graphes vertex-transitifs n'est pas connue.

Pour la 2e question, j'ai trouvé un résultat partiel. Un graphe circulant est un graphe de Cayley sur un groupe cyclique. Evdokimov et Ponomarenko [2] montrent que la reconnaissance des graphes circulants peut se faire en temps polynomial. Le chapitre du livre d'Alspach [1, Chapitre 6: Graphiques Cayley, Section 6.2: Reconnaissance] serait également intéressant pour vous, même s'il dit que:

Nous ignorerons le problème informatique de savoir si un graphe arbitraire est un graphe de Cayley. Au lieu de cela, nous supposons toujours que les graphiques Cayley ont été décrits en termes de groupes sur lesquels ils sont construits, ainsi que les ensembles de connexions. Pour la plupart des problèmes, ce n'est pas un inconvénient.

1. Beineke, Wilson, Cameron. Sujets en théorie des graphes algébriques . Cambridge University Press, 2004.
2. Evdokimov, Ponomarenko. Graphes circulants: reconnaissance et test d'isomorphisme en temps polynomial. Mathématiques de Saint-Pétersbourg. J. 15 (2004) 813-835. doi: 10.1090 / S1061-0022-04-00833-7
3. Jajcay, Malnič, Marušič. Sur le nombre de marches fermées dans les graphes vertex-transitifs. Mathématiques discrètes. 307 (2007) 484-493. doi: 10.1016 / j.disc.2005.09.039