Graphique auto-complémentaire - Self-complementary graph
Un graphe d'auto-complémentaire est un graphique qui est isomorphe à son complément . Les graphes auto-complémentaires non triviaux les plus simples sont le graphe de chemin à 4 sommets et le graphe de cycle à 5 sommets . Il n'y a pas de caractérisation connue des graphes auto-complémentaires.
Exemples
Chaque graphique de Paley est auto-complémentaire. Par exemple, le graphe de la tour 3 × 3 (le graphe de Paley d'ordre neuf) est auto-complémentaire, par une symétrie qui maintient le sommet central en place mais échange les rôles des quatre milieux latéraux et des quatre coins de la grille. Tous les graphes auto-complémentaires fortement réguliers avec moins de 37 sommets sont des graphes de Paley ; cependant, il existe des graphes fortement réguliers sur 37, 41 et 49 sommets qui ne sont pas des graphes de Paley.
Le graphe de Rado est un graphe auto-complémentaire infini.
Propriétés
Un n graphe d'auto-complémentaire -vertex a un nombre exactement la moitié des arêtes du graphe complet , c. -à- n ( n - 1) / 4 bords, et (s'il y a plus d'un sommet) il doit avoir un diamètre de 2 ou 3. Puisque n ( n −1) doit être divisible par 4, n doit être congru à 0 ou 1 mod 4; par exemple, un graphe à 6 sommets ne peut pas être auto-complémentaire.
Complexité de calcul
Les problèmes de vérifier si deux graphes auto-complémentaires sont isomorphes et de vérifier si un graphe donné est auto-complémentaire sont équivalents en temps polynomial au problème général d' isomorphisme de graphe .
