REMARKS ON A CONJECTURE ABOUT RANDIC INDEX AND GRAPH RADIUS

چکیده مقاله

Let G be a nontrivial connected graph. The radius of G is the minimum eccentricity among eccentricities of all vertices in G. The Randic index of G is defined as Let G be a nontrivial connected graph. The radius r.G/ of G is the minimum eccentricity among eccentricities of all vertices in G. The Randi c index of G is defined as R.G/ D Puv2E.G/1pdG.u/dG.v/, and the Harmonic index is defined as H.G/ DPuv2E.G/2dG.u/CdG.v/where dG.x/ is the degree of the vertex x in G. In 1988, Fajtlowicz conjectured that for anyconnected graph G, . This conjecture remains still open so far. More recently,Deng et al. proved that this conjecture is true for connected graphs with cyclomatic number nomore than 4 by means of Harmonic index. In this short paper, we use a class of composite graphs to construct infinite classes of connected graphs, with cyclomatic number greater than 4, forwhich the above conjecture holds. In particular, for any given positive odd number k > 7, we construct a connected graph with cyclomatic number k such that the above conjecture holds for this graph. where d(G).x/ is the degree of the vertex x in G. In 1988, Fajtlowicz conjectured that for any connected graph G, R(G) > r(G) + 1. This conjecture remains still open so far. More recently,Deng et al. proved that this conjecture is true for connected graphs with cyclomatic number no more than 4 by means of Harmonic index. In this short paper, we use a class of composite graphs to construct infinite classes of connected graphs, with cyclomatic number greater than 4, for which the above conjecture holds. In particular, for any given positive odd number k > 7, we construct a connected graph with cyclomatic number k such that the above conjecture holds for this graph.