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 autre qu'un graphe complet est de degré de sommet-connexité k s'il est k-sommet-connexe sans être k+1-sommet-connexe, donc si k est la taille du plus petit sous-ensemble de sommets dont la suppression déconnecte le graphe[2]. Les graphes complets ne sont pas inclus dans cette version de la définition car ils ne peuvent pas être déconnectés en supprimant des sommets. Le graphe complet à n sommets est de degré de connexité n-1.
Une définition équivalente est qu'un graphe avec au moins deux sommets est k-sommet-connexe, pour chaque paire de ses sommets, il existe est k chaînes indépendantes reliant ces sommets ; c'est le théorème de Menger[3]. Cette définition produit la même réponse n − 1, pour la connexité du graphe complet Kn[2].
Un graphe 1-sommet-connexe est appelé un graphe connexe ; un graphe 2-sommet-connexe est appelé un graphe biconnexe. Un graphe 3-connexe est aussi appelé triconnexe.
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é.
Nombre de graphes simples -sommet-connexes à sommets pour de 1 à 9, avec la référence à OEIS :
\ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | OEIS |
---|---|---|---|---|---|---|---|---|---|---|
total | 1 | 2 | 4 | 11 | 34 | 156 | 1044 | 12346 | 274668 | A000088 |
1 | 1 | 1 | 2 | 6 | 21 | 112 | 853 | 11117 | 261080 | A001349 |
2 | 0 | 1 | 1 | 3 | 10 | 56 | 468 | 7123 | 194066 | A002218 |
3 | 0 | 0 | 1 | 1 | 3 | 17 | 136 | 2388 | 80890 | A006290 |
4 | 0 | 0 | 0 | 1 | 1 | 4 | 25 | 384 | 14480 | A086216 |
5 | 0 | 0 | 0 | 0 | 1 | 1 | 4 | 39 | 1051 | A086217 |
6 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 5 | 59 | |
7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 5 |
Nombre de graphes simples exactement -sommet-connexes à sommets:
\ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | OEIS |
---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 5 | 13 | 44 | 191 | 1229 | 13588 | |
1 | 1 | 0 | 1 | 3 | 11 | 56 | 385 | 3994 | 67014 | A052442 |
2 | 0 | 1 | 0 | 2 | 7 | 39 | 332 | 4735 | 113176 | A052443 |
3 | 0 | 0 | 1 | 0 | 2 | 13 | 111 | 2004 | 66410 | A052444 |
4 | 0 | 0 | 0 | 1 | 0 | 3 | 21 | 345 | 13429 | A052445 |
5 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 34 | 992 | |
6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 4 | 54 |