K-tree

Quality 0.50 · 3 views · Updated 2 months ago

title: "K-tree" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-minor-theory", "trees-(graph-theory)", "perfect-graphs", "graph-families"] topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/K-tree" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::figure[src="https://upload.wikimedia.org/wikipedia/commons/9/96/Goldner-Harary_graph.svg" caption="The [[Goldner–Harary graph]], 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, and include also the maximal outerplanar graphs. Planar 3-trees are also known as Apollonian networks.

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.

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.

References

(1992). "The Steiner Tree Problem". Elsevier.
[http://www.cirm.univ-mrs.fr/videos/2008/exposes/325/Darrasse.pdf Distances in random Apollonian network structures] {{Webarchive. link. (2011-07-21 , talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06.)
(2008). "Building Bridges: between Mathematics and Computer Science". Springer-Verlag.
Kleinschmidt, Peter. (1 December 1976). "Eine graphentheoretische Kennzeichnung der Stapelpolytope". Archiv der Mathematik.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::