The NP-hard problem of determining the number of spanning trees of graphs is examined in this paper. A spanning tree of a graph G is a tree such that (i) it is a subgraph of G (i.e., that includes only edges from G), and (ii) it includes every vertex of G. The most classical interest concerning a spanning tree is the number of spanning trees or the complexity of the graph G denoted by  We propose the first attempt to use a binary version of the fruit fly optimization algorithm (BFFOA) to compute the minimal spanning tree of a graph in a heuristic manner. The fruit fly of BFFOA is binary encoded and used to represent which one of the vertices of the graph belongs to the spanning tree of G. The feasibility is enforced by repairing the fruit fly such that an extra vertex created from vertices of G is added to B, and this repairing process is repeated until B becomes the spanning tree of G. Theoretically computed graph results are used to compare the proposed BFFOA against competing techniques. The proposed BFFOA performs better than the binary Grey Wolf Optimizer (BGWO), the binary Particle Swarm Optimizer (BPSO), the binary Whale Optimizer (BWO), and the binary Multi-verse Optimization (BMVO) algorithms, according to analysis and computational results.

spanning trees, fruit fly optimization algorithm, binary optimization

Received: July 15, 2024; Revised: July 18, 2024; Accepted: September 19, 2024; Published: October 19, 2024

How to cite this article: Ahmad Asiri and Basma Mohamed, Binary fruit fly optimization algorithm for counting the number of spanning trees in networks, Advances and Applications in Discrete Mathematics 41(8) (2024), 663-676. https://doi.org/10.17654/0974165824042

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:
[1] G. Kirchhoff, Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird, Annalen der Physik 148(12) (1847), 497-508.
[2] A. K. Kelmans and V. M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees, Journal of Combinatorial Theory Series B 16(3) (1974), 197-214.
[3] G. A. Cayley, A theorem on trees, Quarterly Journal of Mathematics 23 (1889), 276-378.
[4] K. C. Das, A. S. Cevik and I. N. Cangul, The number of spanning trees of a graph, Journal of Inequalities and Applications (2013), 1-13.
[5] S. N. Daoud, On the complexity of a class of pyramid graphs and Chebyshev polynomials, Mathematical Problems in Engineering (2013), 1-11.
[6] S. D. Nikolopoulos and C. Papadopoulos, On the number of spanning trees of graphs, Discrete Mathematics and Theoretical Computer Science 8 (2006), 235-248.
[7] J. B. Liu, J. Zhao and Z. Zhu, On the number of spanning trees and normalized Laplacian of linear octagonal‐quadrilateral networks, International Journal of Quantum Chemistry 119(17) (2019), e25971.
[8] J. B. Liu, T. Zhang, Y. Wang and W. Lin, The Kirchhoff index and spanning trees of Möbius/cylinder octagonal chain, Discrete Applied Mathematics 307 (2022), 22-31.
[9] B. Mohamed and M. Amin, Enumeration of the number of spanning trees of the globe network and its subdivision, International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks, (GRAPH-HOC) 15(3) (2023), 1-7.
[10] S. N. Daoud, Complexity of products of with some special graphs, Elixir Discrete Mathematics 74 (2014), 27137-27150.
[11] G. Wang and F. Zhu, Counting spanning trees of generalized n-edges Apollonian networks, International Journal of Modern Physics C (2023), 2350119.
[12] F. Bencs and P. Csikvári, Upper bound for the number of spanning forests of regular graphs, European Journal of Combinatorics 110 (2023), 103677.
[13] B. Mohamed and M. Amin, Complexity of some types of cyclic snake graphs, Mathematical Modeling and Applications 9(1) (2024), 14-22.
[14] B. Mohamed and M. Badawy, Some new results on domination and independent dominating set of some graphs, Applied and Computational Mathematics 13(3) (2024), 53-57.
[15] B. Mohamed, A comprehensive survey on the metric dimension problem of graphs and its types, International Journal of Theoretical and Applied Mathematics 9(1) (2023), 1-5.
[16] B. Mohamed and M. Amin, A hybrid optimization algorithms for solving metric dimension problem, International Journal on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks 15(1) (2023), 1-10.
[17] B. Mohamed and M. Amin, Hybridizing slime mould algorithm with simulated annealing for solving metric dimension problem, Machine Learning Research 8(1) (2023), 9-16.
[18] B. Mohamed and M. Amin, The metric dimension of subdivisions of Lilly graph, tadpole graph and special trees, Applied and Computational Mathematics 12(1) (2023), 9-14.
[19] W. T. Pan, A new fruit fly optimization algorithm: Taking the financial distress model as an example, Knowledge-Based Systems 26 (2012), 69-74.