• Nu S-Au Găsit Rezultate

(1)THE K-CONNECTIVITY INDEX OF AN INfiNITE CLASS OFDENDRIMER NANOSTARS WEIQING WANG, XINMIN HOU* Let G be a simple connected graph of order n

N/A
N/A
Protected

Academic year: 2022

Share "(1)THE K-CONNECTIVITY INDEX OF AN INfiNITE CLASS OFDENDRIMER NANOSTARS WEIQING WANG, XINMIN HOU* Let G be a simple connected graph of order n"

Copied!
7
0
0

Text complet

(1)

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)

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/21 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 ii+ = 

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 ii + =  

(3)

V.  

1 2

1 2 k 1 13 3 4 3 3

k k

i ii + =   (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 ii+ =  

( ) 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)

(4)

(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

=

= +

(5)

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 ii+ =  

( ) ( / 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)2k1

= −

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)2k1

= − −

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)2k1

= −

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)2k1

= − −

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 = + + + − + = + − + + +

(6)

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 = ⋅ + − − +kP = + and P( )n3 4 3 =3(k− ⋅1) 2k1, 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

k1, respectively. So,

The other formulas can be verified similarly.

Table 1: formula of k-connected index of D[n]

k kχ

( [ ])

D n

k = 0

3 1

1

3 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

2

1

( [ ]) 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

+

+ +

+ − + −

= +

(7)

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

[1] M. B. Ahmadi, M. Sadeghimehr, Dig. J. Nanomater. Bios., 4(4), 639(2009).

[2] O. Araujo and J. A. de la Pe˜na, Lin. Alg. Appl., 283(3), 171(1998).

[3] E. Buhleier, W. Wehner, F. V¨ogtle, Synthesis, 2(2), 155(1978).

[4] C. J. Hawker, J. M. J. Fr´echet, J. Am. Chem. Soc., 112(21), 7638(1990).

[5] W. Jiang,

S. Zhang, Computing the Connectivity Indices of α

-

and β

-

Cyclodextrins, presented at the IEEE International Conference on Bioinformatics and Biomedicine Workshops, December 18-th, 2010, Hong Kong, China

[6] L. B. Kier, W. J. Murray, M. Randic, L. H. Hall, J. Pharm. Sci., 65(8), 1226(1976).

[7] Hao Li and Mei Lu, MATCH Commun. Math. Comput. Chem., 54(2), 417(2005).

[8] D. A. Morales and O. Araujo, J. Math. Chem., 13(1), 95(1993).

[9] Z. Mihalic and N. Trinajstic, J. Chem. Educ., 69(9), 701(1992).

[10] M. Randic, J. Am. Chem. Soc., 97(23), 6609(1975).

[11] J. Rada and O. Araujo, Discr. Appl. Math., 119(3), 287(2002).

[12] M. Randic, P. J. Hansen, P. C. Jurs, J. Chem. Inf. Comput. Sci., 28(2), 60(1988).

[13] V. K. Singh, V. P. Tewari, D. K. Gupta and A. K. Srivastava, Tetrahedron, 40(15), 2859(1984).

[14] D. A. Tomalia, H. Baker, J. Dewald, M. Hall, G. Kallos, S. Martin, J. Roeck, J.

Ryder and P. Smith, Polym. J., 17(1), 117(1985).

Referințe

DOCUMENTE SIMILARE

Toate acestea sunt doar o parte dintre avantajele in care cred partizanii clonarii. Pentru a si le sustine, ei recurg la o serie de argumente. Unul dintre ele are in atentie

During the period 1992-2004, for criminal offenses with elements of abuse in the field of real estate turnover in Kosovo there were accused in total 35 persons and none

Keywords: trickster discourse, meaning, blasphemy, social change, transgression of social norms.. The Myth of the trickster and its

a¡Iiealie în eazul unei probleme de atribuire neliniarä Partictilanzînd... Xe¡r este o solutie

The Wiener index of a graph is denoted by and is defined by .In general this kind of index is called a topological index, which is a distance based quantity assigned to

Dendrimers have been also studied from the topological point of view, including vertex and fragment enumeration and calculation of some topological descriptors, such as topological

In this paper, we give explicit formulas for the second- and third- order connectivity index of an infinite class of dendrimer nanostars.. During the past several decades, there

In continue we compute the modified Schultz index of C 4 C 8 (S) nanotorus by using the exact formula for computation Wiener index of this graph which obtained in [11].. Yousefi,