K-tree

From Wikipedia, the free encyclopedia
The Goldner–Harary graph, an example of a planar 3-tree.

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.[1]

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.[2]

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.[1][2]

Certain k-trees with k ≥ 3 are also the graphs formed by the edges and vertices of stacked polytopes, polytopes 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.[3] 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.[4]

1-trees are the same as unrooted trees. 2-trees are maximal series-parallel graphs,[5] and include also the maximal outerplanar graphs. Planar 3-trees are also known as Apollonian networks.[6]

References

  1. ↑ 1.0 1.1 Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences 11 (2-4): 57–64, MR 966069 .
  2. ↑ 2.0 2.1 Grötschel, Martin; Katona, Gyula O. H. (2008), Building Bridges: between Mathematics and Computer Science, Bolyai Society Mathematical Studies 19, Springer-Verlag, p. 390, ISBN 978-3-540-85218-6 .
  3. ↑ Below, Alexander; De Loera, Jesús A.; Richter-Gebert, Jürgen. "The Complexity of Finding Small Triangulations of Convex 3-Polytopes". arXiv:math/0012177..
  4. ↑ Kleinschmidt, Peter (1 December 1976). "Eine graphentheoretische Kennzeichnung der Stapelpolytope". Archiv der Mathematik 27 (1): 663–667. doi:10.1007/BF01224736. 
  5. ↑ Hwang, Frank; Richards, Dana; Winter, Pawel (1992), The Steiner Tree Problem, Annals of Discrete Mathematics (North-Holland Mathematics Studies) 53, Elsevier, p. 177, ISBN 978-0-444-89098-6 .
  6. ↑ Distances in random Apollonian network structures, talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06.
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.