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]
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 ) v ∈ V (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 tree3 ) ( v ≥ d
T
is called a leaf whend ( 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
GG G
)
∑
⎥⎦⎢⎣ ⎥
⎢
=
=
20
) , ( )
(
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 ≥11 ) 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
GIn 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
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
kv v
1,
2,
L,
im i
i
m
v
d ( ) = i = 1 , 2 ,
L, k T
i1, T
i2, L , T T − v
i, and the order of is equal to (j
;i
T
ijn
ij= 1 , 2 ,
L, m
i= 1 , 2 ,
L, k
). ThenW(T)=
∑ ∑
,where= ≤ < < ≤
⎟⎟ −
⎠
⎜⎜ ⎞
⎝
⎛ +
ki p q r m
ir iq ip
i
n n n n
3
1 11
2
1
1
+ n + + n = n −
n
i i L imi , and.
, k i = 1 , 2 ,
LLet 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
nz
O
O
a b
O
a b
T
0 T1 T2T
3Fig. 2 The trees
T
n forn = 0 , 1 , 2 , 3
Theorem 1.
z ( T
n) = z ( T
n−1)
2+ 2 z ( T
n−2) z ( T
n−1)
, wherez ( 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≥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
nz
} b
( 2 z T
]) =
−2
−1
T
n( T
nz
∪ T
n) ( ) )
(
−1 2+
−2 −1= z T
n nz T
n ,which completes the proof of this theorem. ■ Theorem 2.
z ( D [ n z ( T
n−1)
4+ 4 z ( T
n−2)
2 −1)
3, wherez ( 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
nD [ n ] −
,, and are all isomorphic to . By Lemmas 1 and 2, we
have
b n
D [ ] − D [ n ] − c D [ n ] − d 2 T
n−2∪ 3 T
n−1] [
, ) ( ) ( 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 have4 (
4 3 2
32 3
) 2 2 )(
3 2 2
]) (
21 2
2
− − − − − − −
=
n+ n+ n+ n+n
nn ) 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
iD [n ]
with the distance from the center vertexi
For 1≤i≤n−1O. We find that, for 1≤i≤n−1, the number of such ’s is
v
i4 × 2
i−1= 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
in ] − 2
1+ +
2
− 3 − D[
2
02
n+1 2
n−i−
2 2 )
1 =
n+2−
o
2
1=
+
n−i− L2 ( 2
1 −
n−i−
n−i+1− 2
For the center vertex , the graph
D [ n ] − o
has four components, each of which has thesame 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
12
−
++ 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
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).