Graphe sommet-connexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, un graphe connexe « est dit k-sommet-connexe s'il possède au moins k + 1 sommets et s'il reste encore connexe après en avoir ôté k – 1[1]. »

Un graphe régulier de degré k est au plus k-sommet-connexe et k-arête-connexe. S'il est effectivement k-sommet-connexe et k-arête-connexe, il est dit optimalement connecté.

Exemples[modifier | modifier le code]

  • Pour tout n, le graphe complet Kn (régulier de degré n – 1) est optimalement connecté.
  • Pour tout k > 2 et tout j > 1, le graphe moulin (en) Wd(k, j) est 1-sommet-connexe. Pour le séparer en j composantes connexes, il suffit de supprimer son sommet de plus haut degré : son centre.
  • Le graphe cycle Cn est 2-sommet-connexe pour tout n > 3.
  • Le 110-graphe de Iofinova-Ivanov est 3-sommet-connexe

Référence[modifier | modifier le code]

  1. Jiří Matoušek et Jaroslav Nešetřil (en), Introduction aux mathématiques discrètes, Springer,‎ (lire en ligne), p. 144.

Article connexe[modifier | modifier le code]

Lexique de la théorie des graphes