Graphe à seuil

vignette| Un 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 : Ajout d'un sommet isolé au graphe. 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. Une définition équivalente est la suivante : un graphe est un graphe à seuil s'il existe un nombre réel et pour chaque sommet un poids (nombre réel) tel que pour deux sommets , la paire est une arête si et seulement si . Une autre définition équivalente est la suivante: un graphe est un graphe à seuil s'il y a un nombre réel et, pour chaque sommet , un poids réel tel que pour tout ensemble de sommets , l'ensemble est indépendant si et seulement si . Le nom de « graphe à seuil » vient de ces définitions : S est le « seuil » pour la propriété d'être une arête, ou de manière équivalente T est le seuil pour être un ensemble indépendant. Les graphes à seuil ont également une caractérisation par sous-graphe exclu : un graphe est un graphe à seuil si et seulement si aucun ensemble de quatre de ses sommets ne forme un sous-graphe induit qui est un graphe chemin à trois arêtes , un graphe cycle quatre arêtes ou un graphe couplage à deux arêtes .