In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a caterpillar or caterpillar tree is a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
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."
[.]
Equivalent characterizations
The following characterizations all describe the caterpillar trees:
*They are the trees for which removing the leaves and incident edges produces a
path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
.
*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
In graph theory, a star is the complete bipartite graph a tree (graph theory), tree with one internal node and leaves (but no internal nodes and leaves when ). Alternatively, some authors define to be the tree of order (graph theory), order ...
''K''
1,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
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
is a
Hamiltonian graph
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
. 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 graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
s contain a
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
; 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.
*They are the connected
triangle-free
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...
interval graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line,
with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
...
s.
*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.
Generalizations
A
''k''-tree is a
chordal graph
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
with exactly
maximal cliques, each containing vertices; in a ''k''-tree that is not itself a , 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
separator
Separator can refer to:
* A mechanical device to separate fluids and solids, like
** Cream separator, separates cream from milk
** Demister (vapor), removal of liquid droplets entrained in a vapor stream
** Separator (oil production), of an oil pr ...
''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
pathwidth ''k''.
[.]
A lobster graph is a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
in which all the vertices are within distance 2 of a central
path.
Enumeration
Caterpillars provide one of the rare
graph enumeration problems for which a precise formula can be given: when ''n'' ≥ 3, the number of caterpillars with ''n'' unlabeled vertices is
:
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, ... .
Computational complexity
Finding a spanning caterpillar in a graph is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
. 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)-
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
for the MSCP unless
P = NP
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used above ...
. Here f(n) is any polynomial-time computable function of n, the number of vertices of a graph.
There is a parametrized algorithm that finds an optimal solution for the MSCP in bounded
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gr ...
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
Halin graph.
Applications
Caterpillar trees have been used in
chemical graph theory to represent the structure of
benzenoid
In organic chemistry, benzenoids are a class of organic compounds with at least one benzene ring. These compounds have increased stability due resonance in the benzene rings. Most aromatic hydrocarbons are benzenoid. Notable counterexamples are c ...
hydrocarbon
In organic chemistry, a hydrocarbon is an organic compound consisting entirely of hydrogen and carbon. Hydrocarbons are examples of group 14 hydrides. Hydrocarbons are generally colourless and hydrophobic, and their odors are usually weak or ...
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. 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.
[.][.]
References
External links
*{{mathworld, urlname=Caterpillar, title=Caterpillar
Trees (graph theory)
Mathematical chemistry