Applied Mathematics

p-ISSN: 2163-1409    e-ISSN: 2163-1425

2015;  5(5): 93-96

doi:10.5923/j.am.20150505.01

 

Computing the Hosoya Polynomial, Wiener Index and Hyper-Wiener Index of the Harary Graph

Mohammad Reza Farahani1, M. R. Rajesh Kanna2

1Department of Applied Mathematics of Iran University of Science and Technology (IUST), Narmak, Tehran, Iran

2Post Graduate Departments of Mathematics, Maharani's Science College for Women, Mysore, India

Correspondence to: Mohammad Reza Farahani, Department of Applied Mathematics of Iran University of Science and Technology (IUST), Narmak, Tehran, Iran.

Email:

Copyright © 2015 Scientific & Academic Publishing. All Rights Reserved.

This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/

Abstract

The distance d(u,v) between two vertices u and v of a connected graph G is equal to the length of a shortest path that connects u and v. The Hosoya polynomial was introduced by H. Hosoya in 1988 and defined as H(G,x)= ½ Also, the Wiener index W(G) is the sum of all distances between vertices of G as W(G)=½ whereas the hyper-Wiener index WW(G) is defined as (d(u,v)+d(u,v)2). In this paper, we compute the Hosoya polynomial of the Harary graph. Also we compute the Wiener index and hyper Wiener index of this family of Regular graphs.

Keywords: Harary graph, Topological Indices, Hosoya polynomial, Wiener Index, Hyper-Wiener index

Cite this paper: Mohammad Reza Farahani, M. R. Rajesh Kanna, Computing the Hosoya Polynomial, Wiener Index and Hyper-Wiener Index of the Harary Graph, Applied Mathematics, Vol. 5 No. 5, 2015, pp. 93-96. doi: 10.5923/j.am.20150505.01.

Article Outline

1. Introduction
2. Main Result
ACKNOWLEDGEMENTS

1. Introduction

Let G=(V,E) be a simple connected graph. The vertex-set and edge-set of G denoted by V=V(G) and E=E(G), respectively. An edge e=uv of a graph G is joined between two vertices u and v. The distance between vertices u and v, d(u,v), in a graph is the number of edges in a shortest path connecting them and the diameter of a graph G, D(G) is the longest topological distance in G.
A topological index of a graph is a single unique number characteristic of the graph and is mathematically invariant under graph automorphism. The topological index of a molecular graph G is a non-empirical numerical quantity that quantifies the structure and the branching pattern of G.
Usage of topological indices in biology and chemistry began in 1947 when H. Wiener [1, 2] introduced Wiener index to demonstrate correlations between physicochemical properties of organic compounds and the index of their molecular graphs.
The hyper-Wiener index is one of distance-based graph invariants, (based structure descriptors), used for predicting physico–chemical properties of organic compounds. The hyper-Wiener index was introduced by M. Randić in 1993 [3, 4]. The Wiener index and the hyper Wiener index of G are defined as follows:
(1)
(2)
respectively.
The Hosoya polynomial was first introduced by H. Hosoya, in 1988 [5] and define as follows:
(3)
In references [6-20], some properties and more historical details of the Wiener and Hyper Wiener indices and the Hosoya polynomial of molecular graphs are studded.

2. Main Result

The aim of this section is to obtain a closed formula of Hosoya polynomial, Wiener index and hyper-Wiener index of the Harary graph H2r+1,2n. At first we need the following definition.
Definition 1 [21-24]. Let r and n be two positive integer numbers and n≥r+1, then in the Harary graph H2r+1,2n, two vertices i and j are joined if and only if | i-j|≤ r or j=i+n (∀i,j∊ℤ2n).
Example 1. In case r=2 and n=6 (6≥2+1), the Harary graph H5,12 is shown in Figure 1. By Definition 1, one can see that the vertex v1 is joined with the vertices v2,v3, v12,v11 and v7, since 7-1=6 and for all numbers 2,3,11 and 12 (∊ℤ12), |1-2|=|1-12|<|1-3|=|1-11|≤2.
Figure 1. The Harary graph H5,12
It is easy to see that this 2r+1-regular graph has 2n vertices and 2n(2r+1)/2= n(2r+1) edges. And obviously for n=r+1, H2r+1,2r+2 is automorphic with the complete graph K2r+2. Also for r=1, H3,2n is automorphic with the Moebius graph M2n. More information can be found in [1, 12, 18, 25] and Figure 1. Here, we have the following theorems, which are main results in this work.
Theorem 1. Let G be the Harary graph H2r+1,2n for given positive integer number r and n. Then, the Hosoya polynomial of H2r+1,2n is
(4)
Proof. Consider the Harary graph G=H2r+1,2n as order 2n (=|V(H2r+1,2n)|). From definition of the Harary graph, this implies that for all two vertices if and only if i−r ≤ j ≤ i+r or |j-i|=n (∀i,j=1,2,…,n), thus the coefficient of the first term in the Hosoya polynomial of G ( x1 ) is equal to |E(H2r+1,2n)|=2rn+n.
On the other hand from the structure of H2r+1,2n, ∀i,j∊ℤ2n & |i-j|≤r or |i-j|=n d(vi,vi±(r+j))= d(vi,vi+n±j)=2, since for a vertex vi∊V(H2r+1,2n), vi,vj, vi,vi±r, vi,vi+n, vi±rvi±r+j and vi+n,vi+n±j belong to E(H2r+1,2n). Hence the coefficient of the second term in H(H2r+1,2n,x) is 4n.
Also by similar argument, one can see that for all vertices of G, d(vi,vi±(dr+j)) and d(vi,vi+n±((d-1)r+j)) are equal to d+1, where This implies that the diameter of Harary graph H2r+1,2n will be It is easy to see that the latest coefficient in H(H2r+1,2n,x) is equal to
Therefore by using the definition of Hosoya polynomial, we have
And this complete the proof of Theorem 1.
According to Equation 3, we can obtain the Wiener index and the hyper-Wiener index of the Harary graph H2r+1,2n by the Hosoya polynomial.
Theorem 2. Let H2r+1,2n be the Harary graph (∀r,n∊ℤ & n≥r+1). Then, the Wiener index of H2r+1,2n is equal to
Proof. Consider the Harary graph G= H2r+1,2n. From definitions of the Wiener index and Hosoya Polynomial of G (Equations 1 and 3), we see that the Wiener index W(G) is the first derivative of the Hosoya polynomial H(G,x) evaluated at x=1. Thus
Here the proof of Theorem 2 is completed.
As an immediately result from Theorem 2, we have.
Theorem 3. For given positive integer numbers r and n (n≥r+1), the hyper-Wiener index of the Harary graph H2r+1,2n is equal to
Proof. Let H2r+1,2n be the Harary graph (∀r,n∊ℤ & n≥r+1) . According to Equation 2, we can compute the hyper-Wiener index of H2r+1,2n as follows:

ACKNOWLEDGEMENTS

Authors are also thankful to the University Grants Commission, Government of India, for the financial support under the GrantMRP(S)-0535/13-14/KAMY004/UGC-SWRO.

References

[1]  H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), 17–20.
[2]  H. Wiener, Relations of the physical properties of the isomeric alkanes to molecular structure: surface tension, specific dispersion, and critical solution temperature in aniline, J. Phys. Chem. 52 (1948), 1082–1089.
[3]  M. Randić, Novel molecular descriptor for structure-property studies. Chem. Phys. Lett., 211, (1993), 478.
[4]  M. Randić, X. Gou, T. Oxley, H. Krishnapriyan, and L. Naylor. Wiener matrix invariants. J. Chem. Inf. Comput. Sci., 34, (1994) 361.
[5]  H. Hosoya. On some counting polynomials in chemistry. Discrete Appl. Math. 19, (1989), 239-257.
[6]  A.A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: Theory and applications, Acta Appl. Math. 66 (2001), 211–249.
[7]  I. Gutman, Y.N. Yeh, Y.N. Lee and Y.L. Lau, Some recent results in the theory of the Wiener number, Ind. J. Chem 32 (1993), 551–661.
[8]  Gutman, Hosoya polynomial and the distance of the total graph of a tree. Publikacije Elektrotehnickog Fakulteta, Univerzitetu Beogradu. 10, (1999) 53.
[9]  Gutman and S. Klavžar. A method for Calculating Wiener numbers of benzenoid hydrocarbons and phenylenes. ACH Models Chem. 133, (1996), 389-399.
[10]  D.J. Klein, I. Lukovits, I. Gutman, On the definition of the hyper-Wiener index for cycle-containing structures, J. Chem. Inf. Comput. Sci. 35 (1995), 50–52.
[11]  S. Nikolić, N. Trinajstić and Z. Mihalić. The Wiener index: Development and applications, Croat. Chem. Acta. 68 (1995), 105–129.
[12]  A. Iranmanesh and Y. Alizadeh, Computing Hyper-Wiener and Schultz Indices of TUZC6[p;q] Nanotube By Gap Program. Digest. J. Nanomater. Bios. 4(1), (2009), 607-611.
[13]  A.R. Ashrafi and H. Shabani. The Hosoya Polynomial of TUC4C8(S) Nanotubes. Digest. J. Nanomater. Bios. 4(3), (2009), 453-457.
[14]  M.V. Diudea. Hosoya polynomial in Tori. MATCH Commun. Math. Comput. Chem. 45, (2002), 109-122.
[15]  W.C. Shiu and P.C.B. Lam. The Wiener number of a hexagonal net. Discrete Appl. Math. 73, (1997), 101-111.
[16]  Sh. Xu and H. Zhang. Generalized Hosoya Polynomials of Hexagonal Chains. J. Math. Chem. 43, (2008), 2.
[17]  W. Yan, B-Y. Yang and Y-N. Yeh, The behaviour of Wiener indices and polynomials of graphs under five graph decorations, Appl. Math. Lett. 20 (2007), 290–295.
[18]  B.Y. Yang and Y.N. Yeh, A Crowning Moment for Wiener Indices, Stud. Appl. Math. 112 (2004), 333–340.
[19]  P. Žigert, S. Klavžar and I. Gutman. Calculating the hyper-Wiener index of benzenoid hydrocarbons. ACH Models Chem. 137, (2000), 83-94.
[20]  B. Zhou and I. Gutman. Relations Between Wiener, Hyper-Wiener and Zagreb Indices. Chem. Physics Letters. 394, (2004), 93-95.
[21]  B. West, Introduction to graph theory. Prentice Hall of India, (2003).
[22]  H. Abdollahzadeh Ahangar and L. Pushpalatha. On the Chromatic Number of Some Harary Graphs, Int. Math. Forum, 4(31), (2009), 1511-1514.
[23]  A.P. Kazemi. Chromatic Numbers in Some Graphs. International Mathematical Forum, 2(35), (2007), 1723-1727.
[24]  M. Farahani. Hosoya polynomial, Wiener and Hyper-Wiener indices of some regular graphs. Informatics Engineering, an International Journal (IEIJ), 1(1), December, (2013), 9-13.