Image by Engin_Akyurt on Pixabay · Pixabay License
k-tree
Sign in to savethumb|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.
~2 min read
Article
3 sectionsContents
- Characterizations
- Related graph classes
- References
thumb|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.