A k -Tree is an undirected graph formed from a complete graph with ( k + 1) vertices with successive additions of vertices such that each added vertex v has exactly k neighbors U such that k + 1 vertices (vertex v + vertices U ) form a clique [1] [2] .
Content
- 1 Descriptions
- 2 Connected graph classes
- 3 notes
- 4 Literature
Descriptions
k -Trees are exactly maximal graphs with a given tree width , that is, graphs to which one cannot add an edge without increasing the tree width of the graph [2] . It is also exactly chord graphs , all maximal clicks of which have the same size and all minimal clique separators which also have the same size k [1] .
Connected graph classes
1-Trees are the same as non-rooted trees . 2-trees are maximal parallel-sequential graphs [3] , and they also include maximal outerplanar graphs . Planar 3-trees are also known as Apollonius networks [4] .
Graphs that have a tree width not exceeding k are precisely subgraphs of k- trees, and for this reason they are called partial k- trees [2] .
Graphs formed by edges and vertices of k- dimensional block polytopes , that is, polyhedra formed from a simplex by successive gluing of the faces of simplexes, are k- trees if [5] . This gluing process imitates the construction of k- trees by adding vertices to the clique [6] . A k -Tree is a graph of a block polyhedron if and only if no three cliques with ( k + 1) vertices have k common vertices [7] .
Notes
- ↑ 1 2 Patil, 1986 , p. 57–64.
- ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2008 , p. 390
- ↑ Hwang, Richards, Winter, 1992 .
- ↑ Distances in random Apollonian network structures Archived July 21, 2011 to Wayback Machine , talk slides by Olivier Bodini, Alexis Darrasse, Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06
- ↑ Koch, Perles, 1976 , p. 420.
- ↑ Below, De Loera, Richter-Gebert .
- ↑ Kleinschmidt, 1976 , p. 663–667.
Literature
- Patil HP On the structure of k -trees // Journal of Combinatorics, Information and System Sciences. - 1986. - T. 11 , no. 2-4 . - S. 57–64 .
- Frank Hwang, Dana Richards, Pawel Winter. The Steiner Tree Problem. - Elsevier, 1992. - T. 53. - S. 177. - (Annals of Discrete Mathematics (North-Holland Mathematics Studies)). - ISBN 978-0-444-89098-6 .
- Jaroslav Nešetřil, Patrice Ossona de Mendez. Structural Properties of Sparse Graphs // Building Bridges: between Mathematics and Computer Science / Martin Grötschel, Gyula OH Katona. - Springer-Verlag, 2008. - T. 19. - S. 390. - (Bolyai Society Mathematical Studies). - ISBN 978-3-540-85218-6 .
- Etan Koch, Micha A. Perles. 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., 1976. - S. 391-420. Congressus Numerantium, No. Xvii.
- Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. The Complexity of Finding Small Triangulations of Convex 3-Polytopes.
- Peter Kleinschmidt. Eine graphentheoretische Kennzeichnung der Stapelpolytope // Archiv der Mathematik. - 1976. - December ( t. 27 , issue 1 ). - S. 663–667 . - DOI : 10.1007 / BF01224736 .