Caterpillar Graph

A caterpillar graph, caterpillar tree, or simply "caterpillar," is a tree in which every graph vertex is on a central stalk or only one graph edge away from the stalk (in other words, removal of its endpoints leaves a path graph; Gallian 2007). A tree is a caterpillar iff all nodes of degree  are surrounded by at most two nodes of degree two or greater.

An n-alkane graph is also sometimes known as a caterpillar graph (Boesch et al. 1974; Merrifield and Simmons 1989, pp. 161-162).

Caterpillar graphs are graceful.

The number of caterpillar trees on  nodes is

where  is the floor function (Harary and Schwenk 1973). For , 2, ... nodes, this gives 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, ... (OEIS A005418). The first few caterpillars are illustrated above.

The number of noncaterpillar trees on , 8, ... as 1, 3, 11, 34, 99, ... (OEIS A052471). The noncaterpillar trees on  nodes are illustrated above.

---

REFERENCES

Boesch, F. T.; Chen, S.; and McHugh, J. A. M. "On Covering the Points of a Graph with Point Disjoint Paths." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.

Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.

Gardner, M. Wheels, Life, and other Mathematical Amusements. New York: W. H. Freeman, p. 160, 1983.

Gutman, I. and El-Basil, S. "Topological Properties of Benzenoid Systems. XXXVII. Characterization of Certain Chemical Graphs." Z. Naturforsch. A 40, 923-926, 1985.

Harary, F. and Schwenk, A. J. "The Number of Caterpillars." Disc. Math. 6, 359-365, 1973.

Hoffman, N. "Binary Grids and a Related Counting Problem." Two Year Coll. Math. J. 9, 267-272, 1978.

Horton, M. "Graceful Trees: Statistics and Algorithms." Bachelor of Computing with Honours thesis. University of Tasmania, 2003. https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.

Merrifield, R. E. and Simmons, H. E. Topological Methods in Chemistry. New York: Wiley, 1989.

Sloane, N. J. A. Sequences A005418/M0771 and A052471 in "The On-Line Encyclopedia of Integer Sequences."Sulanke, R. A. "Moments of Generalized Motzkin Paths." J. Integer Sequences 3, No. 00.1.1, 2000. http://www.math.uwaterloo.ca/JIS/VOL3/SULANKE/sulanke.

اخر الاخبار

اخبار العتبة العباسية المقدسة

مجلة تسليم تدعو الباحثين والأكاديميين للمشاركة في أعدادها القادمة

المجمع العلمي يواصل إقامة محاضراته الأسبوعية في مقام الإمام المهدي (عجل الله فرجه)

جامعة الكفيل تطلق الدورة التدريبية الصيفية لطلبة كلية الهندسة التقنية

استعدادًا لزيارة الأربعين العتبة العباسية المقدسة تعقد الورشة التنسيقية الرابعة الخاصة بمراكز إرشاد التائهين

المزيد

الآخبار الصحية

دراسة علمية تكشف مفاجأة حول الأسباب الحقيقية للسمنة

دراسة: الأطباء يتجاهلون "سببا شائعا" لارتفاع ضغط الدم

نظامك الغذائي غني بالبروتين؟.. احذر هذه الآثار الجانبية

لا تتجاهلها.. أعراض تنذرك بأنك مهدد بالإصابة بالسكري

المزيد

الآخبار التكنلوجية

ISOFIX: معيار الأمان الذهبي لمقاعد الأطفال في السيارات

هل المحرك الأكبر دائمًا الأفضل للسيارة؟

اختبارات ناجحة لمحرك "VK-800" الروسي وتطويره لطائرة بايكال الخفيفة

رئيس إنفيديا: الذكاء الاصطناعي الصيني "محفز للتقدم العالمي"

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength