MMN-662
Remarks on a conjecture about Randić index and graph radius
Abstract
Let G be a nontrivial connected graph. The radius r.G/ of G is the minimum eccent-
ricity among eccentricities of all vertices in G. The Randi ́ index of G is defined as R.G/ D
c
P
P
1
2
p
,
, and the Harmonic index is defined as H.G/ D
d .u/Cd .v/
uv2E.G/
dG .u/dG .v/
uv2E.G/
G
G
where dG .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 gra-
phs 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.
Vol. 14 (2013), No. 3, pp. 845-850
DOI: 10.18514/MMN.2013.662