Article ID: MTJPAM-D-24-00028

Title: A study of Hamiltonian cycles, decomposition, and mixed, directed forms in the Fibonacci graph Fd,2n


Montes Taurus J. Pure Appl. Math. / ISSN: 2687-4814

Article ID: MTJPAM-D-24-00028; Volume 8 / Issue 1 / Year 2026, Pages 29-46

Document Type: Research Paper

Author(s): Savitha Honaganahally Chandregowda a, Anitha Narasimha Murthy b

aDepartment of Science and Humanities, PES University, Bengaluru-560085, Karnataka, India

bDepartment of Science and Humanities, PES University, Bengaluru-560085, Karnataka, India

Received: 16 February 2024, Accepted: 21 July 2025, Published: 2 March 2026

Corresponding Author: Savitha Honaganahally Chandregowda (Email address: savithahc@pesu.pes.edu)

Full Text: PDF

Abstract

A Knödel graph is a well-studied class of graphs known for its unique structural properties, and the Fibonacci graph Fd, 2n serves as a specialized class of these graphs. This paper introduces the concept of Fibonacci-length Hamiltonian cycles in Fd, 2n. We also explore the decomposition of Fd, 2n, presenting necessary and sufficient conditions for its decomposition into edge-disjoint standard subgraphs. Furthermore, we present the geometrical interpretation of first six coefficients of its characteristic polynomial. Mixed and directed Hamiltonian Fibonacci graph and its energy are also studied.

Keywords: Fibonacci graph, Hamiltonian cycle, mixed graph, distances in graph, eigenvalues

References:
  1. C. Adiga, N. Anitha and H. C. Savitha, Fibonacci graph and its energies, Adv. Stud. Contemp. Math. 31, 107–122, 2021.
  2. C. Adiga, B. R. Rakshith and W. So, On the mixed adjacency matrix of a mixed graph, Linear Algebra Appl. 495, 223–241, 2016.
  3. D. Anick and M. Ramras, Edge decomposition of hypercube by paths, Australas. J. Combin. 61 (3), 210–226, 2015.
  4. S. Arumugam, I. S. Hamid and V. M. Abraham, Decomposition of graphs into paths and cycles, J. Discrete Math. 2013; Article ID: 721051.
  5. B. Z. Chen and Z. Q. Feng, Recursive backtracking methods for exact Hamiltonian cycle enumeration algorithms, Int. J. Comput. Math. Comput. Syst. Theory 16 (1), 1–18, 2023.
  6. F. R. K. Chung, P. Erdős and J. Spencer, On the decomposition of graphs into complete bipartite subgraphs, In: Studies in Pure Mathematics: To the Memory of Paul Turán, Springer, 1983.
  7. F. H. Clarke, The characteristic polynomial of a graph, McGill University, Montreal, 1970.
  8. J. Cohen, P. Fraigniaud and C. Gavoille, Recognizing Knödal graphs, Discrete Math. 250, 41–62, 2002.
  9. S. Kh. Darbinyan, A survey on sufficient conditions for Hamiltonian cycles in bipartite digraphs, 2016; ArXiv:1604.08733v1.
  10. L. DeBiasio, R. A. Krueger, D. Pritikin and E. Thompson, Hamiltonian cycles in k-partite graphs, J. Graph Theory 94 (1), 92–112, 2020.
  11. K. Fan, Maximum properties and inequalities for the eigenvalues of completely continuous operators, Proc. Natl. Acad. Sci. USA 37, 760–766, 1951.
  12. Z. Gan and Y. Xu, Hamiltonian and long paths in bipartite graphs with connectivity, Discrete Math. 345 (12), 2022; Article ID: 113083.
  13. S. Y. Hsieh, G. H. Chen and C. W. Ho, Hamiltonian-laceability of star graphs, In: Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN’97), Taipei, Taiwan, 1997, pp. 112–117; DOI: 10.1109/ISPAN.1997.645079.
  14. K. Kawarabayashi, A survey on Hamiltonian cycles, Interdiscip. Inf. Sci. 7 (1), 25–39, 2001.
  15. J. Liu and X. Li, Hermitian-adjacency matrices and Hermitian energies of mixed graphs, Linear Algebra Appl. 466, 182–207, 2016.
  16. Y. Liu and J. Wu, Efficient algorithms for detecting Hamiltonian cycles in large-scale graphs, J. Graph Algorithms Appl. 26 (3), 123–138, 2022.
  17. A. R. Meena, M. Y. Lee and S. H. Kim, Backtracking and pruning techniques for Hamiltonian cycles in large-scale graphs, Theor. Comput. Sci. 905, 15–29, 2022.
  18. P. S. Nadar, S. Paulraja and S. Sampath Kumar, Edge disjoint Hamilton cycles in Knödel graphs, Discrete Math. Theor. Comput. Sci. 17 (3), 263–284, 2016.
  19. H. Qiao, J. Meng and E. Sabir, The edge fault-tolerant spanning laceability of the enhanced hypercube networks, J. Supercomput. 79 (6), 6070–6086, 2023.
  20. K. K. Reji and M. Jasmine, On some decomposition problems of Fibonacci graphs, complete bipartite graphs and complete graphs, Math. Sci. Int. Res. J. 6, 39–46, 2017.
  21. R. Sampathkumar and S. Anantharaman, On-proper Hamiltonian-connection number of graphs, TWMS J. Appl. Eng. Math. 12 (3), 1020–1031, 2022.
  22. T. W. Shyu, Decomposition of complete graphs into paths and stars, Discrete Math. 310, 2164–2169, 2010.
  23. P. B. Siva, R. D. George and R. K. Kumar, Backtracking strategies for Hamiltonian path and cycle detection in bioinformatics networks, IEEE/ACM Trans. Comput. Biol. Bioinform. 18 (4), 1123–1135, 2021.
  24. P. Tan, C. Fang and F. Zhou, Analysis of damped outrigger system, In: The 14th International Symposium on Structural Engineering, Beijing, China, Fundamental Research in Structural Engineering: Retrospective and Prospective (Volumes 1 and 2), 2016.
  25. J. M. Xu and M. Ma, Survey on path and cycle embedding in some networks, Front. Math. China 4 (2), 217–252, 2009.
  26. S. Xue, Q. Deng and P. Li, Fault-tolerant strongly Hamiltonian laceability and hyper-Hamiltonian laceability of Cayley graphs generated by transposition trees, Comput. J. 66 (2), 384–398, 2023.

Cite this article

How to cite this article: S. H. Chandregowda and A. N. Murthy, A study of Hamiltonian cycles, decomposition, and mixed, directed forms in the Fibonacci graph Fd,2n, Montes Taurus J. Pure Appl. Math. 8 (1), 29-46, 2026; Article ID: MTJPAM-D-24-00028.