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.[1][2]
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).[2] 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.[1]
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.[2]
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.[5] This gluing process mimics the construction of k-trees by adding vertices to a clique.[6] 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.[7]
References
^ abPatil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences, 11 (2–4): 57–64, MR0966069.
^Koch, Etan; Perles, Micha A. (1976), "Covering efficiency of trees and k-trees", Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., pp. 391–420. Congressus Numerantium, No. XVII, MR0457265. See in particular p. 420.
^Kleinschmidt, Peter (1 December 1976), "Eine graphentheoretische Kennzeichnung der Stapelpolytope", Archiv der Mathematik, 27 (1): 663–667, doi:10.1007/BF01224736
