Caterpillar tree

<h2 id="equivalent-characterizations">Equivalent characterizations</h2>
The following characterizations all describe the caterpillar trees:

<ul><li>They are the trees for which removing the leaves and incident edges produces a <a href="/facts/Path_graph/4Y2f35eM">path graph</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>They are the trees in which there exists a path that contains every vertex of degree two or more.</li>
<li>They are the trees in which every vertex of degree at least three has at most two non-leaf neighbors.</li>
<li>They are the trees that do not contain as a subgraph the graph formed by replacing every edge in the <a href="/facts/Star_graph/PNW0H6eK">star graph</a> K1,3 by a path of length two.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>They are the connected graphs that can be <a href="/facts/Graph_drawing/uhh73BVo">drawn</a> with their vertices on two parallel lines, with edges represented as non-crossing line segments that have one endpoint on each line.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li>They are the trees whose <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">square</a> is a <a href="/facts/Hamiltonian_graph/MHjY2xoY">Hamiltonian graph</a>. That is, in a caterpillar, there exists a cyclic sequence of all the vertices in which each adjacent pair of vertices in the sequence is at distance one or two from each other, and trees that are not caterpillars do not have such a sequence. A cycle of this type may be obtained by drawing the caterpillar on two parallel lines and concatenating the sequence of vertices on one line with the reverse of the sequence on the other line.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li>
<li>They are the trees whose <a href="/facts/Line_graph/RWNxSy5j">line graphs</a> contain a <a href="/facts/Hamiltonian_path/MHjY2xoY">Hamiltonian path</a>; such a path may be obtained by the ordering of the edges in a two-line drawing of the tree. More generally the number of edges that need to be added to the line graph of an arbitrary tree so that it contains a Hamiltonian path (the size of its <a href="/facts/Hamiltonian_completion/E63XC6ex">Hamiltonian completion</a>) equals the minimum number of edge-disjoint caterpillars that the edges of the tree can be decomposed into.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a></li>
<li>They are the connected graphs of <a href="/facts/Pathwidth/Gf5S2byH">pathwidth</a> one.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li>
<li>They are the connected <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free</a> <a href="/facts/Interval_graph/oLwYI3uT">interval graphs</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a></li>
<li>They are n-vertex graphs whose adjacency matrices can be written in such a way that the ones of the upper triangular part form a path of length n − 1 beginning at the upper right corner and going down or left.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a></li></ul>
<h2 id="generalizations">Generalizations</h2>
A <a href="/facts/K-tree/qgdXYe5r">k-tree</a> is a <a href="/facts/Chordal_graph/7hNerUdA">chordal graph</a> with exactly n − k <a href="/facts/Maximal_clique/XK9ppLz5">maximal cliques</a>, each containing k + 1 vertices; in a k-tree that is not itself a (k + 1)-clique, each maximal clique either separates the graph into two or more components, or it contains a single leaf vertex, a vertex that belongs to only a single maximal clique. A k-path is a k-tree with at most two leaves, and a k-caterpillar is a k-tree that can be partitioned into a k-path and some k-leaves, each adjacent to a <a href="/facts/Vertex_separator/JcBrRzQe">separator</a> k-clique of the k-path. In this terminology, a 1-caterpillar is the same thing as a caterpillar tree, and k-caterpillars are the edge-maximal graphs with <a href="/facts/Pathwidth/Gf5S2byH">pathwidth</a> k.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
A lobster graph is a <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> in which all the vertices are within distance 2 of a central <a href="/facts/Path_(graph_theory)/WMsq21Nf">path</a>.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

<h2 id="enumeration">Enumeration</h2>
Caterpillars provide one of the rare <a href="/facts/Graph_enumeration/3AgPDEAV">graph enumeration</a> problems for which a precise formula can be given: when n ≥ 3, the number of caterpillars with n unlabeled vertices is <a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

2
          
            n
            −
            4
          
        
        +
        
          2
          
            ⌊
            (
            n
            −
            4
            )
            
              /
            
            2
            ⌋
          
        
        .
      
    
    {\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}

For n = 1, 2, 3, ... the numbers of n-vertex caterpillars are

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ... (sequence A005418 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>).
<h2 id="computational-complexity">Computational complexity</h2>
Finding a spanning caterpillar in a graph is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>. A related optimization problem is the Minimum Spanning Caterpillar Problem (MSCP), where a graph has dual costs over its edges and the goal is to find a caterpillar tree that spans the input graph and has the smallest overall cost. Here the cost of the caterpillar is defined as the sum of the costs of its edges, where each edge takes one of the two costs based on its role as a leaf edge or an internal one. There is no f(n)-<a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithm</a> for the MSCP unless <a href="/facts/P_%253D_NP/xoC7Ruda">P = NP</a>. Here f(n) is any polynomial-time computable function of n, the number of vertices of a graph.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>
There is a parametrized algorithm that finds an optimal solution for the MSCP in bounded <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> graphs. So both the Spanning Caterpillar Problem and the MSCP have linear time algorithms if a graph is an outerplanar, a series-parallel, or a <a href="/facts/Halin_graph/9kEV2cjv">Halin graph</a>.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

<h2 id="applications">Applications</h2>
Caterpillar trees have been used in <a href="/facts/Chemical_graph_theory/bst0G88w">chemical graph theory</a> to represent the structure of <a href="/facts/Benzenoid/EVM6gPLN">benzenoid</a> <a href="/facts/Hydrocarbon/Dcg95Ju5">hydrocarbon</a> molecules. In this representation, one forms a caterpillar in which each edge corresponds to a 6-carbon ring in the molecular structure, and two edges are incident at a vertex whenever the corresponding rings belong to a sequence of rings connected end-to-end in the structure. El-Basil (1987) writes, "It is amazing that nearly all graphs that played an important role in what is now called "chemical graph theory" may be related to caterpillar trees." In this context, caterpillar trees are also known as benzenoid trees and Gutman trees, after the work of Ivan Gutman in this area.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a><a class="footnote-ref" id="fnref:20" href="#fn:20">20</a><a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>

<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/Caterpillar.html">"Caterpillar"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars" (PDF), Discrete Mathematics, 6 (4): 359–365, doi:10.1016/0012-365x(73)90067-8, hdl:2027.42/33977. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">El-Basil, Sherif (1987), "Applications of caterpillar trees in chemistry and physics", Journal of Mathematical Chemistry, 1 (2): 153–174, doi:10.1007/BF01205666, S2CID 121322252. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars" (PDF), Discrete Mathematics, 6 (4): 359–365, doi:10.1016/0012-365x(73)90067-8, hdl:2027.42/33977. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">El-Basil, Sherif (1987), "Applications of caterpillar trees in chemistry and physics", Journal of Mathematical Chemistry, 1 (2): 153–174, doi:10.1007/BF01205666, S2CID 121322252. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Harary, Frank; Schwenk, Allen J. (1971), "Trees with Hamiltonian square", Mathematika, 18: 138–140, doi:10.1112/S0025579300008494, hdl:2027.42/153141. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Harary, Frank; Schwenk, Allen J. (1971), "Trees with Hamiltonian square", Mathematika, 18: 138–140, doi:10.1112/S0025579300008494, hdl:2027.42/153141. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Harary, Frank; Schwenk, Allen J. (1971), "Trees with Hamiltonian square", Mathematika, 18: 138–140, doi:10.1112/S0025579300008494, hdl:2027.42/153141. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Harary, Frank; Schwenk, Allen J. (1972), "A new crossing number for bipartite graphs", Utilitas Math., 1: 203–209. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Harary, Frank; Schwenk, Allen J. (1971), "Trees with Hamiltonian square", Mathematika, 18: 138–140, doi:10.1112/S0025579300008494, hdl:2027.42/153141. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Raychaudhuri, Arundhati (1995), "The total interval number of a tree and the Hamiltonian completion number of its line graph", Information Processing Letters, 56 (6): 299–306, doi:10.1016/0020-0190(95)00163-8. <a href="/wiki/Information_Processing_Letters" target="_blank">/wiki/Information_Processing_Letters</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Proskurowski, Andrzej; Telle, Jan Arne (1999), "Classes of graphs with restricted interval models" (PDF), Discrete Mathematics and Theoretical Computer Science, 3: 167–176. <a href="http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf" target="_blank">http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Eckhoff, Jürgen (1993), "Extremal interval graphs", Journal of Graph Theory, 17 (1): 117–127, doi:10.1002/jgt.3190170112. <a href="/wiki/Journal_of_Graph_Theory" target="_blank">/wiki/Journal_of_Graph_Theory</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">E. Guseinov, Patterns of adjacency matrices and yet another proof that caterpillars are graceful [1] <a href="https://elmarguseinov.medium.com/patterns-of-adjacency-matrices-and-yet-another-proof-that-caterpillars-are-graceful-9511ef7472d4" target="_blank">https://elmarguseinov.medium.com/patterns-of-adjacency-matrices-and-yet-another-proof-that-caterpillars-are-graceful-9511ef7472d4</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Proskurowski, Andrzej; Telle, Jan Arne (1999), "Classes of graphs with restricted interval models" (PDF), Discrete Mathematics and Theoretical Computer Science, 3: 167–176. <a href="http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf" target="_blank">http://www.emis.de/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Weisstein, Eric W. "Lobster graph". MathWorld. <a href="/wiki/Eric_W._Weisstein" target="_blank">/wiki/Eric_W._Weisstein</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars" (PDF), Discrete Mathematics, 6 (4): 359–365, doi:10.1016/0012-365x(73)90067-8, hdl:2027.42/33977. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Khosravani, Masoud (2011). Searching for optimal caterpillars in general and bounded treewidth graphs (Ph.D.). University of Auckland. <a href="https://researchspace.auckland.ac.nz/handle/2292/8360?show=full" target="_blank">https://researchspace.auckland.ac.nz/handle/2292/8360?show=full</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Khosravani, Masoud (2011). Searching for optimal caterpillars in general and bounded treewidth graphs (Ph.D.). University of Auckland. <a href="https://researchspace.auckland.ac.nz/handle/2292/8360?show=full" target="_blank">https://researchspace.auckland.ac.nz/handle/2292/8360?show=full</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">El-Basil, Sherif (1987), "Applications of caterpillar trees in chemistry and physics", Journal of Mathematical Chemistry, 1 (2): 153–174, doi:10.1007/BF01205666, S2CID 121322252. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Gutman, Ivan (1977), "Topological properties of benzenoid systems", Theoretica Chimica Acta, 45 (4): 309–315, doi:10.1007/BF00554539. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">El-Basil, Sherif (1990), "Caterpillar (Gutman) trees in chemical graph theory", in Gutman, I.; Cyvin, S. J. (eds.), Advances in the Theory of Benzenoid Hydrocarbons, Topics in Current Chemistry, vol. 153, pp. 273–289, doi:10.1007/3-540-51505-4_28, ISBN 978-3-540-51505-0, S2CID 91687862. <a href="978-3-540-51505-0" target="_blank">978-3-540-51505-0</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
</ol>

Caterpillar tree open-in-new

Caterpillar tree