On a conjecture of randić index and graph radius

Hanyuan Denga, Zikai Tanga, Jie Zhang

Research output: Contribution to journalArticlepeer-review

12 Citations (SciVal)


The Randić index R(G) of a graph G is defined as the sum of (didj)- (formula presented) over all edges vivj of G, where di is the degree of the vertex vi in G. The radius r(G) of a graph G is the minimum graph eccentricity of any graph vertex in G. Fajtlowicz in [S. Fajtlowicz, On conjectures of Graffiti, Discrete Math. 72 (1988) 113-118] conjectures R(G) ≥ r(G) - 1 for any connected graph G. A stronger version, R(G) ≥ r(G), is conjectured for all connected graphs except even paths by Caporossi and Hansen in [G. Caporossi, et al., Variable neighborhood search for extremal graphs 1: The Autographix system, Discrete Math. 212 (2000) 29-44]. In this paper, we make use of Harmonic index H(G), which is defined as the sum of (formula presented) over all edges vivj of G, to show that R(G) ≥ r(G) - (formula presented) (k - 1) for any graph with cyclomatic number k ≥ 1, and R(T) > r(T) + (formula presented) for any tree except even paths. These results improve and strengthen the known results on these conjectures.
Original languageEnglish
Pages (from-to)1369-1375
Number of pages7
Issue number6
Publication statusPublished - 2015

Bibliographical note

Publisher Copyright: © 2015 University of Nis. All Rights Reserved.


  • Graph
  • Harmonic index
  • Radius
  • Randi´c index


Dive into the research topics of 'On a conjecture of randić index and graph radius'. Together they form a unique fingerprint.

Cite this