Advanced
MULTIPLICATIVELY WEIGHTED HARARY INDICES OF GRAPH OPERATIONS
MULTIPLICATIVELY WEIGHTED HARARY INDICES OF GRAPH OPERATIONS
Journal of Applied Mathematics & Informatics. 2015. Jan, 33(1_2): 89-100
Copyright © 2015, Korean Society of Computational and Applied Mathematics
  • Received : August 27, 2013
  • Accepted : August 06, 2014
  • Published : January 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
K. PATTABIRAMAN

Abstract
In this paper, we present exact formulae for the multiplica-tively weighted Harary indices of join, tensor product and strong product of graphs in terms of other graph invariants including the Harary index, Zagreb indices and Zagreb coindices. Finally, We apply our result to com-pute the multiplicatively weighted Harary indices of fan graph, wheel graph and closed fence graph. AMS Mathematics Subject Classification : 05C12, 05C76.
Keywords
1. Introduction
All the graphs considered in this paper are simple and connected. For vertices u, v V ( G ), the distance between u and v in G , denoted by dG ( u, v ), is the length of a shortest ( u, v )-path in G and let dG ( v ) be the degree of a vertex v V ( G ). For two simple graphs G and H their tensor product , denoted by G × H , has vertex set V ( G ) × V ( H ) in which ( g 1 , h 1 ) and ( g 2 , h 2 ) are adjacent whenever g 1 g 2 is an edge in G and h 1 h 2 is an edge in H . Note that if G and H are connected graphs, then G × H is connected only if at least one of the graph is nonbipartite. The strong product of graphs G and H , denoted by G H , is the graph with vertex set V ( G ) × V ( H ) = {( u, v ) : u V ( G ), v V ( H )} and ( u, x )( v, y ) is an edge whenever ( i ) u = v and xy E ( H ), or ( ii ) uv E ( G ) and x = y , or ( iii ) uv E ( G ) and xy E ( H ), see Fig.1 .
PPT Slide
Lager Image
Tensor and strong product of C3 and P3
The join G + H of graphs G and H is obtained from the disjoint union of the graphs G and H , where each vertex of G is adjacent to each vertex of H .
A topological index of a graph is a real number related to the graph; it does not depend on labeling or pictorial representation of a graph. In theoretical chemistry, molecular structure descriptors (also called topological indices) are used for modeling physicochemical, pharmacologic, toxicologic, biological and other properties of chemical compounds [11] . There exist several types of such indices, especially those based on vertex and edge distances. One of the most intensively studied topological indices is the Wiener index; for other related topological indices see [31] .
Let G be a connected graph. Then Wiener index of G is defined as
PPT Slide
Lager Image
with the summation going over all pairs of distinct vertices of G . Similarly, the Harary index of G is defined as
PPT Slide
Lager Image
The Harary index of a graph G has been introduced independently by Plavsic et al. [20] and by Ivanciuc et al. [16] in 1993. Its applications and mathematical properties are well studied in [?, 32 , 19] . Zhou et al. [33] have obtained the lower and upper bounds of the Harary index of a connected graph. Very recently, Xu et al. [28] have obtained lower and upper bounds for the Harary index of a connected graph in relation to χ ( G ), chromatic number of G and ω ( G ), clique number of G . and characterized the extremal graphs that attain the lower and upper bounds of Harary index. Various topological indices on tensor product, Cartesian product and strong product have been studied various authors, see [2 , 29 , 30 , 4 , 21 , 22 , 23 , 17 , 13] .
Dobrynin and Kochetova [5] and Gutman [12] independently proposed a vertex-degree-weighted version of Wiener index called degree distance or Schultz molecular topological index, which is defined for a connected graph G as
PPT Slide
Lager Image
where dG ( u ) is the degree of the vertex u in G . Note that the degree distance is a degree-weight version of the Wiener index. Hua and Zhang [14] introduced a new graph invariant named reciprocal degree distance, which can be seen as a degree-weight version of Harary index, that is,
PPT Slide
Lager Image
Similarly, the modified Schultz molecular topological index or Gutman index is defined as
PPT Slide
Lager Image
In Su et.al. [26] introduce the multiplicatively weighted Harary indices or reciprocal product-degree distance of graphs, which can be seen as a product -degree-weight version of Harray index
PPT Slide
Lager Image
Hua and Zhang [14] have obtained lower and upper bounds for the reciprocal degree distance of graph in terms of other graph invariants including the degree distance, Harary index, the first Zagreb index, the first Zagreb coindex, pendent vertices, independence number, chromatic number and vertex and edgeconnectivity. Pattabiraman and Vijayaragavan [24 , 25] have obtained the exact expression for the reciprocal degree distance of join, tensor, strong and wreath product of graphs.
The first Zagreb index and second Zagerb index are defined as
PPT Slide
Lager Image
In fact, one can rewrite the first Zagreb index as
PPT Slide
Lager Image
Similarly, the first Zagreb coindex and second Zagerb coindex are defined as
PPT Slide
Lager Image
The Zagreb indices are found to have appilications in QSPR and QSAR studies as well, see [6] . For the survey on theory and application of Zagreb indices see [10] . Feng et al. [9] have given a sharp bounds for the Zagreb indices of graphs with a given matching number. Khalifeh et al. [18] have obtained the Zagreb indices of the Cartesian product, composition, join, disjunction and symmetric difference of graphs. Ashrafi et al. [3] determined the extremal values of Zagreb coindices over some special class of graphs. Hua and Zhang [15] have given some relations between Zagreb coindices and some other topolodical indices. Ashrafi et al. [1] have obtained the Zagreb indices of the Cartesian product, composition, join, disjunction and symmetric difference of graphs.
A path, cycle and complete graph on n vertices are denoted by Pn , Cn and Kn , respectively. We call C 3 a triangle. In this paper, we present exact formulae for the multiplicatively weighted Harary indices of join, tensor product and strong product of graphs in terms of other graph invariants including the Harary index, Zagreb indices and Zagreb coindices. Finally, We apply our result to compute the multiplicatively weighted Harary indices of fan graph, wheel graph and closed fence graph.
2. Multiplicatively weighted Harary index ofG1+G2
In this section, we compute the Multiplicatively Weighted Harary Index of join of two graphs.
Theorem 2.1. Let G 1 and G 2 be graphs with n and m vertices p and q edges, respectively. Then
PPT Slide
Lager Image
Proof . Set V ( G 1 ) = { u 1 , u 2 , . . . , un } and V ( G 2 ) = { v 1 , v 2 , . . . , vm }. By definition of the join of two graphs, one can see that,
PPT Slide
Lager Image
Therefore,
PPT Slide
Lager Image
Using Theorem 2.1, we have the following corollaries.
Corollary 2.2. Let G be graph on n vertices and p edges. Then
PPT Slide
Lager Image
Let Kn,m be the bipartite graph with two partitions having n and m vertices. Note that
PPT Slide
Lager Image
Corollary 2.3.
PPT Slide
Lager Image
One can observe that M 1 ( Cn ) = 4 n , n ≥ 3, M 1 ( P 1 ) = 0, M 1 ( Pn ) = 4 n − 6, n > 1 and M 1 ( Kn ) = n ( n − 1) 2 . Similarly,
PPT Slide
Lager Image
By direct calculations we obtain the second Zagreb indices and coindices of Pn and Cn .
PPT Slide
Lager Image
Using Corollary 2.2, we compute the formulae for reciprocal degree distance of star, fan and wheel graphs,
PPT Slide
Lager Image
see Fig.2 .
PPT Slide
Lager Image
Fan graph and wheel graph
Example 1.
PPT Slide
Lager Image
3. Multiplicatively weighted Harary index of tensor product of graphs
In this section, we compute the Multiplicatively weighted Harary index of G × Kr .
The proof of the following lemma follows easily from the properties and structure of G × Kr . The lemma is used in the proof of the main theorem of this section.
Lemma 3.1. Let G be a connected graph on n ≥ 2 vertices. For any pair of vertices xij , xkp V ( G × Kr ), r ≥ 3, i, k ∈ {1, 2, . . . , n } j, p ∈ {1, 2, . . . , r }. Then
( i ) If uiuk E ( G ), then
PPT Slide
Lager Image
( ii ) If uiuk E ( G ), then d G×Kr ( xij , xkp ) = dG ( ui, uk ).
( iii ) d G×Kr ( xij , xip ) = 2.
Proof . Let V ( G ) = { u 1 , u 2 , . . . , un } and V ( Kr ) = { v 1 , v 2 , . . . , vr } . Let xij denote the vertex ( ui, vj ) of G × Kr . We only prove the case when uiuk E ( G ), i k and j = p . The proofs for other cases are similar.
We may assume j = 1. Let P = ui us 1 us 2 . . . usp uk be the shortest path of ength p + 1 between ui and uk in G . From P we have a ( xi 1 , xk 1 )-path P 1 = xi 1 xs 1 2 . . . x sp -1 2 x sp 3 xk 1 if the length of P is odd, and P 1 = xi 1 xs 1 2 . . . x sp -1 2 x sp 2 xk 1 if the length of P is even.
Obviously, the length of P 1 is p + 1, and thus dG × Kr ( xi 1 , xk 1 ) ≤ p + 1 ≤ dG ( ui, uk ). If there were a ( xi 1 , xk 1 )-path in G × Kr that is shorter than p + 1 then it is easy to find a ( ui, uk )-path in G that is also shorter than p + 1 in contrast to dG ( ui, uk ) = p + 1. □
Theorem 3.2. Let G be a connected graph with n ≥ 2 vertices and m edges. Then
PPT Slide
Lager Image
Proof . Set V ( G ) = { u 1 , u 2 , . . . , un } and V ( Kr ) = { v 1 , v 2 , . . . , vr }. Let xij denote the vertex ( ui, vj ) of G × Kr . The degree of the vertex xij in G × Kr is dG ( ui ) dKr ( vj ), that is dG×Kr ( xij ) = ( r − 1) dG ( ui ). By the definition of multiplicatively weighted Harary index
PPT Slide
Lager Image
where A 1 to A 3 are the sums of the above terms, in order.
We shall calculate A 1 to A 3 of (1) separately.
( A 1 ) First we compute
PPT Slide
Lager Image
PPT Slide
Lager Image
( A 2 ) Next we compute
PPT Slide
Lager Image
Let E 1 = { uv E ( G ) | uv is on a C 3 in G } and E 2 = E ( G ) − E 1 .
PPT Slide
Lager Image
Now summing (3) over j = 0, 1, . . . , r − 1, we get,
PPT Slide
Lager Image
( A 3 ) Next we compute
PPT Slide
Lager Image
PPT Slide
Lager Image
Using (1) and the sums A 1 , A 2 and A 3 in (2),(4) and (5), respectively, we have,
PPT Slide
Lager Image
Using Theorem 3.2, we have the following corollaries.
Corollary 3.3. Let G be a connected graph on n ≥ 2 vertices with m edges. If each edge of G is on a C 3 , then
PPT Slide
Lager Image
For a triangle free graph
PPT Slide
Lager Image
Corollary 3.4. If G is a connected triangle free graph on n ≥ 2 vertices and m edges, then
PPT Slide
Lager Image
By direct calculations we obtain expressions for the values of the Harary indices of Kn and Cn .
PPT Slide
Lager Image
when n is even, and
PPT Slide
Lager Image
otherwise. Similarly,
PPT Slide
Lager Image
Using Corollaries 3.3 and 3.4, we obtain the multiplicatively weighted Harary indices of the graphs Kn × Kr and Cn × Kr .
Example 2. ( i )
PPT Slide
Lager Image
( ii )
PPT Slide
Lager Image
4. Multiplicatively weighted Harary index of strong product of graphs
In this section, we obtain the multiplicatively weighted Harary index of G Kr .
Theorem 4.1. Let G be a connected graph with n vertices and m edges. Then
PPT Slide
Lager Image
Proof . Set V ( G ) = { u 1 , u 2 , . . . , un } and V ( Kr ) = { v 1 , v 2 , . . . , vr }. Let xij denote the vertex ( ui, vj ) of G Kr . The degree of the vertex xij in G Kr is dG ( ui ) + dKr ( vj ) + dG ( ui ) dKr ( vj ), that is d G Kr ( xij ) = rdG ( ui ) + ( r − 1). One can see that for any pair of vertices xij , xkp V ( G Kr ), d G Kr ( xij , xip ) = 1 and d G Kr ( xij , xkp ) = dG ( ui , uk ).
PPT Slide
Lager Image
where A 1 , A 2 and A 3 are the sums of the terms of the above expression, in order. We shall obtain A 1 to A 3 of (6), separately.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Using (7), (8) and (9) in (6), we have
PPT Slide
Lager Image
Using Theorem 4.1, we obtain the following corollary.
Corollary 4.2.
PPT Slide
Lager Image
As an application we present formula for multiplicatively weighted Harary index of closed fence graph, Cn K 2 , see Fig. 3 .
PPT Slide
Lager Image
Closed fence graph
Example 3. By Corolarry 4.2, we have
PPT Slide
Lager Image
BIO
K. Pattabiraman received M.Sc. and Ph.D. from Annamalai University. Since 2006 he has been at Annamalai University. His research interests include Graph Theory and Mathematical Chemistry.
Department of Mathematics, Faculty of Engineering and Technology, Annamalai University Annamalainagar-608 002.
e-mail: pramank@gmail.com
References
Ashrafi A.R. , Doslic T. , Hamzeha A. (2010) The Zagreb coindices of graph operations Discrete Appl. Math. 158 1571 - 1578    DOI : 10.1016/j.dam.2010.05.017
Alizadeh Y. , Iranmanesh A. , Doslic T. (2013) Additively weighted Harary index of some com-posite graphs Discrete Math. 313 26 - 34    DOI : 10.1016/j.disc.2012.09.011
Ashrafi A.R. , Doslic T. , Hamzeha A. (2011) Extremal graphs with respect to the Zagreb coindices MATCH Commun. Math.Comput. Chem. 65 85 - 92
Doslic T. (2008) Vertex-weighted Wiener polynomials for composite graphs Ars Math. Contemp. 1 66 - 80
Dobrynin A.A. , Kochetova A.A. (1994) Degree distance of a graph: a degree analogue of the Wiener index J. Chem. Inf. Comput. Sci. 34 1082 - 1086    DOI : 10.1021/ci00021a008
Devillers J. , Balaban A.T. 1999 Topological indices and related descriptors in QSAR and QSPR Gordon and Breach Amsterdam, The Netherlands
Das K.C. , Zhou B. , Trinajstic N. (2009) Bounds on Harary index J. Math. Chem. 46 1369 - 1376    DOI : 10.1007/s10910-009-9520-x
Das K.C. , Xu K. , Cangul I.N. , Cevik A.S. , Graovac A. (2013) On the Harary index of graph operations J. Inequal. Appl. 339 -    DOI : 10.1186/1029-242X-2013-339
Feng L. , Llic A. (2010) Zagreb, Harary and hyper-Wiener indices of graphs with a given matching number Appl. Math. Lett. 23 943 - 948    DOI : 10.1016/j.aml.2010.04.017
Gutman I. , Das K.C. (2004) The first Zagerb index 30 years after MATCH Commun. Math. Comput. Chem. 50 83 - 92
Gutman I. , Polansky O.E. 1986 Mathematical Concepts in Organic Chemistry Springer-Verlag Berlin
Gutman I. (1994) Selected properties of the Schultz molecular topogical index J. Chem. Inf. Comput. Sci. 34 1087 - 1089    DOI : 10.1021/ci00021a009
Hoji M. , Luo Z. , Vumar E. (2010) Wiener and vertex PI indices of kronecker products of graphs Discrete Appl. Math. 158 1848 - 1855    DOI : 10.1016/j.dam.2010.06.009
Hua H. , Zhang S. (2012) On the reciprocal degree distance of graphs Discrete Appl. Math. 160 1152 - 1163    DOI : 10.1016/j.dam.2011.11.032
Hua H. , Zhang S. Relations between Zagreb coindices and some distance-based topo-logical indices MATCH Commun. Math.Comput. Chem. in press
Ivanciuc O. , Balaban T.S. (1993) Reciprocal distance matrix, related local vertex invariants and topological indices J. Math. Chem. 12 309 - 318    DOI : 10.1007/BF01164642
Khalifeh M.H. , Youseri-Azari H. , Ashrafi A.R. (2008) Vertex and edge PI indices of Cartesian product of graphs Discrete Appl. Math. 156 1780 - 1789    DOI : 10.1016/j.dam.2007.08.041
Khalifeh M.H. , Yousefi-Azari H. , Ashrafi A. R. (2009) The first and second Zagreb indices of some graph operations Discrete Appl. Math. 157 804 - 811    DOI : 10.1016/j.dam.2008.06.015
Lucic B. , Milicevic A. , Nikolic S. , Trinajstic N. (2002) Harary index-twelve years later Croat. Chem. Acta 75 847 - 868
Plavsic D. , Nikolic S. , Trinajstic N. , Mihalic Z. (1993) On the Harary index for the charac-terization of chemical graphs J. Math. Chem. 12 235 - 250    DOI : 10.1007/BF01164638
Pattabiraman K. , Paulraja P. (2012) On some topological indices of the tensor product of graphs Discrete Appl. Math. 160 267 - 279    DOI : 10.1016/j.dam.2011.10.020
Pattabiraman K. , Paulraja P. (2012) Wiener and vertex PI indices of the strong product of graphs Discuss. Math. Graph Thoery 32 749 - 769    DOI : 10.7151/dmgt.1647
Pattabiraman K. , Paulraja P. (2011) Wiener index of the tensor product of a path and a cycle Discuss. Math. Graph Thoery 31 737 - 751    DOI : 10.7151/dmgt.1576
Pattabiraman K. , Vijaragavan M. (2013) Reciprocal degree distance of some graph operations Trans. Combin. 2 13 - 24
Pattabiraman K. , Vijaragavan M. Reciprocal degree distance of product graphs Dis-crete Appl. Mathematics.
Su G. , Gutman I. , Xiong L. , Xu L. Reciprocal product degree distance of graphs, Manuscript
Wang H. , Kang L. (2013) More on the Harary index of cacti J. Appl. Math. Comput. 43 369 - 386    DOI : 10.1007/s12190-013-0668-y
Xu K. , Das K.C. (2011) On Harary index of graphs Dis. Appl. Math. 159 1631 - 1640    DOI : 10.1016/j.dam.2011.06.003
Xu K. , Das K.C. , Hua H. , Diudea M.V. (2013) Maximal Harary index of unicyclic graphs with given matching number Stud. Univ. Babes-Bolyai Chem. 58 71 - 86
Xu K. , Wang J. , Liu H. The Harary index of ordinary and generalized quasi-tree graphs J. Appl. Math. Comput.    DOI : 10.1007/s12190-013-0727-4
Yousefi-Azari H. , Khalifeh M.H. , Ashrafi A.R. (2011) Calculating the edge Wiener and edge Szeged indices of graphs J. Comput. Appl. Math. 235 4866 - 4870    DOI : 10.1016/j.cam.2011.02.019
Zhou B. , Du Z. , Trinajstic N. (2008) Harary index of landscape graphs Int. J. Chem. Model. 1 35 - 44
Zhou B. , Cai X. , Trinajstic N. (2008) On the Harary index J. Math. Chem. 44 611 - 618    DOI : 10.1007/s10910-007-9339-2