Graphe circulant
En théorie des graphes, un graphe circulant est un graphe non orienté sur lequel agit un groupe cyclique d'automorphismes de graphes qui en fait un graphe sommet-transitif. On trouve aussi l'appellation graphe cyclique mais ce terme aussi d'autres significations. Il y a plusieurs manières équivalentes de définir les graphes circulants ; un graphe est circulant lorsque le groupe d'automorphisme du graphe admet un sous-groupe cyclique qui agit de manière transitive sur les sommets du graphe. En d'autres termes, le graphe possède un automorphisme de graphe, qui est une permutation circulaire de ses sommets. la matrice d'adjacence du graphe est une matrice circulante ; les n sommets du graphe peuvent être numérotés de 0 à de telle manière que, s'il y a deux sommets adjacents de numéros x et , alors deux sommets quelconques de numéros z et sont toujours adjacents ; le graphe peut être dessiné (éventuellement avec des croisements d'arêtes) en plaçant ses nœuds sur les sommets d'un polygone régulier de sorte que chaque symétrie de rotation du polygone est également une symétrie du dessin ; le graphe est le graphe de Cayley d'un groupe cyclique. vignette|240x240px| Le graphe d'Andrásfai sur 17 sommets. Un graphe cycle est un graphe circulant ; un graphe couronne avec un nombre de sommets égal à (donc de la forme 4k+2) ; un graphe de Paley : le graphe de Paley d'ordre n, où n est un nombre premier congruent à , est un graphe dont les sommets sont les entiers de 0 à et dans lequel deux sommets sont adjacents si leur différence est un résidu quadratique modulo n. Puisque la présence ou l'absence d'une arête ne dépend que de la différence modulo n de deux nombres de sommets, tout graphe de Paley est un graphe circulant ; une échelle de Möbius est un graphe circulant. un graphe complet. un graphe biparti complet est un graphe circulant s'il a le même nombre de sommets des deux côtés de sa bipartition. un graphe d'Andrásfai ; un graphe de prisme, un . Un graphe circulaire à plus de 2 sommets est biconnexe, sans isthme, cyclique, hamiltonien , admet une notation LCF, est régulier, sommet-transitif.
