A lobster graph, lobster tree, or simply "lobster," is a tree with a path graph
such that every graph vertex has graph
distance at most 2 from the path. Equivalently, deleting all pendant
vertices leaves the empty graph on 0 vertices
or a caterpillar graph (Koh et al. 1980,
Chen et al. 1997, Gallian 2025). The numbers of lobsters on 
, 2, ... are 1, 1, 1, 2, 3, 6, 11, 23, 47, 105, 231, 532,
1224, 2872, ... (OEIS A130131), and the corresponding
numbers of nonlobsters are 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 19, 77, 287, ... (OEIS
A130132; the first few of which are illustrated
above). Precomputed properties of a number of lobster trees
are implemented in the Wolfram Language
as GraphData["Lobster"].
