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^[1] . Un chapitre sur les graphes à seuil apparaît dans le livre de Golumbic de 1980^[2], et le livre de Mahadev et Peled de 1995^[3] leur est consacré.

Comme le notent Diaconis, Holmes et Janson^[4], 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 ${\displaystyle P_{4})}$, des cycles à 4 sommets (notés ${\displaystyle C_{4}}$) et leurs compléments qui sont des paires d'arêtes (notés ${\displaystyle 2K_{2}}$). 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 ${\displaystyle S}$ et pour chaque sommet ${\displaystyle v}$ un poids (nombre réel) ${\displaystyle p(v)}$ tel que pour deux sommets ${\displaystyle u,v}$, la paire ${\displaystyle uv}$ est une arête si et seulement si ${\displaystyle 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 ${\displaystyle T}$ et, pour chaque sommet ${\displaystyle v}$, un poids réel ${\displaystyle a(v)}$ tel que pour tout ensemble de sommets ${\displaystyle X\subseteq V}$, l'ensemble ${\displaystyle X}$ est indépendant si et seulement si ${\displaystyle \sum _{v\in X}a(v)\leq 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 ${\displaystyle P_{4})}$, un graphe cycle quatre arêtes ${\displaystyle C_{4}}$ ou un graphe couplage à deux arêtes ${\displaystyle 2K_{2}}$.

À 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 ${\displaystyle \epsilon }$ et représente le premier sommet du graphe. Chaque caractère suivant est soit le symbole ${\displaystyle u}$, qui dénote l'ajout d'un sommet isolé (ou sommet d'union ), ou ${\displaystyle j}$, qui dénote l'ajout d'un sommet dominant (ou sommet de jointure). Par exemple, la chaîne ${\displaystyle \epsilon uuj}$ représente un graphe en étoile à trois feuilles, tandis que ${\displaystyle \epsilon uj}$ représente un chemin sur trois sommets. Le graphe de la figure peut être représenté comme ${\displaystyle \epsilon uuujuuj}$

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 (${\displaystyle P_{4}}$), et un graphe à seuil est un graphe induit sans ${\displaystyle P_{4}}$, ${\displaystyle C_{4}}$ ni ${\displaystyle 2K_{2}}$ . ${\displaystyle C_{4}}$ est un cycle de quatre sommets et ${\displaystyle 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 ${\displaystyle P_{4}}$ est auto-complémentaire, donc si un graphe est sans ${\displaystyle P_{4}}$, ${\displaystyle C_{4}}$ ni ${\displaystyle 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 Janson^[4], et aussi par Lou, Wang et Huang^[5],[5] ou Tura^[6]. Ainsi, toutes les valeurs propres de la matrice des distances d'un graphe à seuil connexe, autres que -2 et -1, sont simples.

Heggernes & Kratsch^[7] ont montré en 2007 que les graphes à seul peuvent être reconnus en tems liénaire ; si un graphe n'est pas à seuil, l'algorithme détecte une obstruction, c'est-à-dire l'un des graphes ${\displaystyle P_{4}}$, ${\displaystyle C_{4}}$ ou ${\displaystyle 2K_{2}}$.

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

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Threshold graph » (voir la liste des auteurs).

• Milica Anđelić et Slobodan K. Simić, « Some notes on the threshold graphs », Discrete Mathematics, vol. 310, n^os 17-18,‎ 2010, p. 2241–2248 (DOI 10.1016/j.disc.2010.04.022)
• Václav Chvátal et Peter L. Hammer, « Aggregation of inequalities in integer programming », dans P. L. Hammer, E. L. Johnson, B. H. Korte, G. L. Nemhauser (éditeurs), Studies in Integer Programming (Proc. Worksh. Bonn 1975), vol. 1, Amsterdam, North-Holland, coll. « Annals of Discrete Mathematics », 1977, p. 145–162.
• Persi Diaconis, Susan Holmes et Svante Janson, « Threshold graph limits and random threshold graphs », Internet Mathematics, Taylor & Francis Online, vol. 5, n^o 3,‎ 2008, p. 267-320 (arXiv 0908.2448, lire en ligne, consulté le 15 juillet 2021).
• Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, New York, Academic Press, 1980. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.
• Pinar Heggernes et Dieter Kratsch, « Linear-time certifying recognition algorithms and forbidden induced subgraphs », Nordic Journal of Computing, vol. 14, n^os 1-2,‎ 2007, p. 87–108 (2008) (MR 2460558, lire en ligne).
• N. V. R. Mahadev et Uri N. Peled, Threshold Graphs and Related Topics, Elsevier, 1995.
• Pallabi Manna, Peter J. Cameron et Ranjit Mehatari, « Forbidden Subgraphs of Power Graphs », The Electronic Journal of Combinatorics, vol. 28, n^o 3,‎ 2021 (DOI 10.37236/9961, lire en ligne)
• Lu Lu, Qiongxiang Huang et Zhenzhen Lou, « On the distance spectra of threshold graphs », Linear Algebra and its Applications, vol. 553,‎ 2018, p. 223–237 (DOI 10.1016/j.laa.2018.05.014)
• Zhenzhen Lou, Jianfeng Wang et Qiongxiang Huang, « On the Eigenvalues Distribution in Threshold Graphs », Graphs and Combinatorics, vol. 35, n^o 4,‎ 2019, p. 867–880 (DOI 10.1007/s00373-019-02042-1)
• Fernando C. Tura, « A conjecture on the eigenvalues of threshold graphs », Linear Algebra and its Applications, vol. 612,‎ 2021, p. 345–356 (DOI 10.1016/j.laa.2020.11.007, arXiv 2006.03136)

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

• Portail des mathématiques
• Portail de l'informatique théorique