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.

اخر الاخبار

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

قسم الشؤون الفكرية يطلق باقة من النشاطات الرقمية الخاصة بشهر المحرم

العتبة العباسية المقدسة تختتم السلسلة الأولى لمشروع المحاضرات القرآنية العاشورائية في بابل

العتبة العباسية المقدسة تسلّم راية العزاء إلى تجمّع مواكب محافظة الديوانية

قسم الشؤون الفكرية يواصل إقامة المجالس الحسينية ضمن سلسلة (بيوت النعيم)

المزيد

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

تناول الجبن.. مفيد للجسم أم خطر يهدد صحتك؟

طبيبة أسنان تحذر.. لا تتجاهل هذه العلامة بعد التنظيف

يجب أن تأكل المزيد من الشمام هذا الصيف.. إليك السبب ؟

تأثير صحي كبير.. كم بيضة يجب أن تتناول يوميا؟

المزيد

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

أداء خلايا البيروفسكايت الشمسية تحت الماء قد يزيد كفاءة تحويل الكهرباء

مسافة الأمان: أساس القيادة الآمنة وتجنب الحوادث

هل القيادة السريعة تعني استهلاك اكثر للوقود؟

لماذا يعتبر كوكب المريخ غير صالح للحياة؟

المزيد

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

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