On the number of caterpillars

Christian Barrientos

Abstract


A caterpillar is a tree obtained from a path by attaching pendant vertices. The number of caterpillars of size n is a well-known result. In this work extend this result exploring the number of caterpillars of size n together with the cardinalities of the stable sets and the diameter. Three closed formulas are presented, giving the number of caterpillars of size n with: (i) smaller stable set of cardinality k, (ii) diameter d, and (iii) diameter d and smaller stable set of cardinality k.


Keywords


caterpillar, tree, enumeration

Full Text:

PDF

DOI: http://dx.doi.org/10.19184/ijc.2022.6.2.1

References

R. B. J. T. Allenby and A. Slomson, How to Count, an Introduction to Combinatoircs, CRC Press, Boca Raton, 2011.

F. Harary and A. J. Schwenk, The number of caterpillars, Discrete Math., 6(4) (1973), 359--365.

R. J. Wilson, Introduction to Graph Theory, 4th ed., Addison Wesley Longman Limited, Harlow, 1996.


Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats