Graphe circulant

Modèle:Infobox Graphe 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 circulantsModèle:, ; 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 Modèle:Mvar sommets du graphe peuvent être numérotés de 0 à Modèle:Formule de telle manière que, s'il y a deux sommets adjacents de numéros Modèle:Mvar et Modèle:Formule, alors deux sommets quelconques de numéros Modèle:Mvar et Modèle:Formule 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

Le graphe d'Andrásfai sur 17 sommets.

Exemples

• Un graphe cycle est un graphe circulant ;
• un graphe couronne avec un nombre de sommets égal à Modèle:Nobr (donc de la forme 4k+2) ;
• un graphe de Paley : le graphe de Paley d'ordre Modèle:Mvar, où Modèle:Mvar est un nombre premier congruent à Modèle:Nobr, est un graphe dont les sommets sont les entiers de 0 à Modèle:Formule et dans lequel deux sommets sont adjacents si leur différence est un résidu quadratique modulo Modèle:Mvar. Puisque la présence ou l'absence d'une arête ne dépend que de la différence modulo Modèle:Mvar 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 Modèle:Lien.

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, ... (Modèle:OEIS),

Dans le jeu d'échecs, le graphe des tours de taille Modèle:Formule est un graphe dont les sommets sont les carrés d'un échiquier de taille Modèle:Formule 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 Modèle:Mvar et Modèle:Mvar 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 à Modèle:Mvar et Modèle:Mvar 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,\dots ,s_k)$ le graphe avec $n$ nœuds étiquetés $0,1,\dots ,n-1$ et « sauts » $s_1,\dots ,s_k$ où chaque nœud i est adjacent aux 2 k nœuds $i\pm s_1,\dots ,i\pm s_{k}modn$. Par exemple, le graphe $C_n(1,2,\dots ,n/2)$ est le graphe complet, et le graphe $C_n(1)$ est le graphe cycle.

• Le graphe $C_n(s_1,\dots ,s_k)$ est connexe si et seulement si $\gcd (n,s_1,\dots ,s_k)=1$.
• Pour des entiers $1\le s_1<\cdots <s_k$ fixés, le nombre $T(C_n(s_1,\dots ,s_k))$ d'arbres couvrant vérifie $T(C_n(s_1,\dots ,s_k))=n{a}_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))=n{F}_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 Modèle:Mvar a tous ses facteurs premiers congrus à Modèle:Nobr, alors il existe un graphe circulant auto-complémentaire à Modèle:Mvar 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 Modèle:Mvar. 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 à Modèle:Formule tels que si deux sommets numérotés Modèle:Mvar et Modèle:Mvar sont adjacents, alors deux sommets numérotés Modèle:Mvar et Modèle:Formule sont également adjacents pour tout Modèle:Mvar. 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 Modèle:Mvar un entier premier avec Modèle:Mvar, et soit Modèle:Mvar un entier quelconque. Alors la fonction linéaire qui envoie un nombre Modèle:Mvar sur Modèle:Formule 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 Modèle:Mvar et Modèle:Mvar sont des graphes circulants isomorphes, avec des numérotations différentes, alors il existe une application linéaire qui transforme la numérotation pour Modèle:Mvar dans la numérotation pour Modèle:Mvar . Cependant, la conjecture d'Ádám est fausse. Un contre-exemple est donné par des graphes Modèle:Mvar et Modèle:Mvar avec 16 sommets chacun ; un sommet Modèle:Mvar dans Modèle:Mvar est connecté aux six voisins Modèle:Formule, Modèle:Formule et Modèle:Formule modulo 16, tandis que dans Modèle:Mvar les six voisins sont Modèle:Formule, Modèle:Formule et Modèle:Formule 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 Modèle:Formule . Cela a été prouvé par Muzychuk, Klin et Pöschel en 2001 et par Dobson et Morris 2002Modèle:,.

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 polynomialModèle:,.

Bibliographie complémentaire

• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.

Lien externe

• Modèle:MathWorld.