Caterpillar tree

Last updated February 03, 2024

In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.

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.^[2]^[3]
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 K_1,3 by a path of length two.^[3]
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.^[3]^[4]
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.^[3]
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.^[5]
They are the connected graphs of pathwidth one.^[6]
They are the connected triangle-free interval graphs.^[7]
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.^[8]

Generalizations

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 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 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.^[6]

A lobster graph is a tree in which all the vertices are within distance 2 of a central path.^[9]

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 ^[1]

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 OEIS ).

Computational complexity

Finding a spanning caterpillar in a graph is NP-complete. 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 for the MSCP unless P = NP. Here f(n) is any polynomial-time computable function of n, the number of vertices of a graph.^[10]

There is a parametrized algorithm that finds an optimal solution for the MSCP in bounded treewidth 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.^[10]

Applications

Caterpillar trees have been used in chemical graph theory 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. 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.^[2]^[11]^[12]

Related Research Articles

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

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.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

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 cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, a path decomposition of a graph $G$ is, informally, a representation of $G$ as a "thickened" path graph, and the pathwidth of $G$ is a number that measures how much the path was thickened to form $G$ . More formally, a path-decomposition is a sequence of subsets of vertices of $G$ such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

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. These problems may be solved either exactly or asymptotically. The pioneers in this area of mathematics were George Pólya, Arthur Cayley and J. Howard Redfield.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In chemical graph theory, the Wiener index introduced by Harry Wiener, is a topological index of a molecule, defined as the sum of the lengths of the shortest paths between all pairs of vertices in the chemical graph representing the non-hydrogen atoms in the molecule.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.

In the mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after A. Goldner and Frank Harary, who proved in 1975 that it was the smallest non-Hamiltonian maximal planar graph. The same graph had already been given as an example of a non-Hamiltonian simplicial polyhedron by Branko Grünbaum in 1967.

In graph theory, the graph bandwidth problem is to label the $n$ vertices $v i$ of a graph $G$ with distinct integers so that the quantity $is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x -axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement .$

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

<span class="mw-page-title-main">Apollonian network</span> Graph formed by subdivision of triangles

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In graph theory, a branch of mathematics, a chordal completion of a given undirected graph $G$ is a chordal graph, on the same vertex set, that has $G$ as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible.

References

1 2 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 .
1 2 3 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 .
1 2 3 4 Harary, Frank; Schwenk, Allen J. (1971), "Trees with Hamiltonian square", Mathematika , 18: 138–140, doi:10.1112/S0025579300008494, hdl: 2027.42/153141 .
↑ Harary, Frank; Schwenk, Allen J. (1972), "A new crossing number for bipartite graphs", Utilitas Math., 1: 203–209.
↑ 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 .
1 2 Proskurowski, Andrzej; Telle, Jan Arne (1999), "Classes of graphs with restricted interval models" (PDF), Discrete Mathematics and Theoretical Computer Science, 3: 167–176.
↑ Eckhoff, Jürgen (1993), "Extremal interval graphs", Journal of Graph Theory , 17 (1): 117–127, doi:10.1002/jgt.3190170112 .
↑ E. Guseinov, Patterns of adjacency matrices and yet another proof that caterpillars are graceful
↑ Weisstein, Eric W. "Lobster graph". MathWorld .
1 2 Khosravani, Masoud (2011). Searching for optimal caterpillars in general and bounded treewidth graphs (Ph.D.). University of Auckland.
↑ Gutman, Ivan (1977), "Topological properties of benzenoid systems", Theoretica Chimica Acta, 45 (4): 309–315, doi:10.1007/BF00554539 .
↑ 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, S2CID 91687862 .

External links

Weisstein, Eric W. "Caterpillar". MathWorld .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[hs73-1] 1 2 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 .

[eb87-2] 1 2 3 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 .

[hs71-3] 1 2 3 4 Harary, Frank; Schwenk, Allen J. (1971), "Trees with Hamiltonian square", Mathematika , 18: 138–140, doi:10.1112/S0025579300008494, hdl: 2027.42/153141 .

[4] Harary, Frank; Schwenk, Allen J. (1972), "A new crossing number for bipartite graphs", Utilitas Math., 1: 203–209.

[5] 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 .

[pt99-6] 1 2 Proskurowski, Andrzej; Telle, Jan Arne (1999), "Classes of graphs with restricted interval models" (PDF), Discrete Mathematics and Theoretical Computer Science, 3: 167–176.

[7] Eckhoff, Jürgen (1993), "Extremal interval graphs", Journal of Graph Theory , 17 (1): 117–127, doi:10.1002/jgt.3190170112 .

[8] E. Guseinov, Patterns of adjacency matrices and yet another proof that caterpillars are graceful

[9] Weisstein, Eric W. "Lobster graph". MathWorld .

[mk11-10] 1 2 Khosravani, Masoud (2011). Searching for optimal caterpillars in general and bounded treewidth graphs (Ph.D.). University of Auckland.

[11] Gutman, Ivan (1977), "Topological properties of benzenoid systems", Theoretica Chimica Acta, 45 (4): 309–315, doi:10.1007/BF00554539 .

[12] 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, S2CID 91687862 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]