The -centipede graph, -centipede tree, or simply "-centipede," is the tree on nodes obtained by joining the bottoms of copies of the path graph laid in a row with edges. It is therefore isomorphic to the -firecracker graph, with special cases summarized in the table below.graph1path graph 2path graph 3E graphThe rank polynomial of the centipede is given by
A spider graph, spider tree, or simply "spider," is a tree with one vertex of degree at least 3 and all others with degree at most 2. The numbers of spiders on , 2, ... nodes are 0, 0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, ... (OEIS A004250).The count of spider trees with nodes is the same as the number of integer partitions of into three or more parts. It also has closed form(1)where is the partition function P and is the floor function. A generating function for is given by(2)(3)(4)where is a q-Pochhammer symbol.Not all spiders are caterpillar graphs, norare all spiders lobster graphs.
An -firecracker is a graph obtained by the concatenation of -stars by linking one leaf from each (Chen et al. 1997, Gallian 2007).Firecracker graphs are graceful (Chen et al.1997, Gallian 2018).Precomputed properties of firecrackers are implemented in the Wolfram Language as GraphData["Firecracker", n, k].
The path graph is a tree with two nodes of vertex degree 1, and the other nodes of vertex degree 2. A path graph is therefore a graph that can be drawn so that all of its vertices and edges lie on a single straight line (Gross and Yellen 2006, p. 18).The path graph of length is implemented in the Wolfram Language as PathGraph[Range[n]], and precomputed properties of path graphs are available as GraphData["Path", n]. (Note that the Wolfram Language believes cycle graphs to be path graph, a convention that seems neither standard nor useful.)The path graph is known as the singleton graph and is equivalent to the complete graph and the star graph . is isomorphic to the complete bipartite graph and to .Path graphs are graceful.The path graph has chromatic polynomial, independence polynomial, matching polynomial, and reliability polynomial given by(1)(2)(3)(4)where . These have recurrence equations(5)(6)(7)(8)The line graph of..