Search And Characterization Of Trees With Given Order Or Number Of Leaves Having Minimal ABC Index

The atom-bond connectivity?ABC?index a non-travial simple connected graph G =?V,E?is defined as ???,where V?{v₀,v₁,…,v_n-1} and d?v_i?denotes the degree of vertex vi of G.This topological index has attracted a lot of interest in the last few years,due to its wide applications in chemistry.However,the following two elementary problems remain open.Problem A.Characterize n-vertex tree?s?having ininimal ABC index;Problem B.Characterize trees?s?with k leaves having minimal ABC index?for convenience,k-optimal trees?.Towards these two problems,the research route of repeating the prodedure "Search-Conjecture-Prove" is adopted,in which computer search plays an important role.For Problem A,Furtula et al.carried out a brute-force computer search and found n-vertex tree?s?having minimal ABC index for n?31.Dimitrov implemented a search algorithm based on tree degree sequences,which was tested up to n = 300.Lin et al.improved Dimitrov's algorithm and tested up to n = 400.The current search results all support the "modulo 7 conjecture" modified by Dimitrov.However,this conjecture was shown to be completely false for sufficiently large n by Ahmadi et al.In order to guess the structure of trees having minimal ABC index of large order,a much more efficient search algorithm or implementation is desired.As for Problem B,Magnant et al.claimed that,the balanced double star is the unique k-optimal tree if k?19.Unfortunately,the claim was disproved by the search results up to k?53 by Goubko et al.Analogously,the further investigations of Problem B need the aid of high performance computer search.In the present thesis,we address in search and characterization of n-vertex trees having minimal ABC index and k-optimal trees.The main results are as follows:1.Search and characterizing n-vertex tree?s?having minimal ABC indexObviously,to improve the efficiency of the search algorithm based on optimal tree degree sequences,the key is to extract the features of the degree sequence of a tree having minimal ABC index?for convenience,optimal degree sequence?.Let?=(?=d₀,d₁,…,d_t,d_t+1,…,d_n-1)(d₁?3,d_t+1?2)be an optimal degree sequence,nk the number of k's among {d₁,d₂,…,d_n-1?,???,and bk the number of Bk-or B*k-branches in the greedy tree with degree sequence ?.The known reatures of an optimal degree sequence is refined as follows.?1?n₁ ???n-t-1?/2?,n₂ F??n-t-1?/2?,n₃=b₂?<11,n₄?b₃?2t-49/3.Moreover,n₃=b₂?2 and n₄?b₃??4t-23?/6 if n>18 and n-t-1 is odd.?2??n-11?/7?t??n+13?/5.?3?4???t and ??n/7+3 if n?40.?4?2?+ 5t?n+21.?5?4-77/?n-11??d?5.With these features a search program was implemented with OpenMP.Our program identified all n-vertex tree?s?having minimal ABC index for 300?n?1010 within 38.7 hours on a single PC with 8 CPU cores.2.Search and characterizing k-optimal tree?s??1?Let ?=?d₀,d₁,…,d_t,1_k??d_t?2?denote the degree sequence of a k-optimal tree.We prove that d_t?6 and 1?t???k-6?/4?if k?19.?2?With?1?a search algorithm base on degree sequence was designed.The OpenMP implementation of the algorithm was tested for 19?k?210 on a single PC with 8 CPU cores within 64 hours.?3?Based on the results obtained by Gao et al.,by introducing seme graph transformations we refine?1?as:1?t??k/5?,t?d₀?k-4t,d₁=…= dt???d??31 and dt?+1=…?d_t=?d??6,where d ? + 2 and ?=d-?d?,which implies that a k-optimal tree is uniquely determined by its parameters d₀ and t.?4?From?3?we improve the algorithm presented by Gao et al.A serial implement-ation of our algorithm was tested up to k=20000 within 2.5 hours on a single PC.Overall,in this thesis we study the two elementary problems of charactering extremal graphs with respect to ABC index We obtain some features of the degree sequence both for an n-vertex tree having minimal ABC index and a k-optimal tree,and implement the most efficient search programs.The theoretic and search results indicate the possible directions in further investigations and build up a good basis for the complete solution of the two problems.