Caterpillar tree

[1][2] As Harary & Schwenk (1973) colorfully write, "A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed.

"[1] The following characterizations all describe the caterpillar trees: A k-tree is a chordal graph with exactly n − k maximal cliques, 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 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.

[10] There is a parametrized algorithm that finds an optimal solution for the MSCP in bounded treewidth graphs.

[10] Caterpillar trees have been used in chemical graph theory to represent the structure of benzenoid hydrocarbon molecules.