Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
K-tree
open-in-new
<h2 id="characterizations">Characterizations</h2> <p>The <i>k</i>-trees are exactly the maximal graphs with a <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> of <i>k</i> ("maximal" means that no more edges can be added without increasing their treewidth).<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> They are also exactly the <a href="/facts/Chordal_graph/7hNerUdA">chordal graphs</a> all of whose <a href="/facts/Maximal_clique/XK9ppLz5">maximal cliques</a> are the same size <i>k</i> + 1 and all of whose minimal clique separators are also all the same size <i>k</i>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <h2 id="related-graph-classes">Related graph classes</h2> <p>1-trees are the same as <a href="/facts/Tree_(graph_theory)/TCWk4Joy">trees</a>. 2-trees are maximal <a href="/facts/Series%25E2%2580%2593parallel_graph/XdfWgomL">series–parallel graphs</a>,<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> and include also the maximal <a href="/facts/Outerplanar_graph/FrAgUpcV">outerplanar graphs</a>. <a href="/facts/Planar_graph/plREagr9">Planar</a> 3-trees are also known as <a href="/facts/Apollonian_network/C9m4Gd3J">Apollonian networks</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p><p>The graphs that have <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> at most <i>k</i> are exactly the <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraphs</a> of <i>k</i>-trees, and for this reason they are called <a href="/facts/Partial_k-tree/laI60U15">partial <i>k</i>-trees</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>The graphs formed by the edges and vertices of <i>k</i>-dimensional <a href="/facts/Stacked_polytope/FdwYkoDk">stacked polytopes</a>, <a href="/facts/Polytope/a76nXrL0">polytopes</a> formed by starting from a <a href="/facts/Simplex/0FCfNRN8">simplex</a> and then repeatedly gluing simplices onto the faces of the polytope, are <i>k</i>-trees when <i>k</i> ≥ 3.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> This gluing process mimics the construction of <i>k</i>-trees by adding vertices to a clique.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> A <i>k</i>-tree is the graph of a stacked polytope if and only if no three (<i>k</i> + 1)-vertex cliques have <i>k</i> vertices in common.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences, 11 (2–4): 57–64, MR 0966069. <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), "Structural Properties of Sparse Graphs" (PDF), in Grötschel, Martin; Katona, Gyula O. H. (eds.), Building Bridges: between Mathematics and Computer Science, Bolyai Society Mathematical Studies, vol. 19, Springer-Verlag, p. 390, ISBN 978-3-540-85218-6. <a href="978-3-540-85218-6" target="_blank">978-3-540-85218-6</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), "Structural Properties of Sparse Graphs" (PDF), in Grötschel, Martin; Katona, Gyula O. H. (eds.), Building Bridges: between Mathematics and Computer Science, Bolyai Society Mathematical Studies, vol. 19, Springer-Verlag, p. 390, ISBN 978-3-540-85218-6. <a href="978-3-540-85218-6" target="_blank">978-3-540-85218-6</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences, 11 (2–4): 57–64, MR 0966069. <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Hwang, Frank; Richards, Dana; Winter, Pawel (1992), The Steiner Tree Problem, Annals of Discrete Mathematics (North-Holland Mathematics Studies), vol. 53, Elsevier, p. 177, ISBN 978-0-444-89098-6. <a href="978-0-444-89098-6" target="_blank">978-0-444-89098-6</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Distances in random Apollonian network structures Archived 2011-07-21 at the Wayback Machine, talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06. <a href="http://www.cirm.univ-mrs.fr/videos/2008/exposes/325/Darrasse.pdf" target="_blank">http://www.cirm.univ-mrs.fr/videos/2008/exposes/325/Darrasse.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), "Structural Properties of Sparse Graphs" (PDF), in Grötschel, Martin; Katona, Gyula O. H. (eds.), Building Bridges: between Mathematics and Computer Science, Bolyai Society Mathematical Studies, vol. 19, Springer-Verlag, p. 390, ISBN 978-3-540-85218-6. <a href="978-3-540-85218-6" target="_blank">978-3-540-85218-6</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>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. <a href="/wiki/Micha_Perles" target="_blank">/wiki/Micha_Perles</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Below, Alexander; De Loera, Jesús A.; Richter-Gebert, Jürgen (February 2004), "The complexity of finding small triangulations of convex 3-polytopes", Journal of Algorithms, 50 (2): 134–167, arXiv:math/0012177, doi:10.1016/s0196-6774(03)00092-0 <a href="/wiki/Jes%C3%BAs_A._De_Loera" target="_blank">/wiki/Jes%C3%BAs_A._De_Loera</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Kleinschmidt, Peter (1 December 1976), "Eine graphentheoretische Kennzeichnung der Stapelpolytope", Archiv der Mathematik, 27 (1): 663–667, doi:10.1007/BF01224736 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> </ol>