Graphe à seuil

En théorie des graphes, un graphe à seuil est un graphe qui peut être construit, en partant d'un graphe à un seul sommet, par application répétée d'une des deux opérations suivantes : 1. * Ajout d'un sommet isolé au graphe. 2. * Ajout d'un sommet dominant au graphe, c'est-à-dire d'un sommet connecté à tous les autres sommets. Par exemple, le graphe de la figure ci-contre est un graphe de seuil : il peut être construit en commençant par un graphe à un seul sommet (sommet 1), puis en ajoutant les sept autres dans l'ordre dans lequel ils sont numérotés, les sommets noirs comme sommets isolés et les sommets rouges comme sommets dominants. Les graphes à seuil ont été introduits par Chvátal et Hammer en 1977 . Un chapitre sur les graphes à seuil apparaît dans le livre de Golumbic de 1980, et le livre de Mahadev et Peled de 1995 leur est consacré. Comme le notent Diaconis, Holmes et Janson, parmi les 64 graphes étiquetés à 4 sommets, il y a 46 graphes à seuil ; les 18 autres sont des chaînes à 4 sommets (notés , des cycles à 4 sommets (notés ) et leurs compléments qui sont des paires d'arêtes (notés ). Si on considère les graphes non étiquetés, il y a 11 graphes à 4 sommets, dont 8 sont des graphes à seuil.