Graphe scindé

Un graphe scindé, partitionné en une clique et un ensemble stable.

En théorie des graphes, un graphe scindé[1] ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977[2], et introduit indépendamment par Tyshkevich et Tchernyak en 1979[3], [4],[5].

Exemples élémentaires

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 { a , b } {\displaystyle \{a,b\}} et l'ensemble stable { c } {\displaystyle \{c\}}  ;
  2. la clique { b , c } {\displaystyle \{b,c\}} et l'ensemble stable { a } {\displaystyle \{a\}}  ;
  3. la clique { b } {\displaystyle \{b\}} et l'ensemble stable { a , c } {\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].

Relation avec d'autres familles de graphes

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.

Problèmes algorithmiques

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 x {\displaystyle x} dans I {\displaystyle I} tel que C ∪ { x } {\displaystyle C\cup \{x\}} est complet. Dans ce cas, C ∪ { x } {\displaystyle C\cup \{x\}} est une clique maximale et I {\displaystyle I} est un ensemble stable maximal.
  2. Il existe un sommet x {\displaystyle x} dans C {\displaystyle C} tel que I ∪ { x } {\displaystyle I\cup \{x\}} est stable. Dans ce cas, I ∪ { x } {\displaystyle I\cup \{x\}} est un ensemble stable maximum et C {\displaystyle C} est une clique maximum.
  3. C {\displaystyle C} est une clique maximale et I {\displaystyle I} est un ensemble stable maximal. Dans ce cas, G a une partition unique ( C , I ) {\displaystyle (C,I)} en une clique et un ensemble stable, C {\displaystyle C} est la clique maximale et I {\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].

Suites de degrés

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

∑ i = 1 m d i = m ( m − 1 ) + ∑ i = m + 1 n d i . {\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.

Nombre 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].

Notes et références

  1. ↑ Le terme « scindé » est utilisé dans plusieurs textes, par exemple la thèse Tom Bouvier, Graphes et décomposition, Université de Bordeaix, (HAL tel-01110277),   Chapitre 3. Graphes d’incidence et graphes scindés, p. 18.
  2. ↑ Földes et Hammer 1977a ; Földes et Hammer 1977b.
  3. ↑ Tyshkevich et Chernyak 1979.
  4. ↑ Földes et Hammer 1977a donent une définition plus générale, dans laquelle les graphes scindés comprennent aussi les graphes bipartis (c'est-à-dire les graphes qui peuvent être partitionnés en deux ensembles stables) et les compléments de graphes bipartis, (c'est-à-dire les graphes qui peuvent être partitionnés en deux cliques). Földes et Hammer 1977b utilisent la définition donnée ici, qui est aussi utilisée dans la littérature ultérieure, par exemple dans Brandstädt, Le et Spinrad 1999, Definition 3.2.3, p. 41.
  5. ↑ La terminologie « graphe séparé » se trouve par exemple dans les notes sur les graphes parfaits de Florian Hatat.
  6. ↑ Földes et Hammer 1977a
  7. ↑ Golumbic 1980, Theorem 6.3, p. 151.
  8. ↑ McMorris et Shier 1983; Voss 1985; Brandstädt, Le et Spinrad 1999, Theorem 4.4.2, p. 52.
  9. ↑ Bender, Richmond et Wormald 1985.
  10. ↑ Földes et Hammer 1977b ; Golumbic 1980, Theorem 9.7, page 212.
  11. ↑ Brandstädt, Le et Spinrad 1999, Corollary 7.1.1, p. 106, et Theorem 7.1.2, p. 107.
  12. ↑ Kézdy, Snevily et Wang (1996).
  13. ↑ Hammer et Simeone 1981; Golumbic 1980, Theorem 6.2, p. 150.
  14. ↑ Müller 1996.
  15. ↑ Bertossi 1984.
  16. ↑ Hammer et Simeone 1981
  17. ↑ Tyshkevich 1980
  18. ↑ Tyshkevich, Melnikow et Kotov 1981
  19. ↑ Golumbic 1980, Theorem 6.7 et Corollary 6.8, p. 154
  20. ↑ Brandstädt, Le et Spinrad 1999, Theorem 13.3.2, p. 203.
  21. ↑ Royle 2000
  22. ↑ Tyshkevich et Chernyak 1990

Bibliographie

  • E. A. Bender, L. B. Richmond et N. C. Wormald, « Almost all chordal graphs split », J. Austral. Math. Soc., vol. 38, no 2,‎ , p. 214–221 (DOI 10.1017/S1446788700023077 Accès libre, MR 0770128).
  • Alan A. Bertossi, « Dominating sets for split and bipartite graphs », Information Processing Letters, vol. 19,‎ , 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, (ISBN 0-89871-432-X, lire en ligne Inscription nécessaire).
  • Maria Chudnovsky, Neil Robertson, Paul Seymour et Robin Thomas, « The strong perfect graph theorem », Annals of Mathematics, vol. 164, no 1,‎ , 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,‎ , 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, no 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, (ISBN 0-12-289260-7, MR 0562306).
  • Peter Ladislaw Hammer et Bruno Simeone, « The splittance of a graph », Combinatorica, vol. 1, no 3,‎ , 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, no 2,‎ , p. 353–359 (DOI 10.1016/S0097-3165(96)80012-4 Accès libre, MR 1370138).
  • C. N. Lintzmayer, G. O. Mota et M. Sambinelli, « Decomposing split graphs into locally irregular graphs », Discrete Applied Mathematics, vol. 292,‎ , 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,‎ (arXiv 2105.12003).
  • F. R. McMorris et D. R. Shier, « Representing chordal graphs on K1,n », Commentationes Mathematicae Universitatis Carolinae, vol. 24,‎ , p. 489–494 (MR 0730144).
  • Russell Merris, « Split graphs », European Journal of Combinatorics, vol. 24, no 4,‎ , p. 413–430 (DOI 10.1016/S0195-6698(03)00030-1 Accès libre, MR 1975945).
  • Haiko Müller, « Hamiltonian Circuits in Chordal Bipartite Graphs », Discrete Mathematics, vol. 156,‎ , p. 291–298 (DOI 10.1016/0012-365x(95)00057-4 Accès libre).
  • Gordon F. Royle, « Counting set covers and split graphs », Journal of Integer Sequences, vol. 3, no 2,‎ , 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,‎ , 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,‎ , p. 14–26 (MR 0554162).
  • (ru) Regina I. Tyshkevich et A. A. Chernyak, « Еще один метод перечисления непомеченных комбинаторных объектов », Mat. Zametki, vol. 48, no 6,‎ , 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, no 6,‎ , 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,‎ , p. 5–8 (MR 0689420).
  • H.-J. Voss, « Note on a paper of McMorris and Shier », Commentationes Mathematicae Universitatis Carolinae, vol. 26,‎ , p. 319–322 (MR 0803929).

Liens externes

  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique