Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
K-tree
Summary
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.
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.
1-trees are the same as unrooted 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. This gluing process mimics the construction of k-trees by adding vertices to a clique. 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (4)