On reciprocal complementary Wiener number

Discrete Applied Mathematics 157 (2009) 1628–1633

Contents lists available at ScienceDirect

Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam

On reciprocal complementary Wiener number Bo Zhou a,∗ , Xiaochun Cai a , Nenad Trinajstić b a

Department of Mathematics, South China Normal University, Guangzhou 510631, China

b

The Rugjer Bošković Institute, P. O. Box 180, HR-10 002 Zagreb, Croatia

article

a b s t r a c t

info

Article history: Received 31 March 2008 Received in revised form 30 June 2008 Accepted 18 September 2008 Available online 29 October 2008

We report properties, especially upper and lower bounds and the Nordhaus–Gaddum-type result for the reciprocal complementary Wiener number of a connected (molecular) graph. © 2008 Elsevier B.V. All rights reserved.

Keywords: Connected graphs Reciprocal complementary Wiener number Upper and lower bounds Nordhaus–Gaddum-type result

1. Introduction The Wiener number ([21]a) (often also called the Wiener index [1]) and the related molecular descriptors have a long history [18,5,17,13] since 1947 when Harry Wiener (1924–1998) [19] introduced his number as the path number [22]. The empirical Wiener’s definition of his number has been formalized via the distance matrix ([11]a) by Hosoya [6]. In the large family of the Wiener-like molecular descriptors [20], the complementary Wiener number and the reciprocal complementary Wiener number are recent additions. They have been introduced by Ivanciuc [7] and discussed by Ivanciuc et al. [8,9]. Related work may be found in, e.g., [10]. We consider simple (molecular) graphs, i.e., graphs without multiple edges and loops ([21]b, [23]a). Let G be a connected graph with the vertex-set V (G) = {v1 , v2 , . . . , vn }. The distance matrix D of G is an n × n matrix (dij ) such that dij is just the distance (i.e., the number of edges of a shortest path) between the vertices vi and vj in G ([11]a), denoted by d(vi , vj |G). The complementary distance matrix CD of G is an n × n matrix (cij ) such that cij = 1 + D − dij if i 6= j, and 0 otherwise ([11]b), where D is the diameter of the graph G ([23]b). The reciprocal complementary distance matrix RCD of G is an n × n matrix (rcij ) such that rcij = c1 if i 6= j, and 0 otherwise ([11]c). ij

The Hosoya definition of the Wiener number of G, denoted by W(G), is given by [6] W(G) =

n n 1 XX

2 i=1 j=1

dij =

X

dij .

i D+ , then we choose the maximal such k,and for a new 2 00 diameter-maximal graph G with layers V0 , V1 , . . . , Vk−2 , Vk−1 ∪ {x}, Vk − {x}, Vk+1 , . . . , VD , it is easily seen that

RCW(G00 ) − RCW(G0 ) =

D −k  X i=1

=

≤ =

1

−

k 1

−

k 1

−

k

1

−

D+1−i−1 k−1

1 D

+

X

|Vk−1−i |

1 D

+

1 D

+

1 D

−

−

1

−

D+1−i

1



D+1−i−1



1 D−i

D−i



1

 |Vk−1−i |



1

−

D+1−i

i=1



1

1

k−1 X i=1

D+1−i

i=1

X

+

D+1−i



k−1



1

1

=

D−k+1

k

−

1

< 0,

D−k+1

a contradiction again. Now we have proved that for G0 , all noncentral layers are trivial. It may be checked that RCW(G0 ) = f (n, D).  Proposition 7. Let G be a connected graph with n ≥ 2 vertices. Then RCW(G) ≥ n − 1 with equality if and only if G = Pn . Proof. Let D be the diameter of G. Suppose that D < n − 1. If D is even, then D

f (n, D) − f (n, D + 1) = D + 2(n − D − 1)

−1 2 X i =0

1 D−i



+

(n − D)(n − D − 1) 2D



− D + 1 + 2(n − D − 2) 

1 D+2

D −1 2

+

X i =0



 ( n − D − 1)(n − D − 2) +  D+1−i 2(D + 1) 1

D

= −1 + 2

−1 2 X

1 D−i

i =0

+

n−D−1



− 2(n − D − 2)

n−D

2

D

−

n−D−2

1 D+2

+

1 D+1

−

!

1 D 2

+1



D+1

1 n−D−1 n+D · − 2(n − D − 2) · + · 2 (D + 1)(D + 2) 2 D(D + 1)   n+D 2 n+D = (n − D − 2) − + > 0. 2D(D + 1) (D + 1)(D + 2) 2D(D + 1)

≥ −1 + 2 ·

1

D

D

If D is odd, then

 f (n, D) − f (n, D + 1) = D + 2(n − D − 1) 

D+1



+

i=0

− D + 1 + 2(n − D − 2)

X i=0

= −1 + 2

i =0

≥ −1 + 2 ·

1

X

D+1−i

1 D+1

·

D+1 2

+ +

1

X

D+1 −1 2

D+1 −1 2



D−1 −1 2

1

D−i

 + (n − D)(n − D − 1) 2D

 (n − D − 1)(n − D − 2)  + D+1−i 2(D + 1) 1

n−D−1



2 n−D−1 2

n−D D

·

−

n+D D(D + 1)

n−D−2



D+1

> 0.

Thus, f (n, D) is decreasing for 1 ≤ D ≤ n − 1. Now the result follows from Lemma 6.



Let G be a tree with n ≥ 3 vertices. By Proposition 7, RCW(G) ≥ n − 1 with equality if and only if G = Pn . A direct reasoning is as follows. Let w0 w1 . . . wD be a diametrical path in G. Suppose that D < n − 1. Then for some k = 1, 2, . . . , D − 1, wk

1632

B. Zhou et al. / Discrete Applied Mathematics 157 (2009) 1628–1633

has a neighbor w outside this path. Let G0 be the tree formed from G by deleting the edge wk wk+1 and adding the edge wwk+1 . Obviously, G0 has diameter D + 1. Let V1 and V2 be respectively the set of vertices of the subtree of G containing vertex wk and wk+1 formed by deleting the edge wk wk+1 . Let d0ij = d(vi , vj |G0 ) and let rcij0 be the (i, j)-entry of the reciprocal complementary matrix of G0 . For vi , vj ∈ V1 or vi , vj ∈ V2 with i 6= j, we have d0ij = dij and then rcij0 < rcij . For vi ∈ V1 and vj ∈ V2 , we have d0ij = dij + 1 or d0ij = dij − 1 and then rcij0 = rcij or rcij0 < rcij . Thus, RCW(G0 ) < RCW(G). Using this transformation, we can finally obtain RCW(G) > RCW(Pn ) = n − 1 if G 6= Pn . By combining Corollary 3, we know that RCW number satisfies the basic requirement to be a branching index [2]. 3. Nordhaus–Gaddum-type result for the reciprocal complementary Wiener number Zhang and Wu [24] and Zhou, Cai and Trinajstić [25] obtained the Nordhaus–Gaddum-type result for the Wiener index, Zagreb indices, connectivity index and the Harary index, respectively. In the following, we give the Nordhaus–Gaddumtype result for RCW number. There is only one connected graph P4 on 4 vertices with the connected complement P4 = P4 . Obviously, RCW(P4 ) + RCW(P4 ) = 2RCW(P4 ) = 6. For n ≥ 5, the diameter of Pn is 2. Lemma 8. Let G be a connected graph on n ≥ 5 vertices. If G has diameter 2, then RCW(G) + RCW(G) ≥

n2 + 5n − 6 4

with equality if and only if G = Pn . Proof. By Proposition 1, RCW(G) ≥ n − 1 with equality if and only if G = Pn . Let h m be the number i of edges in G. Then n(n−1) 2

n(n−1) 2

− m2 ≥ n(n2−1) − 12 n(n2−1) − (n − 1) = equality if and only if the number of edges of G is equal to n − 1. Thus the result follows easily.  m ≤

− (n − 1). By Proposition 2, RCW(G) =

n(n−1) 4

+

n −1 2

with

Lemma 9. Let G be a connected graph on n ≥ 5 vertices. Suppose that both G and G have diameter 3. Then RCW(G)+ RCW(G) ≥ 5n(n−1) + 1 with equality if and only if d(G, 3) = d(G, 3) = 1. 12 Proof. Let tk = d(G, k) and tk = d(G, k). Obviously, t2 + t3 = t1 , t2 + t3 = t1 and t1 + t1 = RCW(G) + RCW(G) =

3 X tk + tk k=1

= = ≥

4−k

t1 + t1

+

3 5n(n − 1) 12 5n(n − 1) 12

with equality if and only if t3 = t3 = 1.

=

t1 + t1 3

t1 + t1

+

+

2 t3 + t3

+

t2 + t3 + t2 + t3

t3 + t3 2

2

=

5 6




+

t1 + t1 +

n(n−1) . 2

Then

t3 + t3 2 t3 + t3 2

2

+1 

It is easily seen that there are pairs of graphs on n vertices such that both of them have diameter three and t3 = t3 = 1. For example, if n = 5, then there is exactly one pair G and G : the graph formed from the path P5 by adding an edge between the n−1) two neighbors of its center and its complement which is isomorphic to itself such that RCW(G)+RCW(G) = 28 = 5n(12 +1. 3 Proposition 10. Let G be a connected graph on n ≥ 5 vertices with a connected G. Then RCW(G) + RCW(G) ≤

3n(n − 1) 4

with equality if and only if both G and G have diameter 2, whilst

 2   n + 5n − 6 for n ≥ 9 4 RCW(G) + RCW(G) ≥   5n(n − 1) + 1 for 5 ≤ n ≤ 8 12

with equality if and only if G = Pn or G = Pn for n ≥ 9, and both G and G have diameter three with d(G, 3) = d(G, 3) = 1 for 5 ≤ n ≤ 8.

B. Zhou et al. / Discrete Applied Mathematics 157 (2009) 1628–1633

Proof. Let m and m be respectively the number of edges of G and G. Then m + m = RCW(G) + RCW(G) ≤

n(n − 1) 2

−

= n(n − 1) −

m

+

n(n − 1)

2 m+m 2

=

−

n(n−1) . 2

1633

By Proposition 2,

m

2 2 3n(n − 1) 4

with equality if and only if both G and G have diameter 2. On the other hand, note that either both G and G have diameter 3 or one of them has diameter 2, and that n2 +5n−6 4

if and only if n ≥ 9. The second part of the proposition follows from Lemmas 8 and 9.

5n(n−1) 12

+1 >



Acknowledgements BZ and XC were supported by the National Natural Science Foundation of China (Grant No. 10671076) and NT by the Ministry of Science, Education and Sports of Croatia (Grant No. 098-1770495-2919). References [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26]

D. Bonchev, Information Theoretic Indices for Characterization of Chemical Structures, Research Studies Press/Wiley, Chichester, 1983, 71–74. D. Bonchev, N. Trinajstić, Information theory, distance matrix, and molecular branching, J. Chem. Phys. 67 (1977) 4517–4533. I. Gutman, K.C. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004) 83–92. I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. III. Total π -electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972) 535–538. P.J. Hansen, J.P. Jurs, Chemical applications of graph theory. Part I. Fundamentals and topological indices, J. Chem. Educ. 65 (1988) 574–580. H. Hosoya, Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Japan 44 (1971) 2332–2339. O. Ivanciuc, QSAR comparative study of Wiener descriptors for weighted molecular graphs, J. Chem. Inf. Comput. Sci. 40 (2000) 1412–1422. O. Ivanciuc, T. Ivanciuc, A.T. Balaban, The complementary distance matrix, a new molecular graph metric, ACH-Models Chem. 137 (2000) 57–82. O. Ivanciuc, T. Ivanciuc, A.T. Balaban, Quantitative structure-property relationship evaluation of structural descriptors derived from the distance and reverse Wiener matrices, Internet Electron. J. Mol. Des. 1 (2002) 467–487. O. Ivanciuc, T. Ivanciuc, A.T. Balaban, Vertex- and edge-weighted molecular graphs and derived structural descriptors, in: J. Devillers, A.T. Balaban (Eds.), Topological Indices and Related Descriptors in QSAR and QSPR, Gordon and Breach, The Netherlands, 1999, pp. 169–220. D. Janežič, A. Miličević, S. Nikolić, N. Trinajstić, Graph Theoretical Matrices in Chemistry, in: Mathematical Chemistry Monographs, vol. 3, University of Kragujevac, Kragujevac, 2007, (a) pp. 62–64, (b) pp. 79–80, (c) pp. 80–81. S. Nikolić, G. Kovačević, A. Miličević, N. Trinajstić, The Zagreb indices 30 years after, Croat. Chem. Acta 76 (2003) 113–124. S. Nikolić, N. Trinajstić, Z. Mihalić, The Wiener index: Development and applications, Croat. Chem. Acta 68 (1995) 105–128. E.A. Nordhaus, J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177. O. Ore, Diameters in graphs, J. Combin. Theory 5 (1968) 75–81. J. Plesník, On the sum of all distance in a graph or digraph, J. Graph Theory 8 (1964) 1–21. O.E. Polansky, On the modelling of Wiener numbers, in: A. Graovac (Ed.), MATH/CHEM/COMP 1988, Elsevier, Amsterdam, 1989, pp. 167–184. D.H. Rouvray, Predicting chemistry from topology, Sci. Amer. 255 (1986) 40–47. D.H. Rouvray, The rich legacy of half a century of the Wiener index, in: D.H. Rouvray and R.B. King (Eds.), Topology in Chemistry – Discrete Mathematics of Molecules, Horwood, Chichester, 2002, pp. 16–37. R. Todeschini, V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim, 2000. N. Trinajstić, Chemical Graph Theory, 2nd revised ed., CRC Press, Boca Raton, 1992, (a) pp. 241–244, (b) pp. 5–6. H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20. R.J. Wilson, Introduction to Graph Theory, Oliver and Boyd, Edinburgh, 1972, (a) p. 9, (b) p. 31, (c) p. 20. L. Zhang, B. Wu, The Nordhaus–Gaddum-type inequalities for some chemical indices, MATCH Commun. Math. Comput. Chem. 54 (2005) 189–194. B. Zhou, X. Cai, N. Trinajstić, On Harary index, J. Math. Chem. 44 (2008) 611–618. B. Zhou, I. Gutman, Relationships between Wiener, hyper-Wiener and Zagreb indices, Chem. Phys. Lett. 394 (2004) 93–95.