On a Conjecture of Randić Index and Graph Radius

Original · EN

The Randić index R(G) of a graph G is defined as the sum of (dᵢ dⱼ)⁻¹/² over all edges vᵢ vⱼ of G, where dᵢ is the degree of the vertex vᵢ in G. The radius r(G) of a graph G is the minimum graph eccentricity of any graph vertex in G. Fajtlowicz(1988) conjectures R(G) ≥ r(G)-1 for all connected graph G. A stronger version, R(G) ≥ r(G), is conjectured by Caporossi and Hansen(2000) for all connected graphs except even paths. In this paper, we make use of Harmonic index H(G), which is defined as the sum of 2/dᵢ+dⱼ over all edges vᵢ vⱼ of G, to show that R(G) ≥ r(G)-31/105(k-1) for any graph with cyclomatic number k≥ 1, and R(T)> r(T)+1/15 for any tree except even paths. These results improve and strengthen the known results on these conjectures.