K-tree

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] In higher-dimensional geometry, the stacked polytopes have graphs that are k-trees.[7]

References

  1. 1 2 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. 1 2 Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), "Structural Properties of Sparse Graphs" (PDF), in Grötschel, Martin; Katona, Gyula O. H., 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.
  7. ↑ Koch, Etan; Perles, Micha A. (1976), "Covering efficiency of trees and k-trees", Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., pp. 391–420. Congressus Numerantium, No. XVII, MR 0457265. See in particular p. 420.
This article is issued from Wikipedia - version of the Monday, February 01, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.