Caterpillar tree
Encyclopedia
In graph theory
, a caterpillar or caterpillar tree is a tree
in which all the vertices of the caterpillar 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 A. Hobbs. As colorfully write, "A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed."
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 in which the non-leaf vertices induce a 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 which all the vertices are within distance 2 of a central path
.
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
to represent the structure of benzenoid hydrocarbon
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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a caterpillar or caterpillar tree is a tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
in which all the vertices of the caterpillar 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 A. 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 graphPath graphIn the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
. - They are the trees in which there exists a path that contains every node of degree two or more.
- They are the trees in which every node 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 drawnGraph drawingGraph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
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 graphLine graphIn graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
s contain a Hamiltonian pathHamiltonian pathIn the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting 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 completionHamiltonian completionThe Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.The problem is clearly NP-hard in general case...
) 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-freeTriangle-free graphIn 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 girth ≥ 4, graphs with no induced 3-cycle, or locally...
interval graphInterval graphIn graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
s.
Generalizations
A k-tree is a chordal graphChordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
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 in which the non-leaf vertices induce a 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
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
in which all the vertices are within distance 2 of a central path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
.
Enumeration
Caterpillars provide one of the rare graph enumerationGraph enumeration
In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the graph...
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, ... .
Applications
Caterpillar trees have been used in chemical graph theoryChemical graph theory
Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena....
to represent the structure of benzenoid hydrocarbon
Hydrocarbon
In organic chemistry, a hydrocarbon is an organic compound consisting entirely of hydrogen and carbon. Hydrocarbons from which one hydrogen atom has been removed are functional groups, called hydrocarbyls....
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.