Abstract
The augmented Zagreb index (AZI), a variant of the well-known atom-bond connectivity (ABC) index, was shown to have the best predicting ability for a variety of physicochemical properties among several tested vertex-degree-based topological indices. However, contrasting to the extensive research on Problem A: characterizing n -vertex tree(s) with minimal ABC index, few works have been done on Problem B: characterizing n -vertex tree(s) with maximal AZI. Ali and Bhatti conjectured that a tree has maximal AZI iff it has minimal ABC index, with the implication that Problem B is as difficult as Problem A. In this paper, we first prove that among connected graphs with given degree sequence, there exists a breadth-first searching graph maximizing the AZI. Using this, an efficient algorithm based on tree degree sequences is designed to search the n -vertex tree(s) with maximal AZI up to n=200 . We find that the balanced double star uniquely maximizes the AZI for 19\le n\le 200 , and consequently, we disprove the aforementioned conjecture posed by Ali and Bhatti. Naturally, the balanced double star is conjectured to be the unique tree with maximal AZI among n -vertex trees for n\ge 19 . Toward our conjecture, we prove that all the pendent paths are of length 1 in an n -vertex tree with maximal AZI if n\ge 19 .