K-tree
Encyclopedia
In graph theory
, a k-tree is a chordal graph
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.
The k-trees are exactly the maximal
graphs with a given treewidth, graphs to which no more edges can be added without increasing their treewidth. 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.
Every k-tree may be formed by starting with a (k + 1)-vertex complete graph
and then repeatedly adding vertices in such a way that each added vertex has exactly k neighbors that form a clique
.
Certain k-trees with k ≥ 3 are also the graphs formed by the edges and vertices of stacked polytopes, polytope
s formed by starting from a simplex
and then repeatedly gluing simplices onto the faces of the polytope; this gluing process mimics the construction of k-trees by adding vertices to a clique. Every stacked polytope forms a k-tree in this way, but not every k-tree comes from a stacked polytope: 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.
1-trees are the same as unrooted trees
. 2-trees are maximal series-parallel graph
s, and include also the maximal outerplanar graph
s. Planar
3-trees are also known as Apollonian network
s.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a k-tree is a chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
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.
The k-trees are exactly the maximal
Maximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
graphs with a given treewidth, graphs to which no more edges can be added without increasing their treewidth. 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.
Every k-tree may be formed by starting with a (k + 1)-vertex complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
and then repeatedly adding vertices in such a way that each added vertex has exactly k neighbors that form a clique
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
.
Certain k-trees with k ≥ 3 are also the graphs formed by the edges and vertices of stacked polytopes, polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
s formed by starting from a simplex
Simplex
In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron,...
and then repeatedly gluing simplices onto the faces of the polytope; this gluing process mimics the construction of k-trees by adding vertices to a clique. Every stacked polytope forms a k-tree in this way, but not every k-tree comes from a stacked polytope: 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.
1-trees are the same as unrooted trees
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
. 2-trees are maximal series-parallel graph
Series-parallel graph
In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.-Definition and terminology:...
s, and include also the maximal outerplanar graph
Outerplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
s. Planar
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
3-trees are also known as Apollonian network
Apollonian network
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable...
s.