A proof for a conjecture on the Randi? index of graphs with diameter

摘要

The Randi? index R(G) of a graph G is defined by R(G)=∑_(uv)1/√d(u)d(v), where d(u) is the degree of a vertex u in G and the summation extends over all edges uv of G. Aouchiche et al. proposed a conjecture on the relationship between the Randi? index and the diameter: for any connected graph on n<3 vertices with the Randi? index R(G) and the diameter D(G), R(G)-D(G)≤ √2-n+12and R(G)D(G)≤n-3+2√2/2n-2, with equalities if and only if G is a path. In this work, we show that this conjecture is true for trees. Furthermore, we prove that for any connected graph on n<3 vertices with the Randi? index R(G) and the diameter D(G), R(G)-D(G)≤2-n+1/2, with equality if and only if G is a path.