A search for the minimum value of Balaban index

M. Knor, J. Kranjc, Riste Škrekovski and Aleksandra Tepeh

Applied Mathematics and Computation, 2016, vol. 286, issue C, 301-310

Abstract: In this paper we consider graphs of order n with minimum Balaban index. Although the index was introduced 30 years ago, its minimum value and corresponding extremal graphs are still unknown, and it is unlikely that they can be precisely determined soon due to the mathematical intractability of the index. We show that this value is of order Θ(n−1). For small values of n we determine the extremal graphs and we observe that they are similar to dumbbell graphs. We find out that in the class of balanced dumbbell graphs those with clique sizes π/24n+o(n) and the path length n−o(n) have asymptotically the smallest value. We study dumbbell-like graphs in more detail, and we propose several conjectures regarding the structure of the extremal graphs.

Keywords: Balaban index; Minimum value of the Balaban index; Dumbbell graphs (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300316302739
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:286:y:2016:i:c:p:301-310

DOI: 10.1016/j.amc.2016.04.023

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().