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 2026). 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"].
