Searching Algorithm of Greedy Chemical Trees with Minimal Atom-bond Connectivity Index

Abstract

This paper conducted a cross research on computer programming and combinatorial mathematics which studied the minimal Atom-bond connectivity (ABC) index of chemical trees using the greedy algorithm and the theory of integer partitioning. A completed searching algorithm that counting chemical trees with minimal ABC index, fast searching algorithm and their specific value of efficiency are given. We also found the pattern of variation of the (ABC) index of graphs with n (n<500) vertices as the degree sequences changes, and we obtained the lower bound of the ABC index of chemical trees and one of its corresponding extremal graphs. Furthermore, we proposed a conjecture of degree sequence and extremal graph. These provide a new way to search the minimal ABC index of trees. Chinese Library Classification: TQ015.3, TP301.6 Document code: A