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é est appelé un graphe -régulier ou graphe régulier de degré . 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. Image:0-regulární graf na 6 vrcholech.png|graphe 0-régulier Image:1-regulární graf na 6 vrcholech.svg|graphe 1-régulier Image:2-regulární graf na 6 vrcholech.svg|graphe 2-régulier Image:Petersen_graph_blue.svg |[[graphe de Petersen]] (graphe cubique particulier) Image:Infinite-2-regular-graph.png|graphe infini 2-régulier Un graphe fortement régulier est un graphe régulier où chaque paire de sommets adjacents a le même nombre de voisins en commun et où chaque paire de sommets non-adjacents a le même nombre 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 est fortement régulier pour tout Une condition nécessaire et suffisante pour l'existence d'un graphe -régulier à sommets est que soit pair et que . Un théorème de Crispin Nash-Williams affirme que tout graphe -régulier ayant sommets admet un cycle hamiltonien. Soit la matrice d'adjacence du graphe. Le graphe est régulier si et seulement si est un vecteur propre de . Lorsque c'est un vecteur propre, il correspond à une valeur propre qui est égale au degré du graphe. De nombreux problèmes de graphes sont difficiles même si l'on se restreint à la classe des graphes réguliers. Plus précisément, la coloration, le problème du voyageur de commerce et le problème du stable maximum sont NP-difficiles pour les graphes réguliers et même pour les graphes k-réguliers avec k fixé.