On the Trees With Maximal Augmented Zagreb Index

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 breadthfirst 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 ≤ n ≤ 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 ≥ 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 ≥ 19.

Keywords

• Augmented Zagreb index
• extremal graphs
• topological indices
• trees