Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Caterpillar tree
Summary
In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.
Caterpillars were first studied in a series of papers by Harary and Schwenk. The name was suggested by Arthur Hobbs. As colorfully write, "A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed."
The following characterizations all describe the caterpillar trees:
They are the trees for which removing the leaves and incident edges produces a path graph.
They are the trees in which there exists a path that contains every vertex of degree two or more.
They are the trees in which every vertex of degree at least three has at most two non-leaf neighbors.
They are the trees that do not contain as a subgraph the graph formed by replacing every edge in the star graph K1,3 by a path of length two.
They are the connected graphs that can be drawn with their vertices on two parallel lines, with edges represented as non-crossing line segments that have one endpoint on each line.
They are the trees whose square is a Hamiltonian graph. 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.
They are the trees whose line graphs contain a Hamiltonian path; 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 Hamiltonian completion) equals the minimum number of edge-disjoint caterpillars that the edges of the tree can be decomposed into.
They are the connected graphs of pathwidth one.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.