Applied Mathematics
Vol.07 No.03(2016), Article ID:63916,8 pages
10.4236/am.2016.73020
Reciprocal Complementary Wiener Numbers of Non-Caterpillars
Yanli Zhu, Fuyi Wei, Feng Li
Department of Applied Mathematics, South China Agricultural University, Guangzhou, China
Copyright © 2016 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
Received 14 January 2016; accepted 23 February 2016; published 26 February 2016
ABSTRACT
The reciprocal complementary Wiener number of a connected graph G is defined as
where is the vertex set. is the distance between vertices u and v, and d is the diameter of G. A tree is known as a caterpillar if the removal of all pendant vertices makes it as a path. Otherwise, it is called a non-caterpillar. Among all n-vertex non-cater- pillars with given diameter d, we obtain the unique tree with minimum reciprocal complementary Wiener number, where. We also determine the n-vertex non-cat- erpillars with the smallest, the second smallest and the third smallest reciprocal complementary Wiener numbers.
Keywords:
Reciprocal Complementary Wiener Number, Wiener Number, Caterpillar
1. Introduction
The Wiener number was one of the oldest topological indices, which was introduced by Harry Wiener in 1947. About the recent reviews on matrices and topological indices related to Wiener number, refer to [1] - [4] . The RCW number is one of the hotest additions in the family of such descriptors. The notion of RCW number was first put forward by Ivanciuc and its applications were discussed in [5] - [8] .
Let G be a simple connected graph with vertex set. For two vertices, let denote the distance between u and v in G. Then, the RCW number of G is defined by
where d is the diameter and the summation goes over all unordered pairs of distinct vertices of G. Some properties of the RCW number have been obtained in [9] [10] .
A tree is called a caterpillar if the removal of all pendant vertices makes it as a path. Otherwise, it is called a non-caterpillar.
For integers n and d satisfying, let be the tree obtained from the path labelled as
by attaching the path and pendant vertices to vertex for (see Figure 1). Let
In this paper, we show that among all n-vertex non-caterpillars with given diameter d, is the unique tree with minimum RCW number where. Furthermore, we determine the non-caterpillars with the smallest, the second smallest and the third smallest RCW numbers.
2. RCW Numbers of Non-Caterpillars
All n-vertex trees with diameter 2, 3, and are caterpillars. Let n and d be integers with and. Let be the class of non-caterpillars with n vertices and diameter d. Let be
the class of non-caterpillars obtained by attaching the stars at their centers and
pendant vertices to one center (fixed if it is bicentral) of the path, where, and for
(see Figure 2). Recall that Obviously, and
.
Let T be a tree. For and, let be the degree of u in T and be the
sum of all distances from u to the vertices in A, i.e.,. Here and in the following denotes the distance between vertices u and v in T.
Lemma 1 Let T be a tree with minimum RCW number in, where. Then,.
Proof. Suppose that Let be a diametral path of T. If d is odd,
we require that. Then at least one of has degree at least three. There are two cases.
Case 1. One of different from has degree at least three. Let be all the neighbors
outside except those of, where is a neighbor of. Let be the subtree of containing. be the tree formed from T by deleting edges and adding edges for
Figure 1. The tree Nn,d,i.
Figure 2. The tree NC (n,d).
all. Obviously,. Let and. It is easily seen that
with equality if and only if. Since, for and with. We get
Then
with equality if and only if (which is only possible for odd number d). But, and thus if then. So for Thus
since for . It follows that. This is a contradiction.
Case 2. Any verter with and has degree two. Obviously,. Let be the (unique) path from x to in T such that. Since, we have. Let be the neighbors of y in T, where and.
Let be the tree obtained from T by deleting edges and adding edges for all. Then. Let, Since for , we get
This is a contradiction.
By combining Cases 1 and 2, we find that is impossible. The result follows.
Lemma 2 Let with. Then
with equality if and only if.
Proof. Let T be a tree with the minimum RCW number in. Let be a diametral path of T.
Suppose that there is a vertex with Let be the neighbors of u different from in T, where. Clearly, are pendant vertices for. Let be the tree
obtained from T by deleting edges and adding edges for. Obviously, Let, and Since for
, we get
and then, this is a contradiction. Thus any vertex of T outside has degree at most two.
Suppose that there are at least two vertices of T outside with degree two. Let
with and let x be the neighbor of y which is different from in T. Let be the tree formed from T by deleting edge yx and adding edge. Obviously, Let Since and for, we get
This is a contradiction. Thus there is exactly one vertex outside with degree two and all other vertices of T outside are pendant vertices. Then,.
By a direct calculation, we get
Combining Lemmas 1 and 2, we get
Theorem 1 Let, and Then
with equality if and only if.
Lemma 3 For, there is.
Proof. If d is even, then
If d is odd, then
The result follows.
Theorem 2 For, there is
And for any n-vertex non-caterpillar T different from ,
Proof. Let, where. If, then T is a non-caterpillar where
It follows that
and hence is monotonically decreasing for This implies
Now suppose that. By Theorem 1 and Lemma 3, there is
where equality holds if and only if We need only to show
Case 1. n is odd. Let and. Then there is
Case 2. n is even. Let Then there is
Thus, the proof is finished.
Cite this paper
YanliZhu,FuyiWei,FengLi, (2016) Reciprocal Complementary Wiener Numbers of Non-Caterpillars. Applied Mathematics,07,219-226. doi: 10.4236/am.2016.73020
References
- 1. Ivanciuc, O. (2003) Graph Theory in Chemistry. In: Gasteiger, J., Ed., Handbook of Chemoinformatics, Wiley-VCH. Weinheim, 103-138.
http://dx.doi.org/10.1002/9783527618279.ch6 - 2. Ivanciuc, O. (2003) Topological Indices. In: Gasteiger, J., Ed., Handbook of Chemoinformatics, Wiley-VCH, Weinheim, 981-1003.
http://dx.doi.org/10.1002/9783527618279.ch36 - 3. Janezic, D., Milicevic, A., Nikolic, S. and Trinajstic, N. (2007) Graph-Theoretical Matrices in Chemistry. University of Kragujevac, Kragujevac.
- 4. Luo, W. and Zhou, B. (2009) On Ordinary and Reverse Wiener Indices of Non-Caterpillars. Mathematical and Computer Modelling, 50, 188-193.
http://dx.doi.org/10.1016/j.mcm.2009.02.010 - 5. Ivanciuc, O. (2000) QSAR Comparative Study of Wiener Descriptors for Weighted Molecular Graphs. Journal of Chemical Information and Modeling, 40, 1412-1422.
http://dx.doi.org/10.1021/ci000068y - 6. Ivanciuc, O., Ivanciuc, T. and Balaban, A.T. (2000) The Complementary Distance Matrix, a New Molecular Graph Metric. ACH-Models in Chemistry, 137, 57-82.
- 7. Ivanciuc, O., Ivanciuc, T. and Balaban, A.T. (2002) Quantitative Structure-Property Relationship Evaluation of Structural Descriptors Derived from the Distance and Reverse Wiener Matrices. Internet Electron. Journal of Computer-Aided Molecular Design, 1, 467-487.
- 8. Ivanciuc, O., Ivanciuc, T. and Balaban, A.T. (1999) Vertex- and Edge-Weighted Molecular Graphs and Derived Structural Descriptors. In: Devillers, J. and Balaban, A.T., Eds., Topological Indices and Related Descriptors in QSAR and QSPR, Gordon and Breach, Amsterdam, 169-220.
- 9. Cai, X. and Zhou, B. (2009) Reciprocal Complementary Wiener Numbers of Trees, Unicyclic Graphs and Bicyclic Graphs. Discrete Applied Mathematics, 157, 3046-3054.
http://dx.doi.org/10.1016/j.dam.2009.05.001 - 10. Zhou, B., Cai, X. and Trinajstic, N. (2009) On Reciprocal Complementary Wiener Number. Discrete Applied Mathematics, 157, 1628-1633.
http://dx.doi.org/10.1016/j.dam.2008.09.010