graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a ''k''-tree is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

formed by starting with a (''k'' + 1)-vertex

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. A complete digraph is a directed graph in which every pair of distinct vertices is ...

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 A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

Characterizations

The ''k''-trees are exactly the maximal graphs with a

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

of ''k'' ("maximal" means that no more edges can be added without increasing their treewidth). They are also exactly the

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...

s all of whose

maximal clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...

s are the same size ''k'' + 1 and all of whose minimal clique separators are also all the same size ''k''..

Related graph classes

1-trees are the same as unrooted

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...

. 2-trees are maximal

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 t ...

s, and include also the maximal

outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...

Planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

3-trees are also known as

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 maxima ...

s. 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,

polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...

s formed by starting from a

simplex In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...

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.

References

{{reflist Graph minor theory Trees (graph theory) Perfect graphs Graph families