A lobster graph, lobster tree, or simply "lobster," is a tree having the property that the removal of leaf nodes leaves 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"].
Chen, W.-C.; Lu, H.-I.; and Yeh, Y.-N. "Operations of Interlaced Trees and Graceful Trees." Southeast Asian Bull. Math.21,
337-348, 1997.Gallian, J. "Dynamic Survey of Graph Labeling."
Elec. J. Combin., Dynamic Survey DS6, Oct. 30, 2025. https://doi.org/10.37236/27.Koh,
K. M.; Rogers, D. G.; Teo, H. K.; and Yap, K. Y. "Graceful
Graphs: Some Further Results and Problems." Congr. Numer.29,
559-571, 1980.Sloane, N. J. A. Sequences A130131
and A130132 in "The On-Line Encyclopedia
of Integer Sequences."
,
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"].
