Characterizing Trees with Minimal ABC Index with Computer Search: A Short Survey
ODAM-Vol. 1 (2018), Issue 2, pp. 01–09 | Open Access Full-Text PDF
Yiming Zheng, Wenshui Lin, Qi’an Chen, Linshan Huang, Zhixi Wu
Abstract:The atom-bond connectivity (ABC) index of a graph \(G=(V,E)\) is defined as \(ABC(G)=\sum_{v _{i}v_{j} \in E}\sqrt{(d_{i}+d_{j}-2)/(d_{i}d_{j})}\), where \(d_{i}\) denotes the degree of vertex \(v_{i}\) of \(G\). Due to its interesting applications in chemistry, this molecular structure descriptor has become one of the most actively studied vertex-degree-based graph invariants. Many efforts were made towards the elementary problem of characterizing tree(s) with minimal ABC index, which remains open and was coined as the ABC index conundrum”. Up to date, quite a few significant results have been obtained. In the course of research computer search plays a non-negligible role. In the present paper we review the state of the art of the problem. In addition we intend to demonstrate that, repeating the procedure “searching – conjecturing – proving” can be an applicable paradigm to cope with elusive problems of extremal graph characterization.