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

作者：Liu, Jianxi; Liang, Meili^*; Cheng, Bo; Liu, Bolian

来源：Applied Mathematics Letters, 2011, 24(5): 752-756.

DOI：10.1016/j.aml.2010.12.024

• Randic index
• Conjecture
• Diameter

The Randic index R(G) of a graph G is defined by R(G) = Sigma(uv) 1/root 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 Randic index and the diameter: for any connected graph on n > 3 vertices with the Randic index R(G) and the diameter D(G), R(G) - D(G) >= root 2 - n 1/2 and R(G)/D(G) >= n-3 2 root 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) >= root 2 - n 1/2 with equality if and only if G is a path.

• 出版日期2011-5
• 单位Cisco; 广东外语外贸大学; 华南师范大学