Caterpillar Graph

Author

Eric W. Weisstein
May 16, 2017

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/CaterpillarGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/CaterpillarGraph.html.

©2017 Wolfram Research, Inc. except for portions noted otherwise

Usage

?CaterpillarQ

Enumeration

Select[GraphData["Tree"],CaterpillarQ[Graph[#]]&]

Flatten[Position[Graphs[8],_?CaterpillarQ]]

Counts

A005418

Table[Total[Boole[CaterpillarGraphQ/@Trees[n]]],{n,16}]//Timing

Table[Length@GraphData["Caterpillar",n],{n,12}]

Formula

Table[2^(n-2)+2^(Floor[n/2]-1),{n,40}]

Graphics

Caterpillars

ShowGraphArray[Take[cat,7],ImageSize->500]

Noncaterpillars

Length/@(noncat=Select[#,!CaterpillarQ[#]&]&/@Trees/@Range[7,9])//Timing

ShowGraphArray[Map[RadialEmbedding,
Flatten[Partition[#,6,6,{1,1},{}]&/@noncat,1],
{2}],VertexStyle->Disk[.08],GraphicsSpacing->.2]