• Nu S-Au Găsit Rezultate

(1) COMPUTING THE HOSOYA INDEX AND THE WIENER INDEX OF AN INFINITE CLASS OF DENDRIMERS KEXIANG XU* College of Science, Nanjing University of Aeronautics &amp

N/A
N/A
Protected

Academic year: 2022

Share "(1) COMPUTING THE HOSOYA INDEX AND THE WIENER INDEX OF AN INFINITE CLASS OF DENDRIMERS KEXIANG XU* College of Science, Nanjing University of Aeronautics &amp"

Copied!
6
0
0

Text complet

(1)

COMPUTING THE HOSOYA INDEX AND THE WIENER INDEX OF AN INFINITE CLASS OF DENDRIMERS

KEXIANG XU*

College of Science, Nanjing University of Aeronautics & Astronautics, Nanjing, China

A dendrimer is a tree-like highly branched polymer molecule, which has some proven applications, and numerous potential applications. The Hosoya index of a graph is defined as the total number of the independent edge sets of the graph, while the Wiener index is the sum of distances between all pairs of vertices of a connected graph. In this paper, we give a relation for computing Hosoya index and a formula for computing Wiener index, of an infinite family of dendrimers.

(Received October 15, 2010; accepted January 22, 2011) Keywords: Dendrimer, Molecule, Hosoya Index, Wiener Index

1. Intoduction

Dendrimers are nanostructures that can be precisely designed and manufactured for a wide variety of applications, such as drug delivery, gene delivery and diagnostics etc. The name

“dendrimer” comes from the Greek word "δένδρον", which translates to "tree". 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. The first dendrimers were made by divergent synthesis approaches by Vögtle in 1978 [1]. Dendrimers thereafter experienced an explosion of scientific interest because of their unique molecular architecture.

A topological index is a numerical quantity derived in a unambiguous manner from the structure graph of a molecule. As a graph structural invariant, i.e. it does not depend on the labeling or the pictorial representation of a graph. Various topological indices usually reflect molecular size and shape. One topological index is Hosoya index, which was first introduced by H.

Hosoya [2]. It plays an important role in the so-called inverse structure–property relationship problems. For detais of mathematical properties and applications, the readers are suggested to refer to [3,4] and the references therein. As an oldest topological index in chemistry, Wiener index first introduced by H. Wiener [5] in 1947 to study the boiling points of paraffins. Other properties and applications of Wiener index can be found in [3, 6, 7]. For other tological indices, please see [8-11].

*Corresponding author: [email protected]

(2)

Let be a graph with vertex set and edge set . For a vertex , we denote by the neighbors of in G.

G

N

) (G

V E (G ) vV (G )

)

G

(v

v dG(v)= NG(v) is called the degree of v in G or written as d(v) for short. A vertex v of a tree T is called a branching point of T if , and a vertex in a tree

3 ) ( vd

T

is called a leaf when

d ( v ) = 1

. A matching of is a edge subset in which any two edges can not share a common vertex. A matching in with k edges is called a k- matching of . The Hosoya index of molecular graph , denoted by , is defined as [6]:

G

(G z

G

G G

)

⎥⎦

⎢⎣

=

=

2

0

) , ( )

(

n

k

k G m G

z

,

where denotes the number of k-matchings in G for , and . The Wiener index of a molecular graph G was defined as [5]:

) , ( G k

m

k ≥1

1 ) 0 , ( G = m

=

) ( ,

) , ( )

(

G V v u

G

u v

d G

W

,

where the summation goes over all pairs of vertices of G and denotes the distance of the two vertices u and v in the graph G (i.e., the number of edges in a shortest path connecting u and v).

For other undefined notations and terminology from graph theory, the readers are referred to [8].

) , ( u v d

G

In this paper we study the Hosoya index and the Wiener index of an infinite class of dendrimers.

Structure of dendrimer D[n] is shown in Fig. 1 for

n = 1 , 2 , 3

, where denotes the step of growth in this type of dendrimer.

n

t m

a

b c d

olecular size d s

3 2 1

D[1] D[2] D[3]

Fig. 1 Structure of dendrimer D[n] for

n = 1 , 2 , 3

(3)

2. Main results and discussion

To obtain our main results, we list some important lemmas which will be used in the subsequent proofs.

Lemma 1. [3] Let G be a graph, and v ∈ V (G). Then we have

− +

=

) (

}) , { ( )

( ) (

v N

w G

w v G z v

G z G

z

.

Lemma 2. [3] If

G

1

, G

2

,

L

, G

kare the components of a graph G, then we have

) ( )

(

1 i

k

i

G z G

z Π

=

=

.

Lemma 3. [16,17] Let T be a tree of order n, be the all branching points of T with

( ), , be the components of

v

k

v v

1

,

2

,

L

,

im i

i

m

v

d ( ) = i = 1 , 2 ,

L

, k T

i1

, T

i2

, L , T Tv

i, and the order of is equal to (

j

;

i

T

ij

n

ij

= 1 , 2 ,

L

, m

i

= 1 , 2 ,

L

, k

). Then

W(T)=

∑ ∑

,where

= < <

⎟⎟ −

⎜⎜ ⎞

⎛ +

k

i p q r m

ir iq ip

i

n n n n

3

1 1

1

2

1

1

+ n + + n = n

n

i i L imi , and

.

, k i = 1 , 2 ,

L

Let be the binary tree whose step of growth is equal to [see Fig. 2]. In the following theorem, we give the recursive formula for .

T

n n

) ( T

n

z

O

O

a b

O

a b

T

0 T1 T2

T

3

Fig. 2 The trees

T

n for

n = 0 , 1 , 2 , 3

Theorem 1.

z ( T

n

) = z ( T

n1

)

2

+ 2 z ( T

n2

) z ( T

n1

)

, where

z ( T

0

) = 1 , z ( T

1

) = 3

.

Proof. From the definition of Hosoya index, it is easy to check that

z ( T

0

) = 1 , z ( T

1

) = 3

. When

(4)

≥2 n

) (T z

n

, assume that is the first vertex of with as its only neighbors (see Fig. 2) , by Lemma 1, we have

O

(T z

T

n

,b o

a, b

}) { ( }) , { )

( T O o a z T

z

n

− +

n

− +

n

=

.

Note that consists of two components, each of which is , and , are all isomorphic to . By Lemma 2, we have

O T

n

, {o T

n

1

T

n

} ,a {o T

n

) ( T

n

z

} b

( 2 z T

]) =

2

1

T

n

( T

n

z

T

n

) ( ) )

(

1 2

+

2 1

= z T

n n

z T

n ,

which completes the proof of this theorem. ■ Theorem 2.

z ( D [ n z ( T

n1

)

4

+ 4 z ( T

n2

)

2 1

)

3, where

z ( D [ 1 ]) = 5

.

Proof. From the definition, we obtain

z ( D [ 1 ]) = 5 c, d

immediately. For , assume that is the center vertex of with as its four neighbors. Obviously, consists of four components, each of which is . By symmetry, we find that

≥2

n O

a ]

[ n

D a , b , D [ n ] − o

1

T

n

D [ n ] −

,

, and are all isomorphic to . By Lemmas 1 and 2, we

have

b n

D [ ] − D [ n ] − c D [ n ] − d 2 T

n2

∪ 3 T

n1

] [

, ) ( ) ( 4 (

}) , { ] (

}) , { ] [ ( }) , { (

, { ] [ ( ) (

]) [ (

3 1 2

2

+

=

− +

− )

[ ] [

4

1

}) + − +

− +

=

n n

n

z T z T

T z

d o z

c o n D z b o D

z a o n D z o D z n D

n D

n n

]) 1 [ z

[ (D W

which finishes the proof of this theorem. ■

Nest we consider the Wiener index of . In the following theorem we present the formula of . From the definition of Wiener index,

] [n D ])

n ( D = 16 .

] n W

Theorem 3. For a dendrimer

D [

with n≥2 , we have

4 (

4 3 2

32 3

) 2 2 )(

3 2 2

]) (

2

1 2

2

− − − − − − −

=

n+ n+ n+ n+

n

n

n ) 2

3 2 11

4 n

2

)(

2

1

) +

[ (D W

2 ( 4

0

+

3n

+

.

Proof. Note that the number of vertices in

D [n ]

is:

3 2 1 ) 1 2 ( 4 1 2

2

1

+

L

+

n

=

n

− + =

n+2

.

, let be the vertex of

v

i

D [n ]

with the distance from the center vertex

i

For 1≤in−1

(5)

O. We find that, for 1≤in−1, the number of such ’s is

v

i

4 × 2

i1

= 2

i+1, and the graph has three components, two of which have the same order:

, while the remaining one of which has the order:

.

v

i

n ] − 2

1

+ +

2

− 3 − D[

2

0

2

n+

1 2

n−i

2 2 )

1 =

n+2

o

2

1

=

+

n−i L

2 ( 2

1 −

n−i

n−i+1

− 2

For the center vertex , the graph

D [ n ] − o

has four components, each of which has the

same order

− 1

. So by Lemma 3, we have

i −1)2(

n

−2n+1 i i

+1+

3 2

2n

+1+22n)

2

2

1

= +

n n L

=

⎟⎟⎠

1

1 1(2 2 4

n

i i

=

1 1

2

22

( 2 4

n

i

n i

=

1 1

2 ( 2 [ 2 4n

i

i i

=

1 1

23

( 2 [ 4n

i

n i

2 2

0

+

1

+

+

⎜⎜⎝

⎛ −

= 2

3 2 2n

+

⎟⎟⎠

⎜⎜ ⎞

2 − 3

2 2n

+

⎟⎟⎠

⎜⎜ ⎞

2 − 3

2 2n

+

⎟⎟⎠

⎜⎜ ⎞

2 − 3

2 2n

+

+2−2 2)−

2n n i 4(2n −1)3

−4(2 1)3

) n

+ +2 −2n)+2n 1

n

+

+

+2 1 2 )

2n n i i

1

2n

−2

+

22n

]) [n D

=

=

= ( W

+ − −

+1)(2n 1 i 1

− − −

3 3 2 3

2n) 2n i i(2 1] 4(2n 1)

− − − −

−23n 2i ( 2 ] 4(2n 1)3

3 1

) 1 ( 2 3

) 1 ( 2

1 3

) 1 )

2 2 )(

1 2 ( 4

) 2 1 ( 3 2 ) 4 2 2

2 ( ) 4 2

− +

+

− −

+

+

n n

n

n n

n n

n

2 2

1 2

) 2 2

3 2 )(

3

+

+ +

n n

n 2 n

)(

1 ( 4

2 )(

2 2 (

− +

+ n

n 4 ( 2

1 )( −

=

3 1

2 2

1 2

) 2 2

3 2 )(

3

+

+ +

n n

n n

2 3

1 1

3

) 1 ( 4 ) 2 2 ( 2 4

2 4 ) 2 2 3 ( ) 4 2 3

2 ( ) 4 2

×

× +

− +

×

− −

+

+ +

+

n n

n n

n n

n 2

2 2

n n 2

)(

1 ( 4

2 )(

2 2 (

− +

+

n

n

= 8

n n

n n

n n

3 2 3

3 2 )(

3

2 1 2

+

×

+

+

n n

2 ( 4 8

2 )(

2 2 (

3 2

+

n n

n

n

n n

2 2

2 ) 1 2

2 ) 2 ( 4 2

) 1 4 ( ) 2 2 5 3 ( 4 ) 2

2 2

2 2 3

×

×

×

− +

×

− −

+

+

16 2 +

×

=

4 2 3 ) ( 11 4 2

4 3 2

32 3

2 )(

3

1

2

+

+ n

n

− 2 ) −

3n

+ − −

n

n 2 n

)(

2 2

(

n+2

2n+2

=

.

Thus we complete the proof of this theorem. ■ Acknowledgments

This work has been supported by NUAA Research Founding, No.

NS2010205

(6)

References

[1] E. Buhleier, W. Wehner, F. Vögtle, Synthesis, 2, 155 (1978).

[2] H. Hosoya, Bull. Chem. Soc. Jpn. 44, 2332 (1971).

[3] I. Gutman, O.E. Polansky, Mathematical Concepts in Organic Chemistry Springer, Berlin, 1986.

[4] S. Wagner,I. Gutman, Acta. Appl. Math. DOI 10.1007/s10440-010-9575-5, (2010).

[5] H. Wiener, J. Amer. Chem. Soc. 69, 17 (1947).

[6] Fifty years of the Wiener index, I. Gutman, S. Klavzar, B. Mohar (Eds.), MATCH Commun. Math. Comput. Chem. 35, 1-259 (1997).

[7] Fiftieth anniversary of the Wiener index, I. Gutman, S. Klavzar, B.

Mohar (Eds.), Discrete Appl. Math. 80, 1--113 (1997).

[8]M. B. Ahmadi, M. Seif, Digest Journal of Nanomaterials and Biostructures, 5(1), 335 (2010).

[9] H. Wang, H. Hua, Digest Journal of Nanomaterials and Biostructures, 5(2), 497 (2010).

[10] H. Yousefi-Azari, A. R. Ashrafi, M. H. Khalifeh, Digest Journal of Nanomaterials and Biostructures, 3(4), 315 (2008).

[11] M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi, Digest Journal of Nanomaterials and Biostructures, 4(1), 63 (2009).

[12] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan Press, New York, 1976.

[13] H. Y. Deng, MATCH Comm. Math. Comput. Chem. 57, 393 (2007).

[14] J. K. Doyle, J. E. Graver, Discrete Math. 7, 147 (1977).

Referințe

DOCUMENTE SIMILARE

The Wiener [7] index is the first reported distance based topological index and is defined as half sum of the distances between all the pairs of vertices in a molecular graph..

The Hosoya polynomial of a molecular graph G is defined as where the sum is over all unordered pairs {u,v} of distinct vertices in G.. In this paper an algorithm for computing

24 Finally, we prepare a GAP 25 program for computing the line graph L(G), the Hosoya polynomial, Wiener and edge Wiener indices of any connected graph G.. In Table 1,

In this paper, we first report our recent results on computing Wiener, PI and Balaban indices of some nanotubes and nanotori.. Next, the PI and Szeged indices of a new type

This work brings to attention the concept of philosophical leadership, through which the leader can learn the meditative state to achieve a philosophical

(Nous allons voir qu’elle est rencontrée à l’intérieur même de la chronique). Dans ce sens, l’auteur fait appel aux stratégies les plus diverses. Dans une phrase

(idem), ceea ce se întâmplă și în cazul relației dintre activitatea de cercetare și etică. De altfel, dintre cele patru părți în care este structurat volumul, doar

Vasile PLENICEANU 1 , Viorica TOMESCU 2 Abstract: In order to guarantee the preservation and sustainable utilization of the natural potential, we propose that the