k-tree
File:Goldner-Harary graph.svg, an example of a planar 3-tree.]]
In graph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex v has exactly k neighbors U such that, together, the k + 1 vertices formed by v and U form a clique.
Characterizations
The k-trees are exactly the maximal graphs with a treewidth of k ("maximal" means that no more edges can be added without increasing their treewidth). They are also exactly the chordal graphs all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k.{{citation
| last = Patil | first = H. P.
| mr = 966069
| issue = 2–4
| journal = Journal of Combinatorics, Information and System Sciences
| pages = 57–64
| title = On the structure of k-trees
| volume = 11
| year = 1986}}.
Related graph classes
1-trees are the same as trees. 2-trees are maximal series–parallel graphs,{{citation|page=177|title=The Steiner Tree Problem|volume=53|series=Annals of Discrete Mathematics (North-Holland Mathematics Studies)|first1=Frank|author2-link=Dana S. Richards |last1=Hwang|first2=Dana|last2=Richards|first3=Pawel|last3=Winter|publisher=Elsevier|year=1992|isbn=978-0-444-89098-6}}. and include also the maximal outerplanar graphs. Planar 3-trees are also known as Apollonian networks.[http://www.cirm.univ-mrs.fr/videos/2008/exposes/325/Darrasse.pdf Distances in random Apollonian network structures] {{Webarchive|url=https://web.archive.org/web/20110721023259/http://www.cirm.univ-mrs.fr/videos/2008/exposes/325/Darrasse.pdf |date=2011-07-21 }}, talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06.
The graphs that have treewidth at most k are exactly the subgraphs of k-trees, and for this reason they are called partial k-trees.{{citation|page=390|contribution=Structural Properties of Sparse Graphs|first1=Jaroslav|last1=Nešetřil|author1-link=Jaroslav Nešetřil|first2=Patrice|last2=Ossona de Mendez|author2-link= Patrice Ossona de Mendez |title=Building Bridges: between Mathematics and Computer Science|volume=19|series=Bolyai Society Mathematical Studies|editor-first1=Martin|editor-last1=Grötschel|editor1-link=Martin Grötschel|editor-first2=Gyula O. H.|editor-last2=Katona|editor2-link=Gyula O. H. Katona|publisher=Springer-Verlag|year=2008|isbn=978-3-540-85218-6|contribution-url=http://kam.mff.cuni.cz/~kamserie/serie/clanky/2008/s863.pdf}}.
The graphs formed by the edges and vertices of k-dimensional stacked polytopes, polytopes formed by starting from a simplex and then repeatedly gluing simplices onto the faces of the polytope, are k-trees when k ≥ 3.{{citation
| last1 = Koch | first1 = Etan
| last2 = Perles | first2 = Micha A. | author2-link = Micha Perles
| contribution = Covering efficiency of trees and k-trees
| mr = 0457265
| pages = 391–420. Congressus Numerantium, No. XVII
| publisher = Utilitas Math., Winnipeg, Man.
| title = Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976)
| year = 1976}}. See in particular p. 420. This gluing process mimics the construction of k-trees by adding vertices to a clique.{{citation
| last1 = Below | first1 = Alexander
| last2 = De Loera | first2 = Jesús A. | author2-link = Jesús A. De Loera
| last3 = Richter-Gebert | first3 = Jürgen
| arxiv = math/0012177
| date = February 2004
| doi = 10.1016/s0196-6774(03)00092-0
| issue = 2
| journal = Journal of Algorithms
| pages = 134–167
| title = The complexity of finding small triangulations of convex 3-polytopes
| volume = 50}} A k-tree is the graph of a stacked polytope if and only if no three (k + 1)-vertex cliques have k vertices in common.{{citation|last=Kleinschmidt|first=Peter|title=Eine graphentheoretische Kennzeichnung der Stapelpolytope|journal=Archiv der Mathematik|date=1 December 1976|volume=27|issue=1|pages=663–667|doi=10.1007/BF01224736}}