Graphe scindé

Un graphe scindé peut avoir plus d'une partition en une clique et un ensemble stable ; par exemple, le chemin a – b – c est un graphe scindé, dont les sommets peuvent être partitionnés de trois manières différentes :

1. la clique ${\displaystyle \{a,b\}}$ et l'ensemble stable ${\displaystyle \{c\}}$ ;
2. la clique ${\displaystyle \{b,c\}}$ et l'ensemble stable ${\displaystyle \{a\}}$ ;
3. la clique ${\displaystyle \{b\}}$ et l'ensemble stable ${\displaystyle \{a,c\}}$.

Les graphes scindés peuvent être caractérisés par leurs sous-graphes induits interdits : un graphe est scindé si et seulement si aucun sous-graphe induit n'est un cycle sur quatre ou cinq sommets, ou n'est une paire d'arêtes disjointes (le complément d'un 4-cycle[6] - [7].

De par leur définition, les graphes scindé sont clairement fermés par complémentation . Une autre caractérisation des graphes scindés fait intervenir la complémentation : ce sont des graphes cordaux dont les compléments sont également cordaux. Tout comme les graphes cordaux sont les graphes d'intersection de sous-arbres d'arbres, les graphes scindés sont les graphes d'intersection de sous-étoiles distinctes de graphes en étoile[8]. Presque tous les graphes cordaux sont des graphes scindés, au sens où la fraction des graphes cordaux scindés parmi les graphes cordaux à n sommets qui sont scindé tend vers 1 lorsque n tend vers l'infini[9].

Comme les graphes cordaux sont parfaits, les graphes scindés le sont aussi. Les graphes à double scission, une famille de graphes dérivés de graphes scindés en doublant chaque sommet (la clique induit alors un anti-couplage et l'ensemble stable induit un couplage), figure, dans la preuve de Chudnovsky et al. 2006 du théorème des graphes parfaits fort, comme l'une des cinq classes de base de graphes parfaits à partir desquels tous les autres peuvent être formés.

Si un graphe est à la fois un graphe scindé et un graphe d'intervalle, alors son complément est à la fois un graphe scindé et un graphe de comparabilité, et vice versa. Les graphes de comparabilité scindés, et donc aussi les graphes d'intervalles scindés, peuvent être caractérisés en termes d'un ensemble de trois sous-graphes induits interdits[10]. Les cographes scindés sont exactement les graphes à seuil. Les graphes de permutation scindés sont exactement les graphes d'intervalle dont les compléments sont des graphes d'intervalle[11] ; ce sont les graphes de permutation pour des permutations symétriques gauches[12]. Les graphes scindés ont un nombre cochromatique égal à 2.

Soit G un graphe scindé, partitionné en une clique C et un ensemble stable I . Alors chaque clique maximale dans le graphe scindé est soit C lui-même, soit le voisinage d'un sommet dans I . Ainsi, il est facile d'identifier la clique maximale et, de manière complémentaire, l'ensemble stable maximal dans un graphe scindé. Dans tout graphe scindé, l'une des trois conditions suivantes est réalisée[13] :

1. Il existe un sommet ${\displaystyle x}$ dans ${\displaystyle I}$ tel que ${\displaystyle C\cup \{x\}}$ est complet. Dans ce cas, ${\displaystyle C\cup \{x\}}$ est une clique maximale et ${\displaystyle I}$ est un ensemble stable maximal.
2. Il existe un sommet ${\displaystyle x}$ dans ${\displaystyle C}$ tel que ${\displaystyle I\cup \{x\}}$ est stable. Dans ce cas, ${\displaystyle I\cup \{x\}}$ est un ensemble stable maximum et ${\displaystyle C}$ est une clique maximum.
3. ${\displaystyle C}$ est une clique maximale et ${\displaystyle I}$ est un ensemble stable maximal. Dans ce cas, G a une partition unique ${\displaystyle (C,I)}$ en une clique et un ensemble stable, ${\displaystyle C}$ est la clique maximale et ${\displaystyle I}$ est l'ensemble stable maximal.

Certains problèmes d'optimisation qui sont NP-complets sur des familles de graphes plus générales, y compris la coloration de graphes, deviennent simples sur des graphes scindés. Trouver une chaîne hamiltonienne reste NP-complet même pour les graphes scindés qui sont des graphes cordaux forts[14]. Il est également connu que le problème de l'ensemble dominant minimum reste NP-complet pour les graphes scindés[15].

Une propriété remarquable des graphes scindés est qu'ils peuvent être reconnus uniquement à partir de leurs suite de degrés . Soit ${\displaystyle d_{1}\geq d_{2}\geq \cdots \geq d_{n}}$d ₁ ≥ d ₂ ≥ ... ≥ d _n la suite de degrés d'un graphe G et soit ${\displaystyle m}$ le plus grand indice ${\displaystyle i}$ tel que ${\displaystyle d_{i}\geq i-1}$. Alors G est un graphe scindé si et seulement si

${\displaystyle \sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.}$

Dans cas les m sommets avec les degrés les plus grands forment une clique maximale dans G, et les sommets restants constituent un ensemble stable[16] - [17] - [18] - [19] - [20]. (Merris 2003) étudie plus à fond les suites de degrés de graphes scindés.

Gordon F. Royle a démontré[21] que les graphes scindé à n sommets sont en bijection avec certaines familles de Sperner. À l'aide de cette observation, il a établi une formule pour le nombre de graphes scindés non isomorphes à n sommets. Les premières valeurs de cette suite, à partir de n = 1, sont

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... suite A048194 de l'OEIS .

Ce résultat d'énumération a également été prouvé, en 1990, par Tyshkevich et Chernyak[22].

• E. A. Bender, L. B. Richmond et N. C. Wormald, « Almost all chordal graphs split », J. Austral. Math. Soc., vol. 38, n^o 2,‎ 1985, p. 214–221 (DOI 10.1017/S1446788700023077 , MR 0770128).
• Alan A. Bertossi, « Dominating sets for split and bipartite graphs », Information Processing Letters, vol. 19,‎ 1984, p. 37–40 (DOI 10.1016/0020-0190(84)90126-1).
• Andreas Brandstädt, Van Bang Le et Jeremy Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999 (ISBN 0-89871-432-X, lire en ligne ).
• Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas, « The strong perfect graph theorem », Annals of Mathematics, vol. 164, n^o 1,‎ 2006, p. 51–229 (DOI 10.4007/annals.2006.164.51, MR 2233847, arXiv math/0212070).
• Mark Dukes, « The sandpile model on the complete split graph, Motzkin words, and tiered parking functions », Journal of Combinatorial Theory, Series A, vol. 180,‎ 2021, p. 105418 (DOI 10.1016/j.jcta.2021.105418).
• Stéphane Földes et Peter Ladislaw Hammer, « Split graphs », Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Winnipeg, Utilitas Math.,‎ 1977a, p. 311–315 (MR 0505860).
• Stéphane Földes et Peter Ladislaw Hammer, « Split graphs having Dilworth number two », Canadian Journal of Mathematics, vol. 29, n^o 3,‎ 1977b, p. 666–672 (DOI 10.4153/CJM-1977-069-1, MR 0463041).
• Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980 (ISBN 0-12-289260-7, MR 0562306).
• Peter Ladislaw Hammer et Bruno Simeone, « The splittance of a graph », Combinatorica, vol. 1, n^o 3,‎ 1981, p. 275–284 (DOI 10.1007/BF02579333, MR 0637832).
• André E. Kézdy, Hunter S. Snevily et Chi Wang, « Partitioning permutations into increasing and decreasing subsequences », Journal of Combinatorial Theory, Series A, vol. 73, n^o 2,‎ 1996, p. 353–359 (DOI 10.1016/S0097-3165(96)80012-4 , MR 1370138).
• C. N. Lintzmayer, G. O. Mota et M. Sambinelli, « Decomposing split graphs into locally irregular graphs », Discrete Applied Mathematics, vol. 292,‎ 2021, p. 33–44 (DOI 10.1016/j.dam.2020.12.002).
• Nicolas Maack, Hendrik Molter, Rolf Niedermeier et Malte Renken, « On Finding Separators in Temporal Split and Permutation Graphs », arxiv,‎ 2021 (arXiv 2105.12003).
• F. R. McMorris et D. R. Shier, « Representing chordal graphs on K_1,n », Commentationes Mathematicae Universitatis Carolinae, vol. 24,‎ 1983, p. 489–494 (MR 0730144).
• Russell Merris, « Split graphs », European Journal of Combinatorics, vol. 24, n^o 4,‎ 2003, p. 413–430 (DOI 10.1016/S0195-6698(03)00030-1 , MR 1975945).
• Haiko Müller, « Hamiltonian Circuits in Chordal Bipartite Graphs », Discrete Mathematics, vol. 156,‎ 1996, p. 291–298 (DOI 10.1016/0012-365x(95)00057-4 ).
• Gordon F. Royle, « Counting set covers and split graphs », Journal of Integer Sequences, vol. 3, n^o 2,‎ 2000, p. 00.2.6 (MR 1778996, lire en ligne).
• (ru) Regina I. Tyshkevich, « The canonical decomposition of a graph », Doklady Akademii Nauk SSSR, vol. 24,‎ 1980, p. 677–679 (MR 0587712)
• (ru) Regina I. Tyshkevich et A. A. Chernyak, « Canonical partition of a graph defined by the degrees of its vertices », Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk, vol. 5,‎ 1979, p. 14–26 (MR 0554162).
• (ru) Regina I. Tyshkevich et A. A. Chernyak, « Еще один метод перечисления непомеченных комбинаторных объектов », Mat. Zametki, vol. 48, n^o 6,‎ 1990, p. 98–105 (MR 1102626, lire en ligne). — Traduction : « Yet another method of enumerating unmarked combinatorial objects », Mathematical Notes of the Academy of Sciences of the USSR, vol. 48, n^o 6,‎ 1990, p. 1239–1245 (ISSN 0001-4346, DOI 10.1007/BF01240267).
• (ru) Regina I. Tyshkevich, O. I. Melnikow et V. M. Kotov, « On graphs and degree sequences: the canonical decomposition », Kibernetika, vol. 6,‎ 1981, p. 5–8 (MR 0689420).
• H.-J. Voss, « Note on a paper of McMorris and Shier », Commentationes Mathematicae Universitatis Carolinae, vol. 26,‎ 1985, p. 319–322 (MR 0803929).

• (en) Eric W. Weisstein, « Split Graph », sur MathWorld