Graphe à seuil

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 :

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 1977Modèle:Sfn . Un chapitre sur les graphes à seuil apparaît dans le livre de Golumbic de 1980Modèle:Sfn, et le livre de Mahadev et Peled de 1995Modèle:Sfn leur est consacré.

Comme le notent Diaconis, Holmes et JansonModèle:Sfn, 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 $P_4)$, des cycles à 4 sommets (notés $C_4$) et leurs compléments qui sont des paires d'arêtes (notés $2K_2$). Si on considère les graphes non étiquetés, il y a 11 graphes à 4 sommets, dont 8 sont des graphes à seuil.

Autres définitions

Une définition équivalente est la suivante : un graphe est un graphe à seuil s'il existe un nombre réel $S$ et pour chaque sommet $v$ un poids (nombre réel) $p(v)$ tel que pour deux sommets $u,v$, la paire $uv$ est une arête si et seulement si $p(u)+p(v)>S$ .

Une autre définition équivalente est la suivante: un graphe est un graphe à seuil s'il y a un nombre réel $T$ et, pour chaque sommet $v$, un poids réel $a(v)$ tel que pour tout ensemble de sommets $X\subseteq V$, l'ensemble $X$ est indépendant si et seulement si $\sum _{v\in X}a(v)\le T.$. 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 $P_4)$, un graphe cycle quatre arêtes $C_4$ ou un graphe couplage à deux arêtes $2K_2$.

Décomposition

À partir de la définition qui utilise l'addition répétée de sommets, on peut obtenir une autre manière de décrire de manière unique un graphe à seuil, au moyen d'une chaîne de symboles. Le premier caractère de cette chaîne est le symbole $ϵ$ et représente le premier sommet du graphe. Chaque caractère suivant est soit le symbole $u$, qui dénote l'ajout d'un sommet isolé (ou sommet d'union ), ou $j$, qui dénote l'ajout d'un sommet dominant (ou sommet de jointure). Par exemple, la chaîne $ϵuuj$ représente un graphe en étoile à trois feuilles, tandis que $ϵuj$ représente un chemin sur trois sommets. Le graphe de la figure peut être représenté comme $ϵuuujuuj$

Lien avec d'autres classes de graphes et reconnaissance

Les graphes à seuil sont un cas particulier de cographes, de graphes scindés et de graphes trivialement parfaits. Un graphe est un graphe seuil si et seulement s'il est à la fois un cographe et un graphe scindé. Tout graphe qui est à la fois un graphe trivialement parfait et le graphe complémentaire d'un graphe trivialement parfait est un graphe à seuil. Les graphes à seuil sont également un cas particulier de graphes d'intervalles . Toutes ces relations peuvent être déduits de leur caractérisation par les sous-graphes induits interdits : Un cographe est un graphe sans chemin induit sur quatre sommets ($P_4$), et un graphe à seuil est un graphe induit sans $P_4$, $C_4$ ni $2K_2$ . $C_4$ est un cycle de quatre sommets et $2K_2$est son complément, c'est-à-dire formé deux arêtes disjointes. Ceci explique aussi pourquoi les graphes à seuil sont fermés par passage au complément ; le $P_4$ est auto-complémentaire, donc si un graphe est sans $P_4$, $C_4$ ni $2K_2$, son complément l'est aussi.

Les graphes à seuil ont aussi des propriétés spectrales particulières, étudiées par Diaconis, Holmes et JansonModèle:Sfn, et aussi par Lou, Wang et HuangModèle:SfnModèle:,Modèle:Sfn ou TuraModèle:Sfn. Ainsi, toutes les valeurs propres de la matrice des distances d'un graphe à seuil connexe, autres que -2 et -1, sont simples.

Heggernes & KratschModèle:Sfn ont montré en 2007 que les graphes à seul peuvent être reconnus en temps liénaire ; si un graphe n'est pas à seuil, l'algorithme détecte une obstruction, c'est-à-dire l'un des graphes $P_4$, $C_4$ ou $2K_2$.

Voir également

• Graphe d'intervalles propre
• Graphe série-parallèle

Bibliographie

• Modèle:Article
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Ouvrage. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article

Liens externes

• « Threshold graphs », Information System on Graph Classes and their Inclusions.