Read More
Date: 26-3-2022
1191
Date: 28-3-2022
1645
Date: 18-3-2022
1455
|
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.
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.
|
|
مخاطر خفية لمكون شائع في مشروبات الطاقة والمكملات الغذائية
|
|
|
|
|
"آبل" تشغّل نظامها الجديد للذكاء الاصطناعي على أجهزتها
|
|
|
|
|
تستخدم لأول مرة... مستشفى الإمام زين العابدين (ع) التابع للعتبة الحسينية يعتمد تقنيات حديثة في تثبيت الكسور المعقدة
|
|
|