On a relation between randić index and algebraic connectivity

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

9 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)843-849
Journal / PublicationMatch
Volume68
Issue number3
Publication statusPublished - 2012

Abstract

A conjecture of AutoGraphiX on the relation between the Randic index R and the algebraic connectivity a of a connected graph G is: (Equation presented) with equality if and only if G is Pn, which was proposed by Aouchiche et al. [M. Aouchiche, P. Hansen and M. Zheng, Variable neighborhood search for extremal graphs 19: further conjectures and results about the Randić index, Match Commun. Math. Comput. Chem. 58(2007), 83-102.]. We prove that the conjecture holds for all trees and all connected graphs with edge connectivity κ′(G) ≥ 2, and if κ′(G) = 1, the conjecture holds for sufficiently large n. The conjecture also holds for all connected graphs with diameter D ≤ 2(n-3+2√2)/π2 or minimum degree δ ≥ n/2. We also prove R · a ≥ 8√n-1/nD2 and R · a ≥ nδ(2δ-n+2)/2(n-1), and then R · a is minimum for the path if D ≤ (n - 1)1/4 or δ ≥ n/2.

Citation Format(s)

On a relation between randić index and algebraic connectivity. / Li, Xueliang; Shi, Yongtang; Wang, Lusheng.
In: Match, Vol. 68, No. 3, 2012, p. 843-849.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review