Closed-Form Formulas for Fibonacci Numbers of Broom and Double Star Graphs
Abstract
Let 𝐺=(𝑉(𝐺),𝐸(𝐺)) be a graph, and let 𝑖(𝐺) denote the number of independent sets of 𝐺, commonly known as the Fibonacci number of the graph. This paper investigates the Fibonacci numbers of two graph families, namely broom graphs and double star graphs, which naturally generalize the classical path and star graphs. By employing a combinatorial approach based on the systematic enumeration of independent sets, we establish recurrence relations governing these invariants. In particular, the Fibonacci number of the broom graph 𝐵𝑛,𝑚 satisfies 𝑖(𝐵𝑛,𝑚) = 𝑖(𝐵𝑛−1,𝑚) + 𝑖(𝐵𝑛−2,𝑚) under appropriate initial conditions, while the Fibonacci number of the double star graph 𝑆𝑛,𝑚 satisfies 𝑖(𝑆𝑛,𝑚) = 𝑖(𝑆𝑛−1,𝑚) + 2 𝑛−1 × 𝑖(𝑆0,𝑚). Solving these recurrences yields explicit closed-form expressions for both graph families. To the best of our knowledge, such unified recurrence-based characterizations and closed formulas for the Fibonacci numbers of broom and double star graphs have not been previously reported. These results clarify how the structural features of these graphs influence the growth behavior of their Fibonacci numbers and enrich the study of Fibonacci type invariants in graph theory.
Keywords
Full Text:
PDFReferences
G. Chitra and V. Mohanapriya, ‘Fibonacci Antimagic Labeling of Some Special Graphs’, International Journal of Emerging Technologies and Innovative Research, vol. 5, no. 6, pp. 750–753, 2018, [Online]. Available: https://www.jetir.org/view?paper=JETIR1806796
N. Y. Sari, E. Noviani, and F. Fran, ‘Pelabelan Fibonacci Prima Ke-K Pada Graf H dan Graf Ulat H_n’, Jurnal Publikasi Ilmiah Matematika (KUBIK), vol. 8, no. 2, pp. 89–98, 2023, doi: 10.15575/kubik.v8i2.29290.
D. S. Permatasari and P. Agung, ‘Bilangan Fibonacci dalam Perkembangbiakan Lebah Madu’, Jurnal Equation: Teori dan Penelitian Pendidikan Matematika, vol. 5, no. 1, pp. 103–115, Mar. 2022, doi: 10.29300/equation.v5i1.5442.
J. R. Chasnov, Fibonacci Numbers and the Golden Ratio. The Hong Kong University of Science and Technology, 2016. [Online]. Available: https://www.math.hkust.edu.hk/~machas/fibonacci.pdf
D. Grinberg, ‘An Introduction to Graph Theory’, Jun. 10, 2025, arXiv: arXiv:2308.04512. doi: 10.48550/arXiv.2308.04512.
F. Susanto, R. Simanjuntak, and E. T. Baskoro, ‘Further Results on the Total Vertex Irregularity Strength of Trees’, Electronic Journal of Graph Theory and Applications, vol. 13, no. 1, pp. 123–140, Apr. 2025, doi: 10.5614/ejgta.2025.13.1.9.
K. R. Saoub, Graph Theory: An Introduction to Proofs, Algorithms, and Applications, 1st ed. in Textbooks in mathematics. Boca Raton London New York: CRC Press, 2021. doi: 10.1201/9781138361416.
I. Gutman, V. R. Kulli, and I. R. zepovic, ‘Irregularity Sombor Index’, Bulletin of the Academy of Sciences and Arts of the Republic of Serbia, Class of Mathematical and Natural Sciences, vol. 156, pp. 31–37, 2023, doi: 10.5281/zenodo.18005956.
V. Zverovich, Modern Applications of Graph Theory, 1st ed. Oxford: Oxford University Press, 2021. doi: 10.1093/oso/9780198856740.001.0001.
G. Ali, M. Bača, M. Lascsáková, A. Semaničová-Feňovčíková, A. ALoqaily, and N. Mlaiki, ‘Modular Total Vertex Irregularity Strength of Graphs’, AIMS Mathematics, vol. 8, no. 4, pp. 7662–7671, 2023, doi: 10.3934/math.2023384.
S. D. Pasham, ‘Using Graph Theory to Improve Communication Protocols in AI-Powered IoT Networks’, Research and Analysis Journal, vol. 7, no. 02, pp. 01–32, Feb. 2024, doi: 10.18535/raj.v7i02.390.
H. Prodinger and R. F. Tichy, ‘Fibonacci Numbers of Graphs’, The Fibonacci Quarterly, vol. 20, no. 1, pp. 16–21, Feb. 1982, doi: 10.1080/00150517.1982.12430021.
Ö. Eğecioğlu and V. Iršič, ‘Fibonacci-Run Graphs I: Basic Properties’, Discrete Applied Mathematics, vol. 295, pp. 70–84, May 2021, doi: 10.1016/j.dam.2021.02.025.
G. Perarnau and W. Perkins, ‘Counting Independent Sets in Cubic Graphs of Given Girth’, Journal of Combinatorial Theory, Series B, vol. 133, pp. 211–242, Nov. 2018, doi: 10.1016/j.jctb.2018.04.009.
D. S. Taletskii, ‘On The Number of Independent and K-Dominating Sets in Graphs with Average Vertex
Degree at Most K’, Sbornik: Mathematics, vol. 214, no. 11, pp. 1627–1650, 2023, doi: 10.4213/sm9870e.
I. Sason, ‘A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets
in Bipartite Graphs’, Entropy, vol. 23, no. 3, p. 270, Feb. 2021, doi: 10.3390/e23030270.
E. Cohen, W. Perkins, M. Sarantis, and P. Tetali, ‘On the Number of Independent Sets in Uniform, Regular, Linear Hypergraphs’, European Journal of Combinatorics, vol. 99, p. 103401, Jan. 2022, doi:
1016/j.ejc.2021.103401.
F. Ignatius and S. Kaspar, ‘A New Graph Labeling with Tribonacci, Fibonacci and Triangular Numbers’,
Discover Sustainability, vol. 5, no. 1, p. 130, Jun. 2024, doi: 10.1007/s43621-024-00325-z.
O. Sikhwal and A. Rastogi, ‘Domination, Independence and Fibonacci Numbers in Graphs Containing Disjoint Cycles’, International Journal of Computational and Applied Mathematics & Computer Science,
vol. 2, pp. 65–68, Sep. 2022, doi: 10.37394/232028.2022.2.12.
K. U. Sreeja, P. B. Vinodkumar, and P. B. Ramkumar, ‘Independence Polynomial and Z Counting
Polynomial of a Fibonacci Tree’, Turkic World Mathematical Society Journal of Applied and Engineering
Mathematics, vol. 21, no. 3, pp. 1569–1577, 2022, doi: 10.47748/twmsjaem.2022.21.3.006.
S. Mitra, A. Pritchard, and S. Bhoumik, ‘On Fibonacci Cordial Labeling of Some Planar Graphs’, Turkic World Mathematical Society Journal of Applied and Engineering Mathematics, vol. 15, no. 5, pp. 1153–
, 2025, doi: 10.5281/zenodo.18006093.
J. DeMaio and J. Jacobson, ‘Fibonacci Number of the Tadpole Graph’, Electronic Journal of Graph
Theory and Applications, vol. 2, no. 2, pp. 129–138, 2014, doi: 10.5614/ejgta.2014.2.2.5.
A. Knopfmacher, R. F. Tichy, S. Wagner, and V. Ziegler, ‘Graphs, Partitions and Fibonacci Numbers’, Discrete Applied Mathematics, vol. 155, no. 10, pp. 1175–1187, May 2007, doi:
1016/j.dam.2006.10.010.
L. A. Dosal-Trujillo and H. Galeana-Sánchez, ‘The Fibonacci Numbers of Certain Subgraphs of Circulant Graphs’, AKCE International Journal of Graphs and Combinatorics, vol. 12, no. 2–3, pp. 94–103, Nov. 2015, doi: 10.1016/j.akcej.2015.11.002.
L. A. Dosal-Trujillo and H. Galeana-Sánchez, ‘On the Fibonacci Numbers of the Composition of Graphs’, Discrete Applied Mathematics, vol. 266, pp. 213–218, Aug. 2019, doi: 10.1016/j.dam.2019.02.047.
J. Seibert and L. Koudela, ‘The Fibonacci Numbers for The Molecular Graphs of Linear Phenylenes’,
International Journal of Pure and Apllied Mathematics, vol. 106, no. 1, Feb. 2016, doi:
12732/ijpam.v106i1.25.
M. M. N. Bangkit and B. Rahadjeng, ‘Dekomposisi Graf Bintang, Graf Bintang Ganda, dan Graf Sapu’,
MATHunesa: Jurnal Ilmiah Matematika, vol. 10, no. 1, pp. 218–225, Apr. 2022, doi:
26740/mathunesa.v10n1.p218-225.
M. Ghorbani and M. Dehmer, ‘On the Roots of the Modified Orbit Polynomial of a Graph’, Symmetry,
vol. 13, no. 6, p. 972, May 2021, doi: 10.3390/sym13060972.
E. Győri, R. Wang, and S. Woolfson, ‘Extremal Problems of Double Stars’, Discrete Mathematics &
Theoretical Computer Science, vol. 24, no. 2, p. 8499, Apr. 2023, doi: 10.46298/dmtcs.8499.
N. Kusumastuti, Raventino, and F. Fran, ‘The Diachromatic Number of Double Star Graph’, Journal of Physics: Conference Series, vol. 2106, no. 1, p. 012024, Nov. 2021, doi: 10.1088/1742-
/2106/1/012024.
A. Yurttas Gunes, S. Delen, M. Demirci, A. S. Cevik, and I. N. Cangul, ‘Fibonacci Graphs’, Symmetry,
vol. 12, no. 9, p. 1383, Aug. 2020, doi: 10.3390/sym12091383.
DOI: http://dx.doi.org/10.30829/zero.v9i3.26839
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Publisher : Department of Mathematics Faculty of Science and Technology Universitas Islam Negeri Sumatera Utara Medan | |
✉️ Email: zero_journal@uinsu.ac.id 📱 WhatsApp:085270009767 (Admin Official) | |
 |  |  |  |  |