# 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 possède également d'autres significations.

## Définitions équivalentes

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 à n − 1 de telle manière que, s'il y a deux sommets adjacents de numéros x et (x + d) mod n, alors deux sommets quelconques de numéros z et (z + d) mod n 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.

## Exemples et propriétés
### Exemples

* Un graphe cycle est un graphe circulant ;
* un graphe couronne avec un nombre de sommets égal à 2 modulo 4 (donc de la forme 4k+2) ;
* un graphe de Paley : le graphe de Paley d'ordre n, où n est un nombre premier congruent à 1 modulo 4, est un graphe dont les sommets sont les entiers de 0 à n − 1 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 graphe d'antiprisme (en).

### Propriétés

Un graphe circulaire à plus de 2 sommets est biconnexe, sans isthme, cyclique, hamiltonien , admet une notation LCF, est régulier, sommet-transitif.
Le nombre de graphes circulants sur n=1, 2, ... sommets (y compris le graphe vide) est 1, 2, 2, 4, 3, 8, 4, 12, ... (suite A049287 de l'OEIS),
Dans le jeu d'échecs, le graphe des tours de taille m × n est un graphe dont les sommets sont les carrés d'un échiquier de taille m × n et qui a une arête entre deux carrés si une tour d'échecs peut se déplacer de l'un à l'autre en un seul mouvement. Si m et n sont premiers entre eux, alors le graphe des tours est un graphe circulant. En effet, ses symétries incluent comme sous-groupe le groupe cyclique C $_{mn}$ $\simeq$ C $_m$ × C $_n$. Plus généralement, dans ce cas, le produit tensoriel des graphes de deux circulants à m et n sommets est lui-même un circulant.
De nombreux minorants des nombres de Ramsey preuvent se ramener à des exemples de graphes circulants qui ont de petites cliques maximales et de petits ensembles indépendants maximaux

## Un exemple concret

On note $C_{n}({s_{1},\ldots ,s_{k}})$ le graphe avec $n$ nœuds étiquetés $0,1,\ldots ,n-1$ et « sauts » $s_{1},\ldots ,s_{k}$ où chaque nœud i est adjacent aux 2 k nœuds $i\pm s_{1},\ldots ,i\pm s_{k}\mod n$. Par exemple, le graphe $C_{n}({1,2,\ldots ,n/2})$ est le graphe complet, et le graphe $C_{n}({1})$ est le graphe cycle.
* Le graphe $C_{n}({s_{1},\ldots ,s_{k}})$ est connexe si et seulement si $\gcd(n,s_{1},\ldots ,s_{k})=1$.
* Pour des entiers $1\leq s_{1}<\cdots <s_{k}$ fixés, le nombre $T(C_{n}({s_{1},\ldots ,s_{k}}))$ d'arbres couvrant vérifie $T(C_{n}({s_{1},\ldots ,s_{k}}))=na_{n}^{2}$, où $a_{n}$ satisfait est une suite définie par récurrence d'ordre $2^{s_{k}-1}$.
* En particulier, $t(C_{n}({1,2}))=nF_{n}^{2}$ où $F_{n}$ est le n-ième nombre de Fibonacci.

## Graphes circulants auto-complémentaires

Un graphe auto-complémentaire est un graphe isomorphe à son graphe complémentaire. Par exemple, un graphe cycle à cinq sommets est auto-complémentaire et est également un graphe circulant. Plus généralement, tout graphe de Paley d'ordre premier est un graphe circulant auto-complémentaire. Horst Sachs a montré que, si un entier n a tous ses facteurs premiers congrus à 1 modulo 4, alors il existe un graphe circulant auto-complémentaire à n sommets. Il a conjecturé que cette condition est également nécessaire, à savoir qu'il n'existe pas de circulant auto-complémentaire pour d'autres valeurs de n. La conjecture a été prouvée quelque 40 ans plus tard par Vilfred.

## La conjecture d'Ádám

Une numérotation circulante d'un graphe circulant est, par définition, un étiquetage des sommets du graphe par les entiers de 0 à n − 1 tels que si deux sommets numérotés x et y sont adjacents, alors deux sommets numérotés z et (z − x + y) mod n sont également adjacents pour tout z. De manière équivalente, une numérotation circulante est une numérotation des sommets pour lesquels la matrice d'adjacence du graphe est une matrice circulante.
Soit a un entier premier avec n, et soit b un entier quelconque. Alors la fonction linéaire qui envoie un nombre x sur ax + b transforme une numérotation circulante en une autre numérotation circulante. András Ádám a conjecturé que ces applications linéaires sont la seules façon de renuméroter un graphe circulant tout en préservant la propriété circulante; en d'autres termes, si G et H sont des graphes circulants isomorphes, avec des numérotations différentes, alors il existe une application linéaire qui transforme la numérotation pour G dans la numérotation pour H . Cependant, la conjecture d'Ádám est fausse. Un contre-exemple est donné par des graphes G et H avec 16 sommets chacun ; un sommet x dans G est connecté aux six voisins x ± 1, x ± 2 et x ± 7 modulo 16, tandis que dans H les six voisins sont x ± 2, x ± 3 et x ± 5 modulo 16. Ces deux graphes sont isomorphes, mais leur isomorphisme ne peut pas être réalisé par une application linéaire.
La conjecture de Toida affine la conjecture d'Ádám en ne considérant que la classe de graphes circulants où toutes les différences entre les sommets adjacents sont premières le nombre de sommets. Selon cette conjecture affinée, ces graphes circulants devraient avoir la propriété que toutes leurs symétries proviennent des symétries du groupe additif sous-jacent des entiers modulo n . Cela a été prouvé par Muzychuk, Klin et Pöschel en 2001 et par Dobson et Morris 2002$^,$.

## Aspects algorithmiques

Il existe un algorithme de reconnaissance en temps polynomial pour les graphes circulants, et le problème d'isomorphisme pour les graphes circulants peut également être résolu en temps polynomial$^,$.