K-arbre

vignette|Le graphe de Goldner–Harary est un exemple d'un 3-arbre planaire. 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. 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. 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 . 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. 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 . 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. Ce processus de collage imite la construction de k-arbres en ajoutant des sommets à une clique. 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.