IMFM
Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA
Preprint series Vol. 48 (2010), 1118
ISSN 2232-2094
RANDIC INDEX AND THE DIAMETER OF A GRAPH
Zdenek Dvorak Bernard Lidicky Riste Skrekovski
Ljubljana, April 9, 2010
•rh $h
a <
00
o
Randic index and the diameter of a graph*
Zdenek Dvorak Bernard Lidicky^ Riste Skrekovski-
Abstract
The Randic index R(G) of a nontrivial connected graph G is defined as the sum of the weights (d(u)d(v))-2 over all edges e = uv of G. We prove that R(G) > d(G)/2, where d(G) is the diameter of G. This immediately implies that R(G) > r(G)/2, which is the closest result to the well-known Grafiti conjecture R(G) > r(G) — 1 of Fajtlowicz [4], where r(G) is the radius of G. Asymptotically, our result approaches the bound RG) > n-23n+22/^ conjectured by Aouchiche, Hansen and Zheng [1].
1 Introduction
£ CO
All the graphs considered in this paper are simple undirected ones. The CO	eccentricity of a vertex v of a graph G is the greatest distance from v to any
other vertex of G. The radius (resp. diameter) of a graph is the minimum (resp. maximum) over eccentricities of all vertices of the graph. The radius and diameter will be denoted by r(G) and d(G), respectively.
*	Supported by the CZ-SL bilateral project MEB 090805 and BI-CZ/08-09-005.
t Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles ^	University, Malostranske namestl 25, 118 00 Prague, Czech Republic. E-mail:
rakdver@kam.mff.cuni.cz. Supported by Institute for Theoretical Computer Science CD	(ITI), project 1M0545 of Ministry of Education of Czech Republic.
*	Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranske namestl 25, 118 00 Prague, Czech Republic. E-mail: bernard@kam.mff.cuni.cz.
§ Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia. Partially supported by Ministry of Science and Technology of Slovenia, Research Program P1-0297. E-mail: skrekovski@gmail.com.
j-i
There are many different kinds of chemical indices. Some of them are distance based indices like Wiener index, some are degree based indices like RandiC index. The Randic index R(G) of a graph G is defined as
r(G)= y , 1 —.
.. ydeg(«) deg(w)
00
c
r
£ CO
CO
uveE(G)
It is also known as connectivity index or branching index. Randic [11] in 1975 proposed this index for measuring the extent of branching of the carbon-atom skeleton of saturated hydrocarbons. There is also a good correlation between Randic index and several physicochemical properties of alkanes: boiling points, surface areas, energy levels, etc. In 1998 Bollobas and Erdos [2] generalized this index by replacing the square-root by power of any real number, which is called the general Randic index. For a comprehensive survey of its mathematical properties, see the book of Li and Gutman [7], or recent survey of Li and Shi [10]. See also the books of Kier and Hall [5, 6] for chemical properties of this index.
There are several conjectures linking Randic index to other graph parameters. Fajtlowicz [4] posed the following problem:
co
Conjecture 1. For every connected graph G, it holds R(G) > r(G) — 1.
Caporossi and Hansen [3] showed that R(T) > r(T) + \/2 — 3/2 for all trees T. Liu and Gutman [9] verified the conjecture for unicyclic graphs, bicyclic graphs and chemical graphs with cyclomatic number c(G) < 5. You and Liu [12] proved that the conjecture is true for biregular graphs, tricyclic graphs and connected graphs of order n < 10.
Regarding the diameter, Aouchiche, Hansen and Zheng [1] conjectured the following:
Conjecture 2. Any connected graph G of order n > 3 .satisfies
*	R(G) — d(G) > — n±i ani RG > n — 3 +
2	d(G) - 2n — 2
Jh
with equalities if and only if G is a path on n vertices.
Li and Shi [8] proved the first inequality for graphs of minimum degree at least 5. They also proved the second inequality for graphs on n > 15 vertices
with minimum degree at least n/5.
ft
cd
CO CD
■ i-h
The Randic index turns out to be quite difficult parameter to work with. Also, Conjecture 1 is quite weak for graphs with small radius; for instance, R(Kln) = \fn, while r(K\n) = 1 for all n. Instead, we work with a different parameter R(G) defined by
R (G)	max(deg(u), deg(v))
uveE(G)	v 6V h 6V "
1—1
Note that R(G) > R'(G) for every graph G, with the equality achieved only if every connected component of G is regular. The main result of this paper is the following:
o
Theorem 3. For any connected graph G, R'(G) > d(G)/2.
Since R(G) > R'(G) and d(G) > r(G), by our theorem, we immediately obtain that R(G) > r(G)/2. This result supports Conjecture 1. Our result solves asymptotically the second claim of Conjecture 2. Let us remark that the bound of Theorem 3 is sharp, with the equality achieved for example by paths of length at least two. Since Conjecture 2 is also tight for paths, in order to prove Conjecture 2 using our technique, it would be necessary to consider the gap R(G) - R'(G).
2 Proof of the main theorem
We prove the theorem by contradiction. In the rest of the paper, assume that G is a connected graph such that R'(G) < d(G)/2 and G has the smallest number of edges among the graphs with this property, i.e., R(H) > d(H)/2 for every connected graph H with \E(H)| < \E(G)|. Let n = \V(G)|. For an edge uv, a weight of uv is —u—t^—7-tt.
°	'	J	max(deg(u) , deg(v))
If d(G) = 0, then G = K and R'(G) = 0 = d(G)/2. If 1 < d(G) < 2, then G has at least one edge; observe that the sum of the weights of the edges incident with the vertex of G of maximum degree is one, thus R'(G) > 1 > d(G)/2. Therefore, d(G) > 3.
For two vertices x and y of a graph H, let dH(x,y) denote the distance between x and y in H.
Lemma 4. If v is a cut-vertex in G, then all components of G — v except for one consist of a single vertex.
a
CD
u
a <
Proof. Assume for a contradiction that G — v has two components with more than one vertex. Then, there exist induced subgraphs G1,G2 C G such that Gi U G2 = G, V(Gi) H V(G2) = {v} and Gi — v has a component with more than one vertex, for i e {1, 2}.
For i e {1, 2}, let Gi be the graph obtained from Gi by adding degGa_. (v) pendant vertices adjacent to v and let vi be one of these new vertices. Observe that R'(G'1) + R'(G'2) = R'(G) + 1. Furthermore, consider any two vertices x,y e V(G). If x,y e V(G1), then dG(x,y) = dG/ (x,y) < d(G[) < d(G'i) + d(G') — 2. By symmetry, if x,y e V(G2), then dG(x,y) < d(G/1) + d(G'2) — 2. Finally, if say x e V(G1) and y e V(G2), then dG(x,y) = dGl(x,v) + dG2 (y, v) = dGi (x,v1) — 1 + dG> (y, v2) — 1 < d(G/) + d(G') — 2. We conclude
that d(G) < d(G1) + d(G'2) — 2.
Since both G'1 and G' have fewer edges than G, the minimality of G implies that
o

cd co
u
a
CD U
d(G1) , d(G') ^ d(G)
R'(G) = R'(G1) + R'(G') — 1	+ — 1 > 2
C^	222
which contradicts the assumption that G is a counterexample to Theorem 3.
□
(N
A vertex v is locally minimal if its degree is smaller or equal to the degrees of its neighbors.
Lemma 5. Let v e V(G) be a locally minimal vertex. Then deg(v) = 1, the
CO
neighbor of v has degree at least three and d(G — v) = d(G) — 1.
Proof. Suppose first that deg(v) > 1. Let w be a neighbor of v and k the number of neigbors of w distinct from v whose degree is smaller than deg(w). Note that k < deg(w) — 1. We have
R (G vw) R (G) deg(w) + k (deg(w) — 1 deg(w))
= r'(g) — +	k
deg(w) deg(w)(deg(w) — 1)
< R'(G).
Since v is locally minimal, every neighbor of v has degree at least deg(v) > 2, thus by Lemma 4, v is not a cut-vertex. It follows that G - vw is connected,
u
a <
hence d(G — vw) > d(G). By the minimality of G, we obtain R'(G) > R'(G — vw) > d(G — vw)/2 > d(G)/2, which is a contradiction.
Let us now consider the case that deg(v) = 1. Then d(G — v)/2 < R'(G — v) < R'(G) < d(G)/2, and thus d(G — v) < d(G). Removing the pendant vertex v cannot decrease the diameter by more than one, thus d(G — v) = d(G) — 1. Since d(G) > 3, the neighbor w of v has degree at least two, and if deg(w) = 2, then v is the only neighbor of w of degree smaller than deg(w). It follows that if deg(w) = 2, then R'(G — v) = R'(G) — 1/2. We conclude that R'(G) = R'(G — v) + 1/2 > d(G — v)/2 + 1/2 = d(G)/2, which is a contradiction. This implies that deg(w) > 3.	□
•
Let L be the set of vertices of G of degree one. Note that a vertex of G of the smallest degree is locally minimal, thus by Lemma 5, L = 0.
Lemma 6. If the distance between two vertices u and v in G is d(G), then L C {u,v}.
o
Proof. Suppose that there exists a vertex w E L \ {u,v}. Then w is locally minimal and d(G — w) = d(G), contradicting Lemma 5.	□
Lemma 6 implies that \L\ < 2. Lemma 5 shows that all vertices of degree d > 1 are incident with an edge whose weight is 1/d; thus, if many vertices have small degree, then these edges contribute a lot to R'(G). On the other hand, if many vertices have large degree, then G has many edges and R'(G) is large. Let us now formalize this intuition.
CSI CSI
CO
Lemma 7. d(G) > \J8(n — 3) — 1, and thus n <
d2 (G)+2d(G) 8
3.
Proof. Let di > d2 > ... > dn be the degree sequence of G. For 1 < i < n, let vi be the vertex of G of degree di. For each i > 1, the sum of the weights of the edges incident with vi, but not incident with vj for any j < i, is at least 1 — (i — 1)/di. We conclude that the edges incident with the vertices v1, v2, ..., vt contribute at least t — YIt=1 — > t — ^td1 to R'(G). Let to be the largest integer such that dt0 > t0 — 1; thus, for each i > t0, di < dt0+1 < (t0 + 1) — 1 = t0. Then the sum of the weights of the edges incident with the vertices v1, v2, ..., vt0 is at least t0 —	= t0.
By Lemma 5, any vertex v E L has a neighbor s(v) with strictly smaller degree. Let X = {vis(vi)\i > t0 + 1,vi E L}. Note that the edges in X are pairwise distinct, thus \X \>n — t0 — 2. None of the edges in X is incident
a
•rh $h
a <
00
0 o
1
00 ^
CO CO
co CD
$h
CD co
$h
a
CD Jh
with the vertices v^ ..., vt0, hence each of them has weight at least to—i, and
R'(G) > ! +
1

t0 — 1 n — 3
= ---1--
2 t0 — 1 2
> V2(n — 3) — 2,
where the last inequality holds since x + y > 2^/xy for all x,y > 0. As G is a counterexample to Theorem 3, d(G) > 2R'(G) > \J8(n — 3) — 1. This is equivalent to d2(G) + 2d(G) + 1 > 8(n — 3). Since both sides of this inequality are integers, d2(G) + 2d(G) > 8(n — 3), and thus
n
d2(G) + 2d(G)
+ 3.
□
Let w be a neigbor of a vertex of degree one. By Lemma 5, w has degree at least three, and since d(G) > 3, at least one vertex of G is not adjacent to w. We conclude that n > 5, and by Lemma 7, d(G) > 3. Lemma 5 also implies that the vertices of G of small degree must be close to L:
Lemma 8. If the distance of a vertex v from L is at least k > 0, then deg(v) > k + 2.
Proof. By Lemma 5, each vertex not in L has a neighbor of strictly smaller degree, thus there exists a path P from v to L such that the degrees on P are decreasing. Also, the vertex in P that has a neighbor in L has degree at least three. Since P has length at least k, we have deg(v) > 3+£(P) —1 > k+2. □
Choose a vertex v0 E L, and for each integer i, let Li be the set of vertices of G at the distance i from v0, as illustrated in Figure 1. Let 5i be the minimum and Ai the maximum degree of a vertex in Li, and let ni = |Li|. Observe that n0 = n1 = 1, nd(G) > 1 and n = 1==0 ni. Furthermore, by Lemma 6, if ILI > 1 then nd(G) = 1 and L = L0 U Ld(G).
For an integer i, let i = min(i, d(G) —i). Note that the distance between L and Li is at least i. By Lemma 8, we have Ai > 5i > i+2 for 1 < i < d(G) — 1.
8
•rh $h
a <
00
Lo
Li
Lo
La
L
d-1
Ld
0 o
1
CO
£ CO CO
co cd
$h
CD co
$h
a
CD U
Figure 1: A graph G with vertices partitioned into layers L0,L1,...,Ld.
Also, since all neighbors of a vertex in Li belong to Li_1 U Li U Li+1, it follows that Ai < ni_1 + ni + ni+1 — 1, and thus ni_1 + ni + ni+1 > i + 3.
By Lemma 4, n > 2 for 2 < i < d(G) — 2, and thus n > 2d(G) — 2. Together with Lemma 7, we obtain
2d(G) — 2 < n < d2(G' + 2d'G>+3.
8
which implies d(G) < 4 or d(G) > 10. If d(G) = 4, then n1 + n2 + n3 > 2 + 3 = 5, and thus n > 7 > d (G)+2d(G) + 3. This contradicts Lemma 7, hence d(G) > 10.
Let us now derive some formulas dealing with i that we later use to estimate the sizes of the layers Li.
Lemma 9. The following holds:
(a)
d(G) £ i >
d2(G) — 1
i=0
(b)
d(G)
>
i=o
t2 . d3(G) — d(G)
12
Proof. We use the well-known formulas i=0 i = ( + ) and i=0 i2 = fc(fc+1)(2fc+1) 6 .
4
•rh $h
a <
00
0 o
1
00 ^
CO CO
co CD
$h
CD co
$h
a
CD Jh
If d(G) is odd, then
and
d(G) (d(G)~1)/2 d2 (G) 1 y?=2 y i = ^^
i=0 i=0
_ ^G-^ 2 _ d3(G) — d(G)
/ i - 2 / i - _ .
Z^	Z^	12
i=0 i=0
If d(G) is even, then
d(G)
d(G)
y i
i=0
d(G)/2 ^ d^G) d2(G) — 1
2 ^ i =4 > 4
i=0
and
d(G) i=0
d2(G)
d(G)/2-1
2
£
i=0
2 _ d3(G) + 2d(G) ^ d3(G) — d(G)
12
12
□
Let Ri be the sum of the weights of the edges induced by Li plus half of the weights of the edges joining vertices of Li with vertices of Li-1 and Li+1. Observe that R'(G) = ^2^0 Ri. Also, the weight of each edge incident
with a vertex of Li is at least
max(Ai_i,Ai,Ai+i)
Let si = ni-1 + ni + ni+1 and Wi =-"i(i+2)
, thus Ri >
UiSi
2 max(A—i,Ai,Ai+i)' ,	x . Since Ai < si — 1 and
Si > i + 2 for 1 < i < d(G) — 1, we have Ri > W/2 for 2 < i < d(G) — 2. Note also that si > Si + 1 > i + 3 for 1 < i < d(G) — 1.
We can now show that it suffices to consider graphs of small diameter.
Lemma 10. The diameter of G is at most 35.
Proof. Suppose that 3 < i < d(G) — 3. Let
Xi =
s$ + 1)
max(si-2, s—1, si, si+1, si+2) — 1'
Observe that Wi-1 + Wi + Wi+1 > Xi. Let
Mi = si-2 + si_1 + 2 si + si+1 + si+2 + aXi
2
4
1
where a > 0 is a constant to be chosen later. Let j E {i — 2,...,i + 2} be the index such that sj = max(si_2, si_1, 8-i, si+1, si+2).
Recall that si > i + 3, and thus si_2, si+2 > i +1 and si_1, si+1 > i + 2. If j = i, then —---^-r > 1, and thus
J	'	max(s o.s i .s.s-i i .s i o)—I	'
U
D <
00
J '	max(sj_2 Si-1 Si ,«i+1 ,Si+2)_1
Mi > 6i +12 + a(i + 1) > (6 + a)i +12 + a.	(1)
On the other hand, if j = i, then
(i + 1)(i + 3)
o
u
a
cd U
Mi > 5i +11 + (sj — 1) + a
sj — 1
>	5i + 11 + 2^ a(i + 1)(i +3)
>	5i +11 + 2Va(i +1)
= (5 + 2^a)i +11 + 2^a.	(2)
The expression (2) is smaller or equal to (1), giving the lower bound for Mi.
For m E {0,1, 2}, let Bm be the set of integers between 3 and d(G) — 3 (inclusive) whose remainder modulo 3 is m, and bm = max Bm. Let
co
S = 4n o + 2m + 2nd(G)_1 + 4nd(G) + s1 + s2 + sd(G)_2 + sd(G)_1.
Notice that S > 30. On one hand, we have Xi < Wi_1 + Wi + Wi+1 < 2(Ri_1 + Ri + Ri+1), and thus
CO
bm	bm + 1
si
ieBm	i=3+m	i=2+m
d(G)_1
Mi < s1+m + s2+m + sbm+1 + sbm+2 + 2 ^ 'Si + 2a Ri
<	—S + 4n o + 2n1 + 2nd(G)_1 + 4nd(G) + 2 si + 2aJ^Ri
i=1 i>0
= —S + 6n + 2aR'(G)
<	— 30 + 6n + ad(G).
cd
On the other hand,
CD
J^Mi > J2 {(5 + 2Va)i + 11 + 2^)
ieBm
(11 + 2^a)\Bm\ + (5 +	i.
ieB	ieB m
ie Bm
00
£
CO CO
Summing the two inequalities above over the three choices of m, we obtain
d(G)-3
(11 + 2^a)(d(G) — 5) + (5 + 2^a) V i< 18n + 3ad(G) — 90.
a <
i=3
Applying Lemma 9(a), we obtain ^<di^) 3 i > d (G) 25, and thus
(11 + 2Vo)(d(G) — 5) + (5 + 2^a)d G) — 25 < 18n + 3ad(G) — 90
(5 + 2^a)d2(G) +4(11 + 2 ^ — 3a)d(G) < 72n + 90^a — 15.
fi 2
By Lemma 7, n < d (G)+2d(G) + 3, and thus
(5 + 2\fa)d2(G) + 4(11 + 2\fa — 3a)d(G) < 9(d'(G) + 2d(G)) + 90^/a + 201 (2y/a — 4)d'(G) + (26 + 8\fa — 12a)d(G) < 90\/a + 201.
00
Setting a = 10, this implies that d(G) < 35.5, and since d(G) is an integer, the claim of the lemma follows.	□
Lemma 8 gives a lower bound for the minimum degrees 5i in the layers Li, which can in turn be used to bound the size of the layers and consequently the number of vertices of G. The lower bound on n obtained in this way is approximately d'(G)/12, and thus it does not directly give a contradiction with Lemma 7. However, the following lemma shows that this lower bound on n can be increased if the maximum degree of G is large (let us note that A(G) > 5 ld(G)/2\ > l_d(G)/2j +2). Together with Lemma 7, this can be used to bound A(G).
Lemma 11. The following holds: n > (A(G) — [d(G)/2j—2) + d (G)+1'd(G)+3.
Proof. Let j be an index such that a vertex of the degree A(G) lies in Lj, and let B be the set of integers i such that 1 < i < d(G) — 1 and 31i — j. Let a = min B — 1 and b = max B + 1. Observe that
a—1	d(G)
n = ^2 si + ni + JZ ni.
ieB	i=0	i=b+1
u
a
cd
For i E B, we have that si > 5i +1 > i + 3. Furthermore, if j < d(G), then Sj > A(G) + 1 > (j + 3) + (A(G) — |_d(G)/2j — 2), and if j = d(G), then b = d(G) — 2 and nd(G)-1 + nd{G) > A(G) + 1 > 2 + (A(G) — Ld(G)/2j — 2). Also, i > (i — 1 + i + i + 1)/3. Using Lemma 9(a), we conclude that
ft
b n \
n > A(G) — Ld(G)/2j — 2 + ^ I 3 + 1j + a + (d(G) — b)
i=a ^	'
d(G) -r
> A(G) — Ld(G)/2j — 8/3 + £ + 1)
Jh
cd
m
i=0
<2	> A(G) ~\d(G)l2J— 5/3 + d(G) +	^
*	= (A(G) — Ld(G)/2J — 2) + d2<G) + 1122d(G> + 3.
Next, we show that the maximum degree of G is large. This, combined with the previous lemma, will give us a contradiction.
00
Lemma 12. Let k = [d(G)/2], and let d1 > d2 > ... > dn be the degree
CO
Proof. For 1 < i < n, let vi be the vertex of G of degree di. Let ki be the number of neighbors of vi in {vj\j > i}. Note that Yn=1 ki = \E(G)\ = 1 C=1 di, R'(G) = Y,n=1 | and 0 < ki < di.
Let m be the index such that there exists a sequence x1, x2, ..., xn satisfying
• xi = di for 1 < i < m — 1,
sequence of G. Then Y!k=1 di > d (G)+12d (G0+35d(G)+288, and thus A(G) >
d3(G)+12d2(G)+35d(G)+288 72k
• 0 < xm < dm,
xi = 0 for m +1 < i < n, and En=1 xi = \E (G)\.
Jh
a
CD
csi
Since f + d > ^br + — when b > d, we conclude that
^ d-G >#(G) = £ d > £ X > m _ 1,
2 i=1 di i=1 di
i.e., m < |"d(G)/2]. Furthermore, ^ di > 1 + ^ x = 1 + \E(G)|. Let ti = ni-15i-1 + ni5i + ni+15i+1. Note that
o
CSI
i
c^
ti > ni-1(i _ 1 + 2) + ni(i + 2) + ni+1(i +1 + 2) > si(i + 1)
for 2 < i < d(G)_2. Also, t2 > s2(2+1)+n2 and td(G— > sd(G—2(d(G) _ 2+ 1) + nd(G)-2. Using Lemma 9(b), we obtain
d(G)
6\E (G)\ > 3^ nA
i=0
d(G)-2
35ono + 35d(G)nd(G) + + 25d(G)-1nd(G)-1 + + §d(G)-2nd(G)-2 + ^ ti cn	i=2
d(G)-2
>	3(no + nd(G)) + 6(n1 + nd(G)-1) + 5(n + nd(G-) + ^ Si(i + 1)
i=2
d(G)-2
si
i=2 d(G)-2
>	38+ J] (i + 3)(i + 1)
i=2
d3(G) + 12d2(G) + 35d(G) + 216
>	12 '
It follows that
&
> d3(G) + 12d2(G) + 35d(G) + 288
> 38 + Si(i + 1)
CO
72
cd
i=1
Since k > m, the lemma holds.	□
We are now ready to finish the proof.
Jh
a
CD
•rh $h
a <
00
0 o
1
00 ^
CO CO
d(G)	LBd(G)	UBd(G)	d(G)	LBd(G)	UBd(G)
10	8	6	23	23	19
11	8	5	24	26	22
12	10	7	25	26	23
13	10	7	26	29	26
14	12	9	27	30	27
15	12	9	28	33	30
16	14	11	29	34	31
17	15	11	30	37	34
18	17	13	31	38	35
19	17	13	32	41	39
20	20	16	33	42	41
21	20	17	34	45	44
22	23	19	35	46	45
Table 1: Values of the lower bound LBd(G) and the upper bound UBd(G) for A(G) from proof of Theorem 3.
Proof of Theorem 3. By Lemma 10, the diameter of the minimal counterexample G is at most 35. Also, as we observed before, d(G) > 10. Lemmas 7 and 11 imply that
A(G) < |_d(G)/2j + 5
d2(G) + 2d(G)

d2(G) + 12d(G) + 3 12
We denote this upper bound on A(G) by UBd(G). Lemma 12 gives a lower bound on A(G), which we denote by LBd(G). For 10 < d(G) < 35, it holds that UBd(G) < LBd(G), which is a contradiction. See Table 1 for values of
LBd(G) and UBd(G).	□
co CD
CD co
u
a
CD U
References
[1] M. Aouchiche, P. Hansen and M. Zheng, Variable neighborhood search for extremal graphs. 19. Further conjectures and results about the Randic index, MATCH Commun. Math. Comput. Chem. 58 (2007), 83102.
8
•rh $h
a <
00
0 o
1
CO ^
CO CO
m
cd
$h
CD
m
[2]	B. Bollobas and P. Erdos, Graphs of extremal weights, Ars Combin. 50 (1998), 225-233.
[3]	G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs 1: The AutographiX system, Discrete Math. 212 (2000), 29-44.
[4]	S. Fajtlowicz, On conjectures of Graffiti, Discrete Math. 72 (1988), 113118.
[5]	L. B. Kier and L. H. Hall, Molecular Connectivity in Chemistry and Drug Research, Academic Press, New York, 1976.
[6]	L. B. Kier and L. H. Hall, Molecular Connectivity in structure-Activity Analysis, Research Studies Press-Wiley, Chichester(UK), 1986.
[7]	X. Li and I. Gutman, Mathematical Aspects of Randic - Type Molecular Structure Descriptors, Mathematical Chemistry Monographs No.1, Kragujevac, 2006.
[8]	X. Li and Y. Shi, On the Randic index and the diameter, the average distance, manuscript, 2009.
[9]	B. Liu and I. Gutman, On a conjecture on Randic indices, MATCH Commun. Math. Comput. Chem. 62 (2009), 143-154.
[10]	X. Li and Y. Shi, A survey on the Randic index, MATCH Commun. Math. Comput. Chem. 59 (2008), 127-156.
[11]	M. Randic, On characterization of molecular branching, J. Amer. Chem. Soc. 97 (1975), 6609-6615.
[12]	Z. You and B. Liu, On a conjecture of the Randic index, Discrete Appl. Math. 157 (2009), 1766-1772.
U
a
CD U