Graphe circulant

Graphe circulant
Le graphe de Paley d'ordre 13, un exemple de graphe circulant.
Distribution des degrés	Régulier
Automorphismes	Un des automorphismes est une permutation circulaire des sommets
Propriétés	Régulier Hamiltonien Sommet-transitif
modifier

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^[1] 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^[2],[3] ; 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^[4].

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 à 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 ${\displaystyle \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^[1]

Un exemple concret

On note ${\displaystyle C_{n}({s_{1},\ldots ,s_{k}})}$ le graphe avec ${\displaystyle n}$ nœuds étiquetés ${\displaystyle 0,1,\ldots ,n-1}$ et « sauts » ${\displaystyle s_{1},\ldots ,s_{k}}$ où chaque nœud i est adjacent aux 2 k nœuds ${\displaystyle i\pm s_{1},\ldots ,i\pm s_{k}\mod n}$^[5]. Par exemple, le graphe ${\displaystyle C_{n}({1,2,\ldots ,n/2})}$ est le graphe complet, et le graphe ${\displaystyle C_{n}({1})}$ est le graphe cycle.

• Le graphe ${\displaystyle C_{n}({s_{1},\ldots ,s_{k}})}$ est connexe si et seulement si ${\displaystyle \gcd(n,s_{1},\ldots ,s_{k})=1}$.
• Pour des entiers ${\displaystyle 1\leq s_{1}<\cdots <s_{k}}$ fixés, le nombre ${\displaystyle T(C_{n}({s_{1},\ldots ,s_{k}}))}$ d'arbres couvrant vérifie ${\displaystyle T(C_{n}({s_{1},\ldots ,s_{k}}))=na_{n}^{2}}$, où ${\displaystyle a_{n}}$ satisfait est une suite définie par récurrence d'ordre ${\displaystyle 2^{s_{k}-1}}$.
• En particulier, ${\displaystyle t(C_{n}({1,2}))=nF_{n}^{2}}$ où ${\displaystyle 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^[6]. 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^[7],[8].

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^[9],[10].

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Circulant graph » (voir la liste des auteurs).

1. Stanisław P. Radziszowski, « Small Ramsey Numbers », Electronic Journal of Combinatorics,‎ 2021, dynamic survey #16.
2. V. Vilfred, « On circulant graphs », dans R. Balakrishnan, G. Sethuraman et Robin J. Wilson (éditeurs), Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, 2004 (lire en ligne), p. 34–36.
3. (en) Eric W. Weisstein, « Circulant Graph », sur MathWorld.
4. Brian Alspach, « Isomorphism and Cayley graphs on abelian groups », dans Graph symmetry (Montreal, PQ, 1996), Dordrecht, Kluwer Acad. Publ., coll. « NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. » (n^o 497), 1997 (MR 1468786, lire en ligne), p. 1–22.
5. On trouve aussi les notations ${\displaystyle C_{n}^{s_{1},\ldots ,s_{k}}}$ ou ${\displaystyle C_{s_{1},\ldots ,s_{k}}^{n}}$.
6. Horst Sachs, « Über selbstkomplementäre Graphen », Publicationes Mathematicae Debrecen, vol. 9,‎ 1962, p. 270–288 (MR 0151953).
7. Mikhail Muzychuk, Mikhail Klin et Reinhard Pöschel, « The isomorphism problem for circulant graphs via Schur ring theory », dans Codes and association schemes (Piscataway, NJ, 1999), Providence, Rhode Island, American Mathematical Society, coll. « DIMACS Ser. Discrete Math. Theoret. Comput. Sci. » (n^o 56), 2001 (MR 1816402), p. 241–264
8. Edward Dobson et Joy Morris, « Toida's conjecture is true », Electronic Journal of Combinatorics, vol. 9, n^o 1,‎ 2002, R35:1–R35:14 (MR 1928787, lire en ligne).
9. Mikhail Muzychuk, « A Solution of the Isomorphism Problem for Circulant Graphs », Proc. London Math. Soc., vol. 88,‎ 2004, p. 1–41 (DOI 10.1112/s0024611503014412, MR 2018956)
10. Sergei Evdokimov et Ilia Ponomarenko, « Recognition and verification of an isomorphism of circulant graphs in polynomial time », St. Petersburg Math. J., vol. 15,‎ 2004, p. 813–835 (DOI 10.1090/s1061-0022-04-00833-7, MR 2044629).

Bibliographie complémentaire

• Valery A. Liskovets, « Some identities for enumerators of circulant graphs », Journal of Algebraic Combinatorics, vol. 18,‎ 2003, p. 189–209 (arXiv math/0104131, lire en ligne, consulté le 11 mai 2021).
• Arnaud Pêcher, Des multiples facettes des graphes circulants, Université Sciences et Technologies - Bordeaux I, 2008 (HAL tel-00332976, lire en ligne).
• Brian Alspach, Joy Morris et V. Vilfred, « Self-complementary circulant graphs », Ars Combinatoria, vol. 53,‎ 1999, p. 187–191.
• V. Vilfred, « A theory of Cartesian product and factorization of circulant graphs », J. Discrete Math.,‎ 2013, article n^o 163740 (10 pages) (zbMATH 1295.05202).

Lien externe

• (en) Eric W. Weisstein, « Circulant Graph », sur MathWorld.