THE K-CONNECTIVITY INDEX OF AN INfiNITE CLASS OFDENDRIMER NANOSTARS
WEIQING WANG, XINMIN HOU*
Let G be a simple connected graph of order n. In 1975, Randic [10] introduced the connectivity index (now called also Randic index) as ,where uv runs over all edges of G. This index has been successfully related to chemical properties, namely if G is the molecular graph of an alkane, then1χ(G) has a strong correlation with the boiling point and the stability of the compound [8, 9, 12].
The k-connectivity index of an organic molecule whose molecule graph is G is defined , WENJIE NING
Department of Mathematics, University of Science and Technology of China, Hefei 230026, P.R.China
The k-connectivity index kχ(G) of a molecular graph G is the sum of the weights (dv1dv2···dvk+1)-1/2, where v1v2···vk+1runs over all paths of length k in G and dvi denotes the degree of vertex vi. In this paper, we give the explicitly formula of the k-connectivity index of a infinite class of dendrimer s, which generalized Ahmadiand Sadeghimehr’s result [Second-order connectivity index of an infinite class of dendrimer nanostars, Dig. J.
Nanomater Bios., 2009].
(Received June 14, 2011; accepted August 23, 2011) Keywords: Dendrimer, k-Connectivity Index
1 Introduction
A dendrimer is generally described as a macromolecule, which is characterized by its highly branched 3D structure that provides a high degree of surface functionality and versatility. It is constructed through a set of repeating chemical synthesis procedures that build up from the molecular level to the nanoscale region under the condition that is easily performed in a standard organic chemistry laboratory.
Dendrimers have often been referred to as the”Polymers of the 21st century”. Dendrimer chemistry was first introduced in 1978 by Buhleier, Wehner, and Vogtle [3], and in 1985, Tomalia et al [14] synthesized the first family of dendrimers. In 1990, a convergent synthetic approach was introduced by Hawker and Frechet [4]. Dendrimer popularity then greatly increased, resulting in a large number of scientific papers and patents.
As
where v1v2···vk+1 runs over all paths of length k in G and dvi denotes the degree of vertex vi.
The higher connectivity indices are of great interest in molecular graph theory, one can refer [6]
and [13] for more details, and some of their mathematical properties have been reported in [2, 5, 7, 11].
In [1], Ahmadi and Sadeghimehr determined the 2-connectivity index of an infinite class of dendrimer nanostars. In this paper, we give the exact value of the k-connectivity index of such dendrimers for a nonnegative integer k, which generalize Ahmadi and Sadeghimehr’s result.
*Corresponding author email: [email protected]
1 ( ) 1
uv u v
G d d χ =∑
1 2 1
1
1 2
1 2 1
( ) ( )
k
v v vk
v v v
G d d d
χ
+
−
=
∑
+
2. Main results
Let D[n] denote a type of dendrimer with n growth stages, D[2], D[3] and D[5] are shown in Fig.1. The dendrimer D[n] can be constructed recursively: set D[1] := K1,4 the star with four leaves (vertices of degree one), and D[n + 1] is obtained from D[n] by adding two new independent vertices adjacent to each of the leaves of D[n]. The unique vertex of degree four in D[n] is called the center of D[n].
For a given positive integer k, let P(n)i1 i2 ···ik+1 denote the number of paths composed by k+1 consecutive vertices of degree i1, i2,···, ik+1, respectively in D[n]. Since D[n] is undirected, P(n)i1 i2 ···ik+1 = P(n)ik+1ik ···i1 .
We compute Pi1i2···ik+1 according to the choices of i1i2···ik+1.
I. .Such paths exist if and only if k is even and 2 ≤ k ≤ 2n−2.
Such a path must start from a leaf, then k/2 steps toward to the center and k/2 steps away from the center. There are 4 · 2n−1 ways to choose an end of such a path (as there are 4 · 2n−1 leaves).
Then the following k/2 consecutive vertices are uniquely determined (toward the center). Since the next step must toward the reverse direction, this vertex again is determined uniquely. For each of the remaining k−1 vertices, there are two choices, so there are totally 2k/2−1 ways to choose them.
By the symmetry, each path is calculated twice. Hence
II. . Such paths exist if and only if k = n.
Such a path is uniquely determined by the end of degree one. So III. .Such paths exist if and only if 1 ≤ k ≤ n − 1.
By the recursion of D[n], such a path can be seen as a path in D[k] of type 13···34. Hence, by II,
IV. (k1 + k2 = k−2). Such paths exist if and only if k1 = k2 = n−1 and k
= 2n.
Such a path is composed by two symmetric segments of length k2 = n, each segment can be considered as a path from the center to a vertex of degree one. There are
choices for the first vertex adjacent to the center of the two segments. For each of the remaining k−2 vertices in the two segments, there are two choices to take them. Hence
Fig. 1
1 1
( ) 1 2 2
13 31
4 2 2 1 2 , 2 2 2
2
k k
n n n
P = ⋅ − ⋅ − ⋅ = + − ≤ ≤k n−
( ) 1 1
13 34 4 2 2 ,
n n n
P = ⋅ − = + k =n
( ) ( ) 1
33 34 13 34 2 ,1 1
n k k
P = P = + ≤ ≤ −k n
4 2
1 2 k 1
3 3 4
k
i i i+ =
1 2 1
1
13 3 4
k
k
i i i +
−
=
1 2 1
1
13 31
k
k
i i i+
−
=
( ) 2 1
13 4 31
4 2 3 2 , 2
2
n k k
P − − k n
= ⋅ = ⋅ =
1 2
1 2 k 1
13 3 4 3 31
k k
i i i + =
V.
1 2
1 2 k 1 13 3 4 3 3
k k
i i i + = (k2 ≥ 1, k1 + k2 = k−1). Such paths exist if and only if k1 = n−1, k2 = k−n, n+1 ≤ k ≤ 2n−1.
Such a path is composed by two segments of length k1 + 1 and k2, respectively, each of which starts from the center. The difference between the case from case IV is that the two segments are not symmetric. So, by a similar reason as in IV,
VI.
(VI.1) k is even and 1 ≤ k ≤ n−1.
Such a path must start from a vertex of degree one to a vertex of degree three with k/2+1 steps toward to the center, then k/2−1 steps toward or away from the center. There are 4·2n−1 choices for the vertex of degree one, and the first k/2+2 vertices are uniquely determined once the starting vertex of degree one has been chosen. For each of the remaining k/2−1 vertices, there are two choices. So
(VI.2) k is even and n ≤ k ≤ 2n−4.
Such a path must start from a vertex of degree one to a vertex of degree three with i steps with k/2+1 ≤ i ≤ n−1 toward the center, then k−i steps away from the center. There are 4·2n−1 ways to choose the vertex of degree one, and the first i+2 vertices (including the first vertex chosen for the reverse direction) are uniquely determined once the starting vertex of degree one has been chosen.
For each of the remaining k−i−1 vertices, there are two choices. So,
With a similar discussion as in (VI.1) and (VI.2), respectively, we have the following two formulas when k is odd.
(VI.3) k is odd and 1 ≤ k ≤ n − 1 (VI.4) k is odd and n ≤ k ≤ 2n − 3
VII.
(VII.1) k is even. Such a path exists if and only if k≤2n−4, that is n≥k+4
If k = 2n−4, i.e. n = (k+4)/2, by the recursion of D[n], such a path corresponds to a path of type 13···31 of length k in D[n−1]. Hence, by I
If k < 2n−4, i. e. n > (k+4)/2 , by the recursion of D[n], a 3···3 path in D[n] is either a 3···3 path in D[n−1], or a 13···31 path in D[n−1], or a 13···3 path in D[n−1]. So,
Using (1) recursively, and by I and VI, we have
1 2
1 2 k 1
13 3 4 3 3
k k
i i i+ =
( ) 2
13 4 3 4 3 2 3 2 , 1 2 1
n k k
P = ⋅ ⋅ − = ⋅ n+ ≤ ≤k n−
( ) 1 2 1 2
13 33 4 2 2 2
k k
n n n
P = ⋅ − ⋅ − = +
1
( ) 1 1 2 1
13 33
/ 2 1
4 2 2 2 2
n k n
n n k i k
i k
P
− +
− − − +
= +
= ⋅ ⋅
∑
= −
1 1
( ) 1 2 2
13 33 4 2 2 2
k k
n n n
P
− + +
= ⋅ − ⋅ =
1 1
( ) 1 1 2 1
13 33
( 1)/ 2
4 2 2 2 2
n k n
n n k i k
i k
P
− + +
− − − +
= +
= ⋅ ⋅
∑
= −
4 4 4
( ) ( 1) 1 1
( ) 2 2 2 2
13 33 33 33 13 31 2 2 , ( 2 4)
k k k k
n k
P P P k n
+ + − + + − −
= = = = = −
( 1) ( ) ( ) ( )
33 33 33 33 13 31 13 33
n n n n
P + =P +P +P
1 2 1
1
3 3
k k
i i i +
+
=
(1)
(VII.2) k is odd. Such paths exist if and only if k ≤ 2n−5, that is n ≥ (k+5)/2 .
If k = 2n−5 and k ≥ 3, such a path can be considered as a path of type 13···3 of length k in D[n−1].
So, by (VI.4),
If 3 ≤ k < 2n − 5 i.e. n ≥ (k+5)/2 + 1 ≥ 5, such a path corresponds to either a path of type 3···3 in D[n−1] or a path of type 13···3 in D[n−1]. So
Applying (2) recursively and by VI,
If k = 1 and n = 3, such a path can be considered as a path of type 13 in D[2]. By (VI.3), Applying (2) recursively and again by VI,
4 1
( )
( ) 2 ( ) ( )
33 33 33 33 13 31 13 33
4 2
( )
k n
n i i
i k
P P P P
+ −
= +
= +
∑
+
1 2 1 1
4 2
1 1 1 1
2 2
4 1
2
2 (3 2 2 ),
2 (3 2 2 ) 3 2 , 1
n k i
k k
i k
k k
k i n i
k k
k i k
i
k n
k n
− + − +
= +
+ − + − + −
+ = +
=
+ ⋅ − ≥
= + ⋅ − + ⋅ ≤ −
∑
∑ ∑
2 1
2 1
3 2 (2 1 ) 2 , 2 4
3 2 (3 ) 2 , 1
n k k
n k k
n k n k n
k k n
+ −
+ −
⋅ − + − ⋅ ≤ ≤ −
=
⋅ − + ⋅ ≤ −
5 5 1 5
( ) ( 1) 1
( ) 2 2 2 2 1 1
3 3 3 3 13 3 2 2 2
k k k k
n k k
P P P
+ + − + + + − + +
= = = − =
( ) ( 1) ( 1)
3 3 3 3 13 3
n n n
P =P − +P −
5 1
( )
( ) 2 ( )
3 3 3 3 13 3
5 2
k n
n i
i k
P P P
+ −
= +
= +
∑
1 1
1 2 1
5 2
1 1 1
1 2 1 2
5 1
2
2 (2 2 ), 2 5
2 (2 2 ) 2 , 3 1
n k i
k k
i k
k k
k i n i
k k
k i k
i
n k n
k n
− + +
+ +
= +
+ + − + +
+ +
+ = +
=
+ − ≤ ≤ −
= + − + ≤ ≤ −
∑
∑ ∑
1 2
1 2
2 (2 1 ) 2 , 2 5
2 (3 ) 2 , 3 1
n k k
n k k
n k n k n
k k n
+ +
+ +
− + − ⋅ ≤ ≤ −
=
− + ⋅ ≤ ≤ −
(2)
(3) 3
33 2
P =
1
( ) (3) ( )
33 33 13
3 n
n i
i
P P P
−
=
= +
∑
Therefore, we have
VIII. , where k1 + k2 = k, k1≥ 1, k2≥ 1 By the symmetry of k1 and k2, we may assume k1≥ k2.
(VIII.1) k is even
If k1 = k2 = k/2 , such a path can be seen as a path of type 13···343···31 in D[k/2].
By IV,
If k1 > k2, that is k1≥ k/2+1, such a path can be seen as a path of type 13···343···3 in D[k1]. By V,
If k ≤ n, then
If n+1 ≤ k ≤ 2n−2, then
(VIII.2) k is odd
Similarly as in (VIII.1) (the only difference is k1 ≠ k2 in this case), we have
and
Based on the above computations, we can get the formula of the k-connected index of D[n] for any nonnegative integer k.
Theorem 2.1 Given a positive integer n, the k-connected index of D[n] for any nonnegative integer k are listed in Table 1.
Proof: If k = 0, let ni denote the number of vertices of degree i in D[n], then n1 = 2n+1, n3 = 22 + ··· + 2n = 2n+1− 4, and n4 = 1 from the definition of D[n]. Hence
If 1 ≤ k ≤ n − 1 and k is even, then the possible types of all paths of length k in D[n] are 13···31, 3···34, 13···3, 3···3 and 3···343···3. By I, III, (VI.1), (VII.1) and (VIII.1),
3 4
2 2 2n
= + ++
2 1 8, 3
0, 1, 2
n n
n
+ − ≥
= =
1 2 ( )
3 3 1
2
2 (2 1 ) 2 , 2 5
2 (3 ) 2 ,1 1
n k k
n
n k k
n k n k n
P
k k n
+ +
+ +
− + − ⋅ ≤ ≤ −
=
− + ⋅ ≤ ≤ −
1 2
1 2 k 1
3 3 4 3 3
k k
i i i+ =
( ) ( / 2) 1
3 343 3 13 343 3 3 2
n k k
P =P = ⋅ −
(1) ( )
3 343 3 k 13 343 3 3 2
n k
P =P = ⋅
1
1
1 ( )
( ) ( / 2)
3 343 3 13 343 31 13 343 3
/ 2 1 k
k
n k
k k
P P P
−
= +
= +
∑
1
1
1 1
/ 2 1
3 2 3 2
k
k k
k k
− −
= +
= ⋅ +
∑
⋅ 3(k 1)2k−1= −
1
1
1 ( )
( ) ( / 2)
3 343 3 13 343 31 13 343 3
/ 2 1 n
k
n k
k k
P P P
−
= +
= +
∑
1
1
1 1
/ 2 1
3 2 3 2
n
k k
k k
− −
= +
= ⋅ +
∑
⋅ 3(2n k 1)2k−1= − −
1 1
1 1
1 1
( ) ( )
3 343 3 13 343 3
( 1)/ 2 ( 1)/ 2
3 2
k k
k k
n
k k k k
P P
− −
= + = +
=
∑
=∑
⋅
3(k 1)2k−1
= −
1 1
1 1
1 1
( ) ( )
3 343 3 13 343 3
( 1)/ 2 ( 1)/ 2
3 2
n n
k k
n
k k k k
P P
− −
= + = +
=
∑
=∑
⋅
3(2n k 1)2k−1
= − −
1 1 1
0
2 2 4 1
2 1 1 1( [ ]) 3 (2 4) 2 2
1 3 4
n n
n n
χ D n = + + + − + = − + − + + + −
1 1
( ) 2 ( ) 1 ( ) 2 ( ) 2
13 31 2 , 33 34 2 , 33 33 3 2 (3 ) 2 , 13 33 2
k k k
n n n
n n k n k n
P = + − P = + P = ⋅ + − − +k ⋅ P = + and P( )n3 4 3 =3(k− ⋅1) 2k−1, respectively. So,
If 1 ≤ k ≤ n − 1 and k is odd, then the possible types of all paths of length k in D[n] are 3···34,13···3, 3···3 and 3···343···3 By III, (VI.3), (VII.2) and (VIII.2), P( )n33 34 =2k+1,
1 1
( ) 2 ( ) 2
13 33 2 , 33 33 2 (3 ) 2
k k
n n
n n k
P P k
+ + + +
= = − + ⋅
and P( )n3 4 3 =
3(
k− ⋅1) 2
k−1, respectively. So,The other formulas can be verified similarly.
Table 1: formula of k-connected index of D[n]
k kχ
( [ ])
D nk = 0
3 1
13 8
3 2 2 3
+ n+ + −
1 ≤ k ≤ n − 1
odd
1 2 2
1 1
3 1 (3 3 4) ( 3 12)
2 2
3 3
n k k
k k
+ k
+ −
+ +
+ − + −
+
even 2 2
1
3 1 (3 3 4) ( 3 12)
2 2
3 3
n k
k
k k
k
+ −
+
+ + − + −
k = n
odd
3 1 2 2
1 1
3 1 (3 3 4) (8 11 3)
2 2
3 3
k
k
k k
+ k
−
+ +
+ + − + −
even
3 2 2
1
3 1 (3 3 4) (8 11 3)
2 2
3 3
k k
k k
k −
+
+ + − + −
n + 1 ≤ k ≤ 2n − 4 odd
1 2 2
1 1
3 1 (6 3 8) (4 3 3) (14 11 3)
2 2
3 3
n k k
k k
n k
+ + −
+ +
+ − − − + −
+
1 1
2 2
1
1 1 1
( [ ]) 2 2 2
3 3 4 3
k k
n n
k k
k k k
χ D n + − + +
= − + +
⋅
1 1
2
1
1 1
[3 2 (3 ) 2 ] 3( 1) 2
3 4 3
n k k k
k k
k k
+ − −
+ ⋅ − + ⋅ + + − ⋅
⋅
2 2
1
3 1 (3 3 4) ( 3 12)
2 2
3 3
n k
k
k k
+ k −
+
+ − + −
= +
1
1
1
21
( [ ]) 2 2
4 3 3
n k
k k
k k
χ D n = + + + + +
⋅
1 2 1
1
1 1
[2 (3 ) 2 ] 3( 1) 2
3 4 3
n k
k k
k k
k k
+ + −
+ − + ⋅ + + − ⋅
⋅
1 2 2
1 1
3 1 (3 3 4) ( 3 12)
2 2
3 3
n k
k
k k
+ k
+ −
+ +
+ − + −
= +
even 2 2
1
3 1 (6 3 8) (4 3 3) (14 11 3)
2 2
3 3
n k
k
k k
n k
+ −
+
+ − − − + −
+
k = 2n − 3 3 3 7 1
2 3
k k
+ −
k = 2n − 2 2
1
3 3 10 2 3
k k
−
−
+
k = 2n − 1 1 3 1
2 3
k k
−
−
k = 2n 2
4
1 2 3
k k
−
−
k > 2n 0
References