K-arbre
En théorie des graphes, un k- arbre est un type de graphe non orienté. Un graphe est un k-arbre s'il peut être obtenu de la manière suivante : on part du graphe complet à ( k + 1) sommets, puis on ajoute des sommets tels que, pour un sommet v ajouté, v a exactement k voisins dans le graphe au moment de l'ajout, et ces voisins forment une clique[1] - [2].
Caractérisations
Les k-arbres sont exactement les graphes de largeur arborescente donnée, maximaux au sens que l'on ne peut pas ajouter d'arêtes sans augmenter leur largeur arborescente[3]. Ce sont aussi exactement les graphes cordaux dont toutes les cliques maximales ont la même taille k + 1 et dont tous les séparateurs de cliques minimaux ont également tous la même taille k .
Classes de graphes associées
Les 1-arbres sont les arbres non enracinés. Les 2-arbres sont exactement les graphes série-parallèles maximaux. Les graphes planaires externes maximaux sont des 2-arbres. Les 3-arbres planaires sont également connus sous le nom de réseaux apolliniens[4]. Les graphes qui ont une largeur arborescente au plus k sont exactement les sous-graphes des k-arbres, et pour cette raison ils sont appelés k-arbres partiels (en)[2].
Les graphes formés par les arêtes et les sommets de polytopes empilés de dimension k (qui sont des polytopes formés en partant d'un simplexe puis en collant à plusieurs reprises des simplexes sur les faces du polytope) sont des k-arbres lorsque k ≥ 3[5]. Ce processus de collage imite la construction de k-arbres en ajoutant des sommets à une clique[6]. Un k-arbre est le graphe d'un polytope empilé si et seulement s'il n'existe pas trois cliques de k + 1) sommets qui ont k sommets en commun[7].
Notes et références
- (en) H. P. Patil, « On the structure of k-trees », Journal of Combinatorics, Information and System Sciences, vol. 11, nos 2-4,‎ , p. 57–64 (MR 966069).
- (en) Jaroslav Nešetřil et Patrice Ossona de Mendez, « Structural Properties of Sparse Graphs », dans Martin Grötschel et Gyula O. H. Katona (éditeurs), Building Bridges: between Mathematics and Computer Science, Springer-Verlag, coll. « Bolyai Society Mathematical Studies » (no 19), (ISBN 978-3-540-85218-6, lire en ligne), p. 390.
- (en) Frank Hwang, Dana Richards et Pawel Winter, « Polynomially Solvable Cases », dans The Steiner Tree Problem, vol. 53, Elsevier, coll. « Annals of Discrete Mathematics (North-Holland Mathematics Studies) », (ISBN 978-0-444-89098-6), p. 177.
- (en) Olivier Bodini, Alexis Darrasse et Michèle Soria, « Distances in random Apollonian network structures », 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC2008), Viña del Mar, Chile,‎ , p. 307-318 (HAL hal-00345749, lire en ligne, consulté le ).
- (en) Etan Koch et Micha A. Perles, « Covering efficiency of trees and k-trees », dans Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., coll. « Congressus Numerantium » (no XVII), (MR 0457265), p. 391–420. Congressus Numerantium, No. XVII.
- (en) Alexander Below, Jesús A. De Loera et Jürgen Richter-Gebert, « The complexity of finding small triangulations of convex 3-polytopes », Journal of Algorithms, vol. 50, no 2,‎ , p. 134–167 (DOI 10.1016/S0196-6774(03)00092-0).
- (de) Peter Kleinschmidt, « Eine graphentheoretische Kennzeichnung der Stapelpolytope », Archiv der Mathematik, vol. 27, no 1,‎ , p. 663–667 (DOI 10.1007/BF01224736).
Bibliographie additionnelle
- (en) Marta Borowiecka-Olszewska, Ewa Drgas-Burchardt et Mariusz Hałuszczak, « On the structure and deficiency of k-trees with bounded degree », Discrete Applied Mathematics, vol. 201,‎ , p. 24–37 (ISSN 0166-218X, DOI 10.1016/j.dam.2015.08.008)
- (en) Marta Borowiecka et H. P. Patil, « Colourings of (k−r,k)-trees », Opuscula Math., vol. 37, no 4,‎ , p. 491-500 (MR 3647795).