Search And Characterization Of Trees With Minimal ABC Index

Molecular topological indices have found a wide applications in QSPR/QSAR studies, and they are one of the most active topic of the research in mordern chemical graph theory.In1998Estrada et al. proposed the atom-bond connectivity index (ABC index for short). The ABC index of a graph G=(V,E) is defined as where d(vi) denotes the degree of vertex vi. of G. The ABC index was shown to be well correlated with the heats of formation of alkanes, and that it thus can predict their thermal dynamic properties. Hence it can be used for rationalizing the steric effects and stability of alkanes. In connection with these studies, one needs to know which graphs have extremal ABC indices. Furtula et al. showed that the star is the unique tree with maximal ABC index. However the problem of characterizing n-vertex tree(s) with minimal ABC index (also called minimal-ABC tree(s)) is difficult. One approach to the problem is to repeat the process of "Search-Conjecture-Prove":(1) Search minima1-ABC trees of low order,(2) Conjuture the structural features of minimal-ABC trees,(3) Prove the conjectures proposed,(4) Improve the algorithms by considering the proven structural features, and search minimal-ABC trees of higher order, and try to refine and prove the conjectures,(5) Repeat (4).Gutman et al. presented a brute-force computer searching algorithm. Although the algorithm employed a computer grid with400CPUs, in150days only minimal-ABC trees of order n≤31were found. With the search results, Gutman et al. proposed four conjectures for an w-vertex (n≥10) minimal-ABC tree T:(1) T does not contain pendent path of length k≥2,(2) T does not contain pendent path of length k≥4,(3) T contains at most one pendent path of length k=3,(4) T contains no pendent path of length k=1. Gutman et al. proved the first three conjectures. In this thesis we prove the fourth conjecture. Our result is one of the most important structural features of minimal-ABC trees at the present. Gutman et al. designed an incomplete search algorithm which can search up to n=700, and proposed the "modulo7conjecture" according to the experimental results. However, the modulo7conjecture was proved to be wrong by Ahmadi et al. Dimitrov presented an search algorithm based on tree degree sequences, which can find all minimal-ABC trees of order up to300in about15days on a single processor platform, and the modulo7conjecture was admended. However, Dimitrov’s algorithm does not take full use of the properties of degree sequences of minimal-ABC trees, and his algorithm generates degree sequences recursively, thus can not be paralleled. With the increasing of n, Dimitrov’s algorithm will become not applicable. We prove that the BFS (bread-first searching) tree is a minimal-ABC tree among the trees with given degree sequence. By fully use the properties of degree sequences of minimal-ABC trees, we improved Dimitrov’s algorithm. Our algorithm generates only less than2%tree degree sequences. Its serial implement is4times faster than Dimitrov’s. Moreover, our algorithm can be easily paralleled. Its MPI+OpenMP implement costs only0.21hours to find minimal-ABC trees of order n (30≤n≤300), with an efficiency more than1714times higher than Dimitrov’s. Besides, it finds all minimal-ABC trees of order n (30≤n≤400) in about23hours.In conclusion, we present a most efficient search algorithm and a most important structural feature of minimal-ABC trees. These achievements make good preliminaries to completely solve the problem of characterizing minimal-ABC trees.