Graphe régulier

En théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c'est-à-dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré $k>$ est appelé un graphe $k$-régulier ou graphe régulier de degré $k$

Cas particuliers

Un graphe 0-régulier est un ensemble de sommets déconnectés; un graphe 1-régulier a un nombre pair de sommets et est un ensemble d'arêtes déconnectées ou couplage; enfin, un graphe 2-régulier est un ensemble de cycles déconnectés. Un graphe 3-régulier est aussi appelé graphe cubique.

• 

  graphe 0-régulier

• 

  graphe 1-régulier

• 

  graphe 2-régulier

• 

  graphe de Petersen (graphe cubique particulier)

Un graphe fortement régulier est un graphe régulier où chaque paire de sommets adjacents a le même nombre $l$ de voisins en commun et où chaque paire de sommets non-adjacents a le même nombre $n$ de voisins en commun. Les plus petits graphes qui sont réguliers sans être fortement réguliers sont le graphe cycle et le graphe circulant, tous deux à 6 sommets. Le graphe complet $K_m$ est fortement régulier pour tout $m$

Propriétés

Un théorème de Crispin Nash-Williams affirme que tout graphe $k$ régulier ayant $2k+1$ sommets admet un cycle Hamiltonien.

Soit $A$ la matrice d'adjacence du graphe. Le graphe est régulier si et seulement si $\begin{bmatrix}1\\ \vdots \\1 \end{bmatrix}$ est un vecteur propre de $A$. Lorsque c'est un vecteur propre, il correspond à une valeur propre qui est égale au degré du graphe.

Génération

Des graphes réguliers peuvent être générés en utilisant le logiciel GenReg.

Voir aussi

• Graphe de Higman-Sims

Liens externes

• (en) Eric W. Weisstein, « Regular Graph », MathWorld
• (en) Eric W. Weisstein, « Strongly Regular Graph », MathWorld
• (en) Nash-Williams, Crispin (1969), "Valency Sequences which force graphs to have Hamiltonian Circuits", University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo