Graphe d'Andrásfai

Deux tracés du graphe And (4)

En théorie des graphes, un graphe d'Andrásfai est un graphe circulant sans triangle ; il porte le nom de Béla Andrásfai .

Définition

Pour tout entier naturel $n\ge 1$, le graphe d'Andrásfai d'ordre Modèle:Mvar , noté And(Modèle:Mvar) est un graphe circulant sur $3n-1$ sommets, dans lequel tout sommet $k$ est reliée par une arête aux sommets $k\pm j,$ pour tout entier $j$ congru à 1 mod 3. Par exemple, le graphe de Wagner est un graphe d'Andrásfai : c'est le graphe And (3).

Exemples

Propriétés

Les graphes d'Andrásfai sont sans triangle, et le graphe And(Modèle:Mvar) a un nombre d'indépendance (taille maximale d'un ensemble stable) égal à $n$. Il en résulte la formule $R(3,n)\ge 3(n-1)$, où $R(n,k)$ est le nombre de Ramsey. L'égalité vaut seulement pour $n=3,n=4$.

Les graphes d'Andrásfai ont la propriété que tout ensemble stable (i. e. de sommets non connectés) maximal est formé des voisins d'un sommet commun. Par exemple, dans le graphe And(3), les trois voisins d'un sommet, à savoir ses voisins sur le cercle et celui qui lui est opposé, forment un ensemble stable maximal.

Bibliographie

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

Articles connexes

• Graphe de Petersen
• Graphe de Cayley

Lien externe

• Modèle:MathWorld