文章快速检索 高级检索
 浙江大学学报(理学版)  2017, Vol. 44 Issue (3): 253-260, 280  DOI:10.3785/j.issn.1008-9497.2017.03.001 0

### citing the article as [复制中英文]

WEN Yanqing, LIU Baoliang, AN Mingqiang. Multiplicatively weighted Harary index of some graph operations[J]. Journal of Zhejiang University(Science Edition), 2017, 44(3): 253-260, 280. DOI: 10.3785/j.issn.1008-9497.2017.03.001.
[复制英文]

[复制中文]

### Fundation item

Supported by the Doctoral Scientific Research Foundation of Shanxi Datong University (2015-B-06)

### About the author

WEN Yanqing(1980-), ORCID:http://orcid.org/0000-0002-9573-7245, female, doctoral student, lecture, the field of interest are reliability and graph theory, E-mail: oryqwen@163.com

### Corresponding author

AN Mingqiang, ORCID:http://orcid.org/0000-0002-1105-750X, E-mail:anmq@tust.edu.cn

### Article History

Received Date: October 16, 2015
Multiplicatively weighted Harary index of some graph operations
WEN Yanqing1 , LIU Baoliang1 , AN Mingqiang2
1. College of Mathematics and Computer Science, Shanxi Datong University, Datong 037009, Shanxi Province, China;
2. College of Science, Tianjin University of Science and Technology, Tianjin 300457, China
Received Date: October 16, 2015
Fundation item: Supported by the Doctoral Scientific Research Foundation of Shanxi Datong University (2015-B-06)
*Corresponding author: AN Mingqiang, ORCID:http://orcid.org/0000-0002-1105-750X, E-mail:anmq@tust.edu.cn
Abstract: Recently, ALIZADEH et al proposed a modification of the Harary index in which the contributions of vertex pairs were weighted by the product of their degrees. It is named multiplicatively weighted Harary index and defined as: ${H_M}\left( G \right) = \sum\limits_{u \ne v} {\frac{{{\delta _G}\left( u \right){\delta _G}\left( v \right)}}{{{d_G}\left( {u,v} \right)}}}$, where δG(u) denotes the degree of the vertex u in the graph G and dG(u, v) denotes the distance between two vertices u and v in the graph G. In this paper, the explicit formulae for the multiplicatively weighted Harary index of tensor product G×Kr, the strong product GKr and the wreath product G1oG2 in terms of other graph invariants including additively weighted Harary index, Harary index, the first and the second Zagreb indices and the first and the second Zagreb coindices, are obtained, where Kr is the complete graph. Additionally, we apply our results to compute the multiplicatively weighted Harary index of open fence and closed fence graphs.
Key words: multiplicatively weighted Harary index    Harary index    tensor product    strong product    wreath product

1. 山西大同大学 数学与计算机科学学院, 山西 大同 037009;
2. 天津科技大学 理学院, 天津 300457

0 Introduction

All graphs considered in this paper are finite undirected simple connected graphs. Let G=(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). Let δG(v) be the degree of a vertex v in G and dG(u, v) be the distance between two vertices u and v in G. When the graph is clear from the context, we will omit the subscript G from the notation. For other undefined terminology and notations from graph theory, the readers are referred to[1].

A topological index is a number related to a graph invariant under graph isomorphism. Obviously, the number of vertices and edges of a given graph G are topological indices of G. One of the oldest and well-studied distance-based topological index is the Wiener number W(G), also termed as Wiener index in chemical or mathematical chemistry literature, which is defined as the sum of distances over all unordered vertex pairs in G[2], namely,

 $W\left( G \right) = \sum\limits_{u \ne v} {{d_G}\left( {u,v} \right)} .$

This formula was introduced by HOSOYA [3], although the concept has been introduced by later WIENER. However, the approach by WIENER is applicable only to acyclic structures, whilst HOSOYA'S matrix definition allowed the Wiener index to be used for any structure.

Another distance-based graph invariant, defined by [4-5] in a fully analogous manner to Wiener index, is the Harary index, which is equal to the sum of reciprocal distances over all unordered vertex pairs in G, that is,

 $H\left( G \right) = \sum\limits_{u \ne v} {\frac{1}{{{d_G}\left( {u,v} \right)}}} .$

In 1994, DOBRYNIN et al[6] and GUTMAN[7] independently proposed a vertex-degree-weighted version of Wiener index called degree distance or Schultz molecular topological index, which is defined for a graph G as

 $D{D_A}\left( G \right) = \sum\limits_{u \ne v} {\left( {{\delta _G}\left( u \right) + {\delta _G}\left( v \right)} \right){d_G}\left( {u,v} \right)} .$

Similarly, the Gutman index is put forward in [7] and called there the Schultz index of the second kind, for which the name Gutman index has also sometimes been used[8]. It is defined as

 $D{D_M}\left( G \right) = \sum\limits_{u \ne v} {{\delta _G}\left( u \right){\delta _G}\left( v \right){d_G}\left( {u,v} \right)} .$

The interested readers may consult [9-11] for Wiener index, [5] for Harary index, [12-13] for degree distance and [14-15] for Gutman index.

Although Harary index is not well known in the mathematical chemistry community, it arises in the study of complex networks. Let n denote the number of vertices of G. Dividing H(G) by n(n-1), we obtain a normalization of H(G), which is called the efficiency of G[16]. The reciprocal value of the efficiency is called the performance of G[17]. For a given network, both efficiency and performance afford a uniform way to express and quantify the small-world property. Since the strength of interactions between nodes in a network is seldom properly described by their topological distances, one needs to consider both the weighted versions of efficiency and performance.

In order to close the gap between the two research communities by drawing their attention to a generalization of a concept, which gives more weight to the contributions of pairs of vertices of high degrees. Recently, ALIZADEH et al[18] introduced an invariant, named additively weighted Harary index, which is defined as

 ${H_{\rm{A}}}\left( G \right) = \sum\limits_{u \ne v} {\frac{{{\delta _G}\left( u \right) + {\delta _G}\left( v \right)}}{{{d_G}\left( {u,v} \right)}}} .$

Some basic mathematical properties of this index were established[18] and their behavior under several standard graph products were investigated there.

It is known that the intuitive idea of pairs of close atoms contributing more than the distant ones is difficult to capture in topological indices. A possibly useful approach could be used to replace the additive weighting of pairs by the multiplicative one, thus giving rise to a new invariant, named multiplicatively weighted Harary index[18]:

 ${H_{\rm{M}}}\left( G \right) = \sum\limits_{u \ne v} {\frac{{{\delta _G}\left( u \right){\delta _G}\left( v \right)}}{{{d_G}\left( {u,v} \right)}}} .$

Evidently, the additively (resp. multiplicatively) weighted Harary index is related to the Harary index in the same way as the degree distance (resp. Gutman index) is related to the Wiener index.

Very recently, PATTABIRAMAN et al[19] gave the exact formulae for the additively weighted Harary index of tensor product G×Km0, m1, …, mr-1 and the strong product GKm0, m1, …, mr-1, where Km0, m1, …, mr-1 is the complete multipartite graph with partite sets of sizes m0, m1, …, mr-1.

In this paper, we continue this program to the multiplicatively weighted Harary index, and the exact formulae for the multiplicatively weighted Harary index of tensor product G×Kr, the strong product GKr and the wreath product G1oG2 in terms of other graph invariants including additively weighted Harary index, Harary index, the first and the second Zagreb indices, and the first and the second Zagreb coindices, are obtained, where Kr is the complete graph. Additionally, we apply our results to compute the multiplicatively weighted Harary index of open fence and closed fence graphs.

The paper is organized as follows. In section 1, we give some necessary definitions. In section 2 to 4, we present our main results and give some corresponding examples, respectively.

1 Preliminaries 1.1 Some definitions

For a given graph G, its first and second Zagreb indices are defined as follows:

 $\begin{array}{l} {M_1}\left( G \right) = \sum\limits_{u \in V\left( G \right)} {\delta {{\left( u \right)}^2}} ,\\ {M_2}\left( G \right) = \sum\limits_{e = uv \in E\left( G \right)} {\delta \left( u \right)\delta \left( v \right)} . \end{array}$

The first Zagreb index can be also expressed as a sum over edges of G,

 ${M_1}\left( G \right) = \sum\limits_{e = uv \in E\left( G \right)} {\left( {\delta \left( u \right) + \delta \left( v \right)} \right)} .$

For the proof of this fact and more information on Zagreb indices, we encourage the interested reader to [20].

The first and the second Zagreb coindices of a graph G are defined as follows[21]:

 $\begin{array}{*{20}{c}} {{{\bar M}_1}\left( G \right) = \sum\limits_{e = uv \notin E\left( G \right)} {\left( {\delta \left( u \right) + \delta \left( v \right)} \right)} ,}\\ {{{\bar M}_2}\left( G \right) = \sum\limits_{e = uv \notin E\left( G \right)} {\delta \left( u \right)\delta \left( v \right)} .} \end{array}$

Let Kn, Cn and Pn denote the n-vertex complete graph, cycle and path, respectively. We call C3 a triangle.

1.2 Product graphs

Now, we introduce three standard types of product graphs that we consider in this paper. For two simple graphs G and H, their tensor product denoted by G×H, has vertex set V(GV(H) in which (g1, h1) and (g2, h2) are adjacent whenever g1g2 is an edge in G and h1h2 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(GV(H)={(u, v):uV(G), vV(H)} and (u, x)(v, y) is an edge whenever (ⅰ)u=v and xyE(H), or (ⅱ) uvE(G) and x=y, or (ⅲ) uvE(G) and xyE(H). Similarly, the wreath product (also known as the composition) of the graphs G and H, denoted by GoH, has vertex set V(GV(H) in which (g1, h1)(g2, h2) is an edge whenever g1g2E(G), or g1=g2 and h1h2E(H). The tensor product of graphs has been extensively studied in relation to the areas such as graph colorings, graph recognition, decompositions of graphs, and design theory, see [22-26].

For more information about graph products, please see monograph[25]. There is a growing corpus of literature concerned with the study of graph invariants of tensor product, Cartesian product and strong product[27-29].

2 Multiplicatively weighted Hararyindex of tensor product of graphs

Let G be a connected graph with V(G)={v0, v1, …, vn-1} and V(Kr)={u1, u2, …, ur-1}. For convenience, let xij denote the vertex (vi, uj) of G×Kr. The following lemma, which follows easily from the properties and structure of G×Kr, is used in the proof of our main result in this section.

Lemma 1 Let G be a connected graph on n≥2 vertices and xij, xkp be any pair vertices of the graph G′=G×Kr, where r≥3.

(ⅰ)If vivkE(G), then

 $\begin{array}{l} {d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right) = \\ \;\;\;\left\{ \begin{array}{l} 1,\;\;\;\;\;{\rm{if}}\;j \ne p,\\ 2,\;\;\;\;\;{\rm{if}}\;j \ne p,\;and\;{v_i}{v_k}\;{\rm{is}}\;{\rm{on}}\;{\rm{a}}\;{\rm{triangle}}\;{\rm{of}}\;G,\\ 3,\;\;\;\;\;{\rm{if}}\;j \ne p,\;and\;{v_i}{v_k}\;{\rm{is}}\;{\rm{not}}\;{\rm{on}}\;{\rm{a}}\;{\rm{triangle}}\;{\rm{of}}\;G. \end{array} \right. \end{array}$

(ⅱ)If vivk$\notin$E(G), then dG(xij, xkp)=dG(vi, vk).

(ⅲ)dG(xij, xip)=2.

Lemma 2 Let G be a connected graph and let G′=G×Kr. Then the degree of a vertex (vi, uj) in G′ is δG((vi, uj))=δG(vi)(r-1).

Now, we present the exact formulae for the multiplicatively weighted Harary index of G×Kr.

Theorem 1 Let G be a connected graph with n≥2 vertices and E2 be the set of edges of G which do not lie on any triangle of it. Then

 $\begin{array}{l} {H_M}\left( {G \times {K_r}} \right) = r{\left( {r - 1} \right)^2}\left( {r{H_M}\left( G \right) + \frac{1}{4}\left( {r - 1} \right){M_1}\left( G \right) - } \right.\\ \;\;\;\;\;\;\;\;\;\;\left. {\left( {\frac{{{M_2}\left( G \right)}}{2} + \frac{1}{{12}}\sum\limits_{{v_i}{v_k} \in {E_2}} {{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)} } \right)} \right), \end{array}$

where r≥3.

Proof Let us denote G′=G×Kr. Obviously,

 $\begin{array}{l} {H_M}\left( {G'} \right) = \frac{1}{2}\sum\limits_{{x_{ij}},{x_{kp}} \in V\left( {G'} \right)} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{2}\left( {\sum\limits_{i = 0}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{ip}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{ip}}} \right)}}} } + } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\sum\limits_{j = 0}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} } + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} } } \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{2}\left\{ {{A_1} + {A_2} + {A_3}} \right\}, \end{array}$ (1)

where A1 to A3 are the sums of the above terms, in order. In what follows, we compute A1 to A3 of (1), separately.

First, we compute $\sum\limits_{i=0}^{n-1}{\sum\limits_{\begin{smallmatrix} j,p=0 \\ j\ne p \end{smallmatrix}}^{r-1}{\frac{{{\delta }_{{{G}'}}}\left( {{x}_{ij}} \right){{\delta }_{{{G}'}}}\left( {{x}_{ip}} \right)}{{{d}_{{{G}'}}}\left( {{x}_{ij}},{{x}_{ip}} \right)}}}.$

 $\begin{array}{l} {A_1} = \sum\limits_{i = 0}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{ip}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{ip}}} \right)}}} } = \\ \;\;\;\;\;\;\;\;\sum\limits_{i = 0}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _G}\left( {{v_i}} \right)\left( {r - 1} \right) \cdot {\delta _G}\left( {{v_i}} \right)\left( {r - 1} \right)}}{2}} } = \\ \;\;\;\;\;\;\;\;\frac{1}{2}r{\left( {r - 1} \right)^3}{M_1}\left( G \right),{\rm{by}}\;{\rm{lemmas}}\;{\rm{1}}\;{\rm{and}}\;{\rm{2}}{\rm{.}} \end{array}$ (2)

Next we compute $\sum\limits_{j=0}^{r-1}{\sum\limits_{\begin{smallmatrix} i,k=0 \\ i\ne k \end{smallmatrix}}^{n-1}{\frac{{{\delta }_{{{G}'}}}\left( {{x}_{ij}} \right){{\delta }_{{{G}'}}}\left( {{x}_{kj}} \right)}{{{d}_{{{G}'}}}\left( {{x}_{ij}},{{x}_{kj}} \right)}}}.$

To do this, originally we calculate $\sum\limits_{\begin{smallmatrix} i,k=0 \\ i\ne k \end{smallmatrix}}^{n-1}{\frac{{{\delta }_{{{G}'}}}\left( {{x}_{ij}} \right){{\delta }_{{{G}'}}}\left( {{x}_{kj}} \right)}{{{d}_{{{G}'}}}\left( {{x}_{ij}},{{x}_{kj}} \right)}}.$

Let E1={uvE(G)|uv is on a triangle of G} and E2=E(G)-E1.

 $\begin{array}{l} \sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} = \\ \;\;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \notin E\left( G \right)} \end{array}}^{n - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} + \\ \;\;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_1}} \end{array}}^{n - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} + \\ \;\;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_2}} \end{array}}^{n - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} = \\ \;\;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \notin E\left( G \right)} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right)\left( {r - 1} \right) \cdot {\delta _G}\left( {{v_k}} \right)\left( {r - 1} \right)}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} + \\ \;\;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_1}} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right)\left( {r - 1} \right) \cdot {\delta _G}\left( {{v_k}} \right)\left( {r - 1} \right)}}{2}} + \\ \;\;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_2}} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right)\left( {r - 1} \right) \cdot {\delta _G}\left( {{v_k}} \right)\left( {r - 1} \right)}}{3}} , \end{array}$

by lemmas 1 and 2,

\begin{align} {\rm{the}}\;{\rm{above}}\;{\rm{formula}}\;{\rm{ = }}\;{\left( {r - 1} \right)^2}\left[ \left( \sum\limits_{\begin{smallmatrix} i,k=0 \\ \ \ i\ne k \\ {{v}_{i}}{{v}_{k}}\notin E\left( G \right) \end{smallmatrix}}^{n-1}{\frac{{{\delta }_{G}}\left( {{v}_{i}} \right){{\delta }_{G}}\left( {{v}_{k}} \right)}{{{d}_{G}}\left( {{v}_{i}},{{v}_{k}} \right)}}+ \right. \right. \\ \sum\limits_{\begin{smallmatrix} i,k=0 \\ \ \ i\ne k \\ {{v}_{i}}{{v}_{k}}\in {{E}_{1}} \end{smallmatrix}}^{n-1}{\frac{{{\delta }_{G}}\left( {{v}_{i}} \right){{\delta }_{G}}\left( {{v}_{k}} \right)}{{{d}_{G}}\left( {{v}_{i}},{{v}_{k}} \right)}}+\left. \sum\limits_{\begin{smallmatrix} i,k=0 \\ \ \ i\ne k \\ {{v}_{i}}{{v}_{k}}\in {{E}_{2}} \end{smallmatrix}}^{n-1}{\frac{{{\delta }_{G}}\left( {{v}_{i}} \right){{\delta }_{G}}\left( {{v}_{k}} \right)}{{{d}_{G}}\left( {{v}_{i}},{{v}_{k}} \right)}} \right)- \\ \sum\limits_{\begin{smallmatrix} i,k=0 \\ \ \ i\ne k \\ {{v}_{i}}{{v}_{k}}\in {{E}_{1}} \end{smallmatrix}}^{n-1}{\frac{{{\delta }_{G}}\left( {{v}_{i}} \right){{\delta }_{G}}\left( {{v}_{k}} \right)}{2}}-2\left. \sum\limits_{\begin{smallmatrix} i,k=0 \\ \ \ i\ne k \\ {{v}_{i}}{{v}_{k}}\in {{E}_{2}} \end{smallmatrix}}^{n-1}{\frac{{{\delta }_{G}}\left( {{v}_{i}} \right){{\delta }_{G}}\left( {{v}_{k}} \right)}{3}} \right], \\ \end{align}

since dG(vi, vk)=1, if vivkE1 and vivkE2,

 $\begin{array}{l} {\rm{the}}\;{\rm{above}}\;{\rm{formula}}\;{\rm{ = }}\;{\left( {r - 1} \right)^2}\left[ {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} - } \right.\\ \left( {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_1}} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)}}{2}} + \sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_2}} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)}}{2}} } \right) - \\ \left. {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_2}} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)}}{6}} } \right] = \\ {\left( {r - 1} \right)^2}\left( {2{H_M}\left( G \right) - {M_2}\left( G \right) - \sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_2}} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)}}{6}} } \right), \end{array}$ (3)

since each edge vivk of G is being counted twice in the sum, that is, vivk and vkvi.

Now summing (3) over j=0, 1, …, r-1, we have

 $\begin{array}{l} {A_2} = \sum\limits_{j = 0}^{r - 1} {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} } = \\ \;\;\;\;\;\;r{\left( {r - 1} \right)^2}\left( {2{H_M}\left( G \right) - {M_2}\left( G \right) - } \right.\\ \left. {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k}\\ {{v_i}{v_k} \in {E_2}} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)}}{6}} } \right). \end{array}$ (4)

Finally, we compute $\sum\limits_{\begin{smallmatrix} i,k=0 \\ \ \ i\ne k \end{smallmatrix}}^{n-1}{\sum\limits_{\begin{smallmatrix} j,p=0 \\ \ \ j\ne p \end{smallmatrix}}^{r-1}{\frac{{{\delta }_{{{G}'}}}\left( {{x}_{ij}} \right){{\delta }_{{{G}'}}}\left( {{x}_{kp}} \right)}{{{d}_{{{G}'}}}\left( {{x}_{ij}},{{x}_{kp}} \right)}.}}$

 $\begin{array}{l} {A_3} = \sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} } = \\ \;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _G}\left( {{v_i}} \right)\left( {r - 1} \right) \cdot {\delta _G}\left( {{v_k}} \right)\left( {r - 1} \right)}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} } = \\ \;\;\;\;\;\;\;2r{\left( {r - 1} \right)^3}{H_M}\left( G \right),\;{\rm{by}}\;{\rm{lemmas}}\;{\rm{1}}\;{\rm{and}}\;{\rm{2}}{\rm{.}} \end{array}$ (5)

Combining(2), (4) and (5) with (1), we obtain

 $\begin{array}{l} {H_M}\left( {G \times {K_r}} \right) = r{\left( {r - 1} \right)^2}\left( {r{H_M}\left( G \right) + } \right.\\ \;\;\;\;\;\;\;\frac{1}{4}\left( {r - 1} \right){M_1}\left( G \right) - \left( {\frac{{{M_2}\left( G \right)}}{2} + } \right.\\ \;\;\;\;\;\;\;\left. {\left. {\frac{1}{{12}}\sum\limits_{{v_i}{v_k} \in {E_2}} {{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)} } \right)} \right). \end{array}$

By theorem 1, we have the following corollaries.

Corollary 1 Let G be a connected graph with n≥2 vertices. If each edge of G is on a triangle, then ${H_M}\left( {G \times {K_r}} \right) = r{\left( {r-1} \right)^2}\left( {r{H_M}\left( G \right) + \frac{1}{4}\left( {r-1} \right){M_1}\left( G \right)-\frac{{{M_2}\left( G \right)}}{2}} \right)$, where r≥3.

If G is a triangle-free graph, then E2=E(G) and thus $\sum\limits_{{v_i}{v_k} \in {E_2}} {{\delta _G}\left( {{v_i}} \right)} {\delta _G}\left( {{v_k}} \right) = {M_2}\left( G \right)$.

Corollary 2 If G is a connected triangle-free graph with n≥2 vertices, then ${H_M}\left( {G \times {K_r}} \right) = r{\left( {r-1} \right)^2} \times \left( {r{H_M}\left( G \right) + \frac{1}{4}\left( {r-1} \right){M_1}\left( G \right)-\frac{{2{M_2}\left( G \right)}}{3}} \right)$, where r≥3.

Note that M1(Kn)=n(n-1)2, ${M_2}\left( {{K_n}} \right) = \frac{{n{{\left( {n-1} \right)}^3}}}{2}$; M1(Pn)=4n-6, M2(Pn)=4n-8, n≥2; M1(Cn)=M2(Cn)=4n, n≥3. In addition, we see that $H\left( {{P_n}} \right) = n\left( {\sum\limits_{i = 1}^n {\frac{1}{i}} } \right)-n$ and $H\left( {{C_n}} \right) = n\left( {\sum\limits_{i = 1}^{\frac{n}{2}} {\frac{1}{i}} } \right)-1$ for n even and $H\left( {{C_n}} \right) = n\left( {\sum\limits_{i = 1}^{\frac{{n-1}}{2}} {\frac{1}{i}} } \right)$ for n odd.

By direct calculations, we obtain expressions for the values of the multiplicatively weighted Harary index and the additively weighted Harary index of Kn, Pn and Cn: ${H_M}\left( {{K_n}} \right) = \frac{{n{{\left( {n-1} \right)}^3}}}{2}$, HA(Kn)=n(n-1)2; ${H_M}\left( {{P_n}} \right) = H\left( {{P_n}} \right) + 2\left( {\sum\limits_{i = 1}^{n-1} {\frac{1}{i}} } \right)-\frac{2}{{n-1}}$, ${H_A}\left( {{P_n}} \right) = H\left( {{P_n}} \right) + 4\left( {\sum\limits_{i = 1}^{n-1} {\frac{1}{i}} } \right)-\frac{3}{{n-1}}$ and HM(Cn)=HA(Cn)=4H(Cn).

Combining the above known results and corollaries 1 and 2, immediately, we can obtain the explicit multiplicatively weighted Harary index of the following graphs:

Example 1

 $\begin{array}{l} \left( {\rm{a}} \right)\;{\rm{For}}\;n \ge 2,r \ge 3,\;{H_M}\left( {{K_n} \times {K_r}} \right) = \frac{{n{{\left( {n - 1} \right)}^2}}}{4}\\ r\left( {\left( {n - 1} \right)\left( {2{r^3} - 5{r^2} + 4r - 1} \right) + {{\left( {r - 1} \right)}^3}} \right). \end{array}$
 $\begin{array}{l} \left( {\rm{b}} \right)\;{\rm{For}}\;n \ge 2,r \ge 3,\;{H_M}\left( {{P_n} \times {K_r}} \right) = \\ {r^2}{\left( {r - 1} \right)^2}\left( {H\left( {{P_n}} \right) + 2\left( {\sum\limits_{i = 1}^{n - 1} {\frac{1}{i}} } \right) - \frac{2}{{n - 1}}} \right) + \frac{{2n - 3}}{2}\\ r{\left( {r - 1} \right)^3} - \frac{7}{3}\left( {n - 2} \right)r{\left( {r - 1} \right)^2}. \end{array}$
 $\begin{array}{l} \left( {\rm{c}} \right)\;{\rm{For}}\;n \ge 2,\;r = 3,\;{H_M}\left( {{C_n} \times {K_r}} \right) = 3r\left( {5{r^3} - } \right.\\ \left. {13{r^2} + 11r - 3} \right) \end{array}$
 $\begin{array}{l} {\rm{For}}\;n \ge 2,\;r > 3,\;{H_M}\left( {{C_n} \times {K_r}} \right) = 4{r^2}{\left( {r - 1} \right)^2} \times \\ H\left( {{C_n}} \right) + nr{\left( {r - 1} \right)^3} - \frac{7}{3}nr{\left( {r - 1} \right)^2}. \end{array}$
3 Multiplicatively weighted Hararyindex of strong product of graphs

In this section, we obtain the multiplicatively weighted Harary index of G Kr. Let G be a connected graph with V(G)={v0, v1, …, vn-1} and V(Kr)={u1, u2, …, ur-1}. For convenience, let xij denote the vertex (vi, uj) of GKr. Firstly, we give the following lemma, which follows directly from the properties and structure of GKr, is used in the proof of our main result in this section.

Lemma 3 Let G be a connected graph and let G′=GKr. Then

(ⅰ)For any pair of vertices xij, xkpV(G′), dG(xij, xip)=1 and dG(xij, xkp)=dG(vi, vk).

(ⅱ)The degree of a vertex (vi, uj) in G′ is δG((vi, uj))=G(vi)+(r-1).

Theorem 2 Let G be a connected graph with n vertices and m edges. Then

 $\begin{array}{l} {H_M}\left( {G{K_r}} \right) = {r^4}{H_M}\left( G \right) + {r^3}\left( {r - 1} \right){H_A}\left( G \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{r^2}{\left( {r - 1} \right)^2}H\left( G \right) + \frac{{{M_1}\left( G \right){r^3}}}{2}\left( {r - 1} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2m{r^2}{\left( {r - 1} \right)^2} + \frac{{nr}}{2}{\left( {r - 1} \right)^3}. \end{array}$

Proof Let us denote G′=GKr. Obviously,

 $\begin{array}{l} {H_M}\left( {G'} \right) = \frac{1}{2}\sum\limits_{{x_{ij}},{x_{kp}} \in V\left( {G'} \right)} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} = \\ \;\;\;\;\;\;\;\;\frac{1}{2}\left( {\sum\limits_{i = 0}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{ip}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{ip}}} \right)}}} } + } \right.\\ \;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\sum\limits_{j = 0}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} } + \\ \;\;\;\;\;\;\;\;\left. {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} } } \right) = \\ \;\;\;\;\;\;\;\;\frac{1}{2}\left\{ {{A_1} + {A_2} + {A_3}} \right\}, \end{array}$ (6)

where A1, A2 and A3 are the sums of the above terms, in order.

In what follows, we calculate A1, A2 and A3 of (6), separately.

 $\begin{array}{l} {A_1} = \sum\limits_{i = 0}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{ip}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{ip}}} \right)}}} } = \\ \;\;\;\;\;\;\;\sum\limits_{i = 0}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\left( {{r^2}{\delta _G}{{\left( {{v_i}} \right)}^2} + {{\left( {r - 1} \right)}^2} + } \right.} } \\ \;\;\;\;\;\;\;\left. {2r\left( {r - 1} \right){\delta _G}\left( {{v_i}} \right)} \right) = \\ \;\;\;\;\;\;\;{r^3}\left( {r - 1} \right){M_1}\left( G \right) + nr{\left( {r - 1} \right)^3} + \\ \;\;\;\;\;\;\;4m{r^2}{\left( {r - 1} \right)^2},{\rm{by}}\;{\rm{lemma}}\;{\rm{3}}{\rm{.}} \end{array}$ (7)
 $\begin{array}{l} {A_2} = \sum\limits_{j = 0}^{r - 1} {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} } = \\ \;\;\;\;\;\;\;\sum\limits_{j = 0}^{r - 1} {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{\left( {r{\delta _G}\left( {{v_i}} \right) + r - 1} \right)\left( {r{\delta _G}\left( {{v_k}} \right) + r - 1} \right)}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} } = \\ \;\;\;\;\;\;\;{r^2}\sum\limits_{j = 0}^{r - 1} {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;r\left( {r - 1} \right)\sum\limits_{j = 0}^{r - 1} {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right) + {\delta _G}\left( {{v_k}} \right)}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;{\left( {r - 1} \right)^2}\sum\limits_{j = 0}^{r - 1} {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{1}{{{d_G}\left( {{v_i},{v_k}} \right)}}} } = \\ \;\;\;\;\;\;\;2{r^3}{H_M}\left( G \right) + 2{r^2}\left( {r - 1} \right){H_A}\left( G \right) + \\ \;\;\;\;\;\;\;2r{\left( {r - 1} \right)^2}H\left( G \right). \end{array}$ (8)
 $\begin{array}{l} {A_3} = \sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} } = \\ \;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{r - 1} {\frac{{{r^2}{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right) + r\left( {r - 1} \right)\left( {{\delta _G}\left( {{v_i}} \right)} \right.}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;\frac{{\left. {{\delta _G}\left( {{v_k}} \right)} \right) + {{\left( {r - 1} \right)}^2}}}{{{d_G}\left( {{v_i},{u_k}} \right)}}\underline{\underline {{\text{by lemma 3}}}} \\ \;\;\;\;\;\;\;{r^3}\left( {r - 1} \right)\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right){\delta _G}\left( {{v_k}} \right)}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} + \\ \;\;\;\;\;\;\;{r^2}{\left( {r - 1} \right)^2}\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{{{\delta _G}\left( {{v_i}} \right) + {\delta _G}\left( {{v_k}} \right)}}{{{d_G}\left( {{v_i},{v_k}} \right)}}} + \\ \;\;\;\;\;\;\;r{\left( {r - 1} \right)^3}\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{n - 1} {\frac{1}{{{d_G}\left( {{v_i},{v_k}} \right)}}} = \\ \;\;\;\;\;\;\;2{r^3}\left( {r - 1} \right){H_M}\left( G \right) + 2{r^2}{\left( {r - 1} \right)^2}{H_A}\left( G \right) + \\ \;\;\;\;\;\;\;2r{\left( {r - 1} \right)^3}H\left( G \right). \end{array}$ (9)

Combining (7)~(9) with (6), we get

 $\begin{array}{l} {H_M}\left( {G{K_r}} \right) = {r^4}{H_M}\left( G \right) + {r^3}\left( {r - 1} \right){H_A}\left( G \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{r^2}{\left( {r - 1} \right)^2}H\left( G \right) + \frac{{{M_1}\left( G \right){r^3}}}{2}\left( {r - 1} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2m{r^2}{\left( {r - 1} \right)^2} + \frac{{nr}}{2}{\left( {r - 1} \right)^3}. \end{array}$

As an application, we present formulae for multiplicatively weighted Harary index of open and closed fences, PnK2 and CnK2.

Example 2

 $\begin{gathered} \left( {\text{ⅰ}} \right){H_M}\left( {{P_n} \boxtimes {K_2}} \right) = 28n\left( {\sum\limits_{i = 1}^n {\frac{1}{i}} } \right) + \hfill \\ 64\left( {\sum\limits_{i = 1}^{n-1} {\frac{1}{i}} } \right) - \frac{{56}}{{n - 1}} - 3n - 32. \hfill \\ \end{gathered}$
 $\left( {{\text{ⅱ}}} \right){H_M}\left( {{C_n} \boxtimes {K_2}} \right) = \left\{ \begin{gathered} 25n\left( {1 + 4\sum\limits_{i = 1}^{\frac{n}{2}} {\frac{1}{i}} } \right) - 100,\;n\;{\text{is}}\;{\text{even,}} \hfill \\ 25n\left( {1 + 4\sum\limits_{i = 1}^{\frac{{n - 1}}{2}} {\frac{1}{i}} } \right),\;n\;{\text{is}}\;{\text{odd}}{\text{.}} \hfill \\ \end{gathered} \right.$
4 Multiplicatively weighted Hararyindex of wreath product of graphs

In this section, we give the multiplicatively weighted Harary index of G1oG2. Let G1 and G2 be two connected graphs with V(G1)={v0, v1, …, vn1-1} and V(G2)={u0, u1, …, un2-1}. For convenience, let xij denote the vertex (vi, uj) of G1oG2. The following lemma, which follows easily from the properties and structure of G1oG2, is used in the proof of our main result in this section.

Lemma 4 Let G1 and G2 be two connected graphs and let G′=G1oG2. Then the degree of a vertex (vi, uj) in G′ is δG((vi, uj))=n2δG1(vi)+δG2(uj).

Theorem 3 Let G1 and G2 be two connected graphs. The number of vertices and edges of graph Gi is denoted by ni and ei respectively for i=1, 2. Then we have

 $\begin{array}{l} {H_M}\left( {{G_1} \circ {G_2}} \right) = n_2^4{H_M}\left( {{G_1}} \right) + 2{n_2}{e_2}{H_A}\left( {{G_1}} \right) + \\ \;\;\;\;\;\;\;H\left( {{G_1}} \right)\left( {{M_1}\left( {{G_2}} \right) + 2{M_2}\left( {{G_2}} \right) + } \right.\\ \;\;\;\;\;\;\;\left. {2{{\bar M}_2}\left( {{G_2}} \right)} \right) + {n_2}{e_1}\left( {2{M_1}\left( {{G_2}} \right) + } \right.\\ \;\;\;\;\;\;\;\left. {{{\bar M}_1}\left( {{G_2}} \right)} \right) + \frac{{{n_1}}}{2}\left( {2{M_2}\left( {{G_2}} \right) + } \right.\\ \;\;\;\;\;\;\;\left. {{{\bar M}_2}\left( {{G_2}} \right)} \right) + \frac{1}{4}n_2^2{M_1}\left( {{G_1}} \right)\left( {n_2^2 - {n_2} + {e_2}} \right) + \\ \;\;\;\;\;\;\;\frac{{{n_2}}}{2}\sum\limits_{{x_{ij}},{x_{kp}} \in V\left( {{G_1} \circ {G_2}} \right)} {\frac{{{\delta _{{G_1}}}\left( {{v_i}} \right){\delta _{{G_2}}}\left( {{u_p}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} + \\ \;\;\;\;\;\;\;\frac{{{n_2}}}{2}\sum\limits_{{x_{ij}},{x_{kp}} \in V\left( {{G_1} \circ {G_2}} \right)} {\frac{{{\delta _{{G_1}}}\left( {{v_k}} \right){\delta _{{G_2}}}\left( {{u_j}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} . \end{array}$

Proof Let us denote G′=G1oG2. Obviously,

 $\begin{array}{l} {H_M}\left( {G'} \right) = \frac{1}{2}\sum\limits_{{x_{ij}},{x_{kp}} \in V\left({G'}\right)} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} = \\ \;\;\;\;\;\;\;\;\frac{1}{2}\left( {\sum\limits_{i = 0}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{ip}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{ip}}} \right)}}} } + } \right.\\ \;\;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{j = 0}^{{n_2} - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} } + \\ \;\;\;\;\;\;\;\;\left. {\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} } } \right) = \\ \;\;\;\;\;\;\;\;\frac{1}{2}\left\{ {{A_1} + {A_2} + {A_3}} \right\}, \end{array}$ (10)

where A1 to A3 are the sums of the above terms, in order.

In what follows, we compute A1, A2, A3 of (10), separately.

 $\begin{array}{l} {A_1} = \sum\limits_{i = 0}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{ip}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{ip}}} \right)}}} } = \\ \;\;\;\;\;\;\;\sum\limits_{i = 0}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{\left( {{n_2}{\delta _{{G_1}}}\left( {{v_i}} \right) + {\delta _{{G_2}}}\left( {{u_j}} \right)} \right)\left( {{n_2}{\delta _{{G_1}}}\left( {{v_i}} \right) + {\delta _{{G_2}}}\left( {{u_p}} \right)} \right)}}{{{d_{{G_2}}}\left( {{u_j},{u_p}} \right)}}} } = \\ \;\;\;\;\;\;\;\sum\limits_{i = 0}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{n_2^2{\delta _{{G_1}}}{{\left( {{v_i}} \right)}^2}}}{{{d_{{G_2}}}\left( {{u_j},{u_p}} \right)}}} } + \\ \;\;\;\;\;\;\;\sum\limits_{i = 0}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {{n_2}{\delta _{{G_1}}}\left( {{v_i}} \right) \cdot \frac{{{\delta _{{G_2}}}\left( {{u_j}} \right) + {\delta _{{G_2}}}\left( {{u_p}} \right)}}{{{d_{{G_2}}}\left( {{u_j},{u_p}} \right)}}} } + \\ \;\;\;\;\;\;\;\sum\limits_{i = 0}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{{G_2}}}\left( {{u_j}} \right){\delta _{{G_2}}}\left( {{u_p}} \right)}}{{{d_{{G_2}}}\left( {{u_j},{u_p}} \right)}}} } = \\ \;\;\;\;\;\;\;n_2^2\sum\limits_{i = 0}^{{n_1} - 1} {{\delta _{{G_1}}}{{\left( {{v_i}} \right)}^2}\left( {\sum\limits_{{u_j}{u_p} \in E\left( {{G_2}} \right)} {\frac{1}{{{d_{{G_2}}}\left( {{u_j},{u_p}} \right)}}} + } \right.} \\ \;\;\;\;\;\;\;\left. {\sum\limits_{{u_j}{u_p} \notin E\left( {{G_2}} \right)} {\frac{1}{{{d_{{G_2}}}\left( {{u_j},{u_p}} \right)}}} } \right) + \\ \;\;\;\;\;\;\;{n_2}\sum\limits_{i = 0}^{{n_1} - 1} {{\delta _{{G_1}}}\left( {{v_i}} \right)\left( {\sum\limits_{{u_j}{u_p} \in E\left( {{G_2}} \right)} {\left( {{\delta _{{G_2}}}\left( {{u_j}} \right) + {\delta _{{G_2}}}\left( {{u_p}} \right)} \right)} + } \right.} \\ \;\;\;\;\;\;\;\left. {\sum\limits_{{u_j}{u_p} \notin E\left( {{G_2}} \right)} {\frac{{{\delta _{{G_2}}}\left( {{u_j}} \right) + {\delta _{{G_2}}}\left( {{u_p}} \right)}}{2}} } \right) + \\ \;\;\;\;\;\;\;\sum\limits_{i = 0}^{{n_1} - 1} {\left( {\sum\limits_{{u_j}{u_p} \in E\left( {{G_2}} \right)} {{\delta _{{G_2}}}\left( {{u_j}} \right){\delta _{{G_2}}}\left( {{u_p}} \right)} + } \right.} \\ \;\;\;\;\;\;\;\left. {\sum\limits_{{u_j}{u_p} \notin E\left( {{G_2}} \right)} {\frac{{{\delta _{{G_2}}}\left( {{u_j}} \right){\delta _{{G_2}}}\left( {{u_p}} \right)}}{2}} } \right), \end{array}$

since each row induces a copy of G2 and

 $\begin{array}{*{20}{c}} {{d_{G'}}\left( {{x_{ij}},{x_{ip}}} \right) = 1\;{\rm{if}}\;{u_j}{u_p} \in E\left( {{G_2}} \right)\;{\rm{and}}}\\ {{d_{G'}}\left( {{x_{ij}},{x_{ip}}} \right) = 2\;{\rm{if}}\;{u_j}{u_p} \notin E\left( {{G_2}} \right).} \end{array}$
 $\begin{array}{l} {\rm{The}}\;{\rm{above}}\;{\rm{formula}}\;{\rm{ = }}\frac{1}{2}n_2^2{M_1}\left( {{G_1}} \right)\left( {n_2^2 - {n_2} + {e_2}} \right) + \\ \;\;\;\;\;\;2{n_2}{e_1}\left( {2{M_1}\left( {{G_2}} \right) + {{\bar M}_1}\left( {{G_2}} \right)} \right) + {n_1}\left( {2{M_2}\left( {{G_2}} \right) + } \right.\\ \;\;\;\;\;\;\left. {{{\bar M}_2}\left( {{G_2}} \right)} \right). \end{array}$ (11)
 $\begin{array}{l} {A_2} = \sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{j = 0}^{{n_2} - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kj}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kj}}} \right)}}} } = \\ \;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{j = 0}^{{n_2} - 1} {\frac{{\left( {{n_2}{\delta _{{G_1}}}\left( {{v_i}} \right) + {\delta _{{G_2}}}\left( {{u_j}} \right)} \right)\left( {{n_2}{\delta _{{G_1}}}\left( {{v_k}} \right)} \right.}}{{{d_{{G_1}}}\left( {{v_i}{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{j = 0}^{{n_2} - 1} {\frac{{{\delta _{{G_2}}}\left( {{u_j}} \right))}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } , \end{array}$

since the distance between a pair of vertices in a column is the same as the distance between the corresponding vertices of other column.

 $\begin{array}{l} {\rm{The}}\;{\rm{above}}\;{\rm{formula}}\;{\rm{ = }}\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{j = 0}^{{n_2} - 1} {\frac{{n_2^2{\delta _{{G_1}}}\left( {{v_i}} \right){\delta _{{G_1}}}\left( {{v_k}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{j = 0}^{{n_2} - 1} {{n_2}{\delta _{{G_2}}}\left( {{u_j}} \right)\frac{{{\delta _{{G_1}}}\left( {{v_i}} \right) + {\delta _{{G_1}}}\left( {{v_k}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{j = 0}^{{n_2} - 1} {\frac{{{\delta _{{G_2}}}{{\left( {{u_j}} \right)}^2}}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } = \\ \;\;\;\;\;\;\;2n_2^3{H_M}\left( {{G_1}} \right) + 4{n_2}{e_2}{H_A}\left( {{G_1}} \right) + 2{M_1}\left( {{G_2}} \right)H\left( {{G_1}} \right). \end{array}$ (12)
 $\begin{array}{l} {A_3} = \sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{G'}}\left( {{x_{ij}}} \right){\delta _{G'}}\left( {{x_{kp}}} \right)}}{{{d_{G'}}\left( {{x_{ij}},{x_{kp}}} \right)}}} } = \\ \;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{\left( {{n_2}{\delta _{{G_1}}}\left( {{v_i}} \right) + {\delta _{{G_2}}}\left( {{u_j}} \right)} \right)\left( {{n_2}{\delta _{{G_1}}}\left( {{v_k}} \right)} \right.}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{\left. {{\delta _{{G_2}}}\left( {{u_p}} \right)} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } , \end{array}$

since dG(xij, xkp)=dG1(vi, vk)for all i and k, and further the distance between the corresponding vertices of the layers is counted in A2,

 $\begin{array}{l} {\rm{The}}\;{\rm{above}}\;{\rm{formula}}\;{\rm{ = }}\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{n_2^2{\delta _{{G_1}}}\left( {{v_i}} \right){\delta _{{G_1}}}\left( {{v_k}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } \; + \\ \;\;\;\;\;\;\;{n_2}\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{{G_1}}}\left( {{v_i}} \right){\delta _{{G_2}}}\left( {{v_p}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;{n_2}\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{{G_1}}}\left( {{v_k}} \right){\delta _{{G_2}}}\left( {{u_j}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{{G_2}}}\left( {{u_j}} \right){\delta _{{G_2}}}\left( {{u_p}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } = \\ \;\;\;\;\;\;\;2n_2^3\left( {{n_2} - 1} \right){H_M}\left( {{G_1}} \right) + \\ \;\;\;\;\;\;\;{n_2}\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{{G_1}}}\left( {{v_i}} \right){\delta _{{G_2}}}\left( {{u_p}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;{n_2}\sum\limits_{\begin{array}{*{20}{c}} {i,k = 0}\\ {i \ne k} \end{array}}^{{n_1} - 1} {\sum\limits_{\begin{array}{*{20}{c}} {j,p = 0}\\ {j \ne p} \end{array}}^{{n_2} - 1} {\frac{{{\delta _{{G_1}}}\left( {{v_k}} \right){\delta _{{G_2}}}\left( {{u_j}} \right)}}{{{d_{{G_1}}}\left( {{v_i},{v_k}} \right)}}} } + \\ \;\;\;\;\;\;\;4H\left( {{G_1}} \right)\left( {{M_2}\left( {{G_2}} \right) + {{\bar M}_2}\left( {{G_2}} \right)} \right). \end{array}$ (13)

Combining (11)~(13) with (10), we get the desired result.

This completes the proof.

Using theorem 2, we have the following corollary.

Corollary 3 Let G1 be a connected graph and G2 be a connected k-regular graph. The number of vertices and edges of graph Gi is denoted by ni and ei respectively for i=1, 2. Then, we have

 $\begin{array}{l} {H_M}\left( {{G_1} \circ {G_2}} \right) = n_2^4{H_M}\left( {{G_1}} \right) + {n_2}\left( {kn_2^2 - k{n_2} + } \right.\\ \;\;\;\;\;\;\;\left. {2{e_2}} \right){H_A}\left( {{G_1}} \right) + H\left( {{G_1}} \right)\left( {{M_1}\left( {{G_2}} \right) + } \right.\\ \;\;\;\;\;\;\;\left. {2{M_2}\left( {{G_2}} \right) + 2{{\bar M}_2}\left( {{G_2}} \right)} \right) + \\ \;\;\;\;\;\;\;{n_1}{e_1}\left( {2{M_1}\left( {{G_2}} \right) + {{\bar M}_1}\left( {{G_2}} \right)} \right) + \\ \;\;\;\;\;\;\;\frac{{{n_1}}}{2}\left( {2{M_2}\left( {{G_2}} \right) + {{\bar M}_2}\left( {{G_2}} \right)} \right) + \\ \;\;\;\;\;\;\;\frac{1}{4}n_2^2{M_1}\left( {{G_1}} \right)\left( {n_2^2 - {n_2} + {e_2}} \right). \end{array}$
References
 [1] BONDY J A, MURTY U S R. Graph Theory with Applications, Macmillan[M]. London: Elsevier, 1976. [2] WIENER H. Structural determination of paraffin boiling point[J]. J Amer Chem Soc, 1947, 69: 17–20. DOI:10.1021/ja01193a005 [3] HOSOYA H. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons[J]. Bull Chem Soc Jpn, 1971, 44: 2332–2339. DOI:10.1246/bcsj.44.2332 [4] IVANCIUC O, BALABAN T S, BALABAN A T. Reciprocal distance matrix, related local vertex invariants and topological indices[J]. J Math Chem, 1993(12): 309–318. [5] PLAVŠIĆ D, NIKOLIĆ S, TRINAJSTIĆ N, et al. On the Harary index for the characterization of chemical graphs[J]. J Math Chem, 1993(12): 235–250. [6] DOBRYNIN A A, KOCHETOVA A A. Degree distance of a graph: A degree analogue of the Wiener index[J]. J Chem Inf Comput Sci, 1994, 34: 1082–1086. DOI:10.1021/ci00021a008 [7] GUTMAN I. Selected properties of the Schultz molecular topogical index[J]. J Chem Inf Comput Sci, 1994, 34: 1087–1089. DOI:10.1021/ci00021a009 [8] TODESCHINI R, CONSONNI V. Handbook of Molecular Descriptors[M]. Weinheim: Wiley-VCH, 2000. [9] DOBRYNIN A A, ENTRINGER R, GUTMAN I. Wiener index of trees: Theory and applications[J]. Acta Appl Math, 2001, 66: 211–249. DOI:10.1023/A:1010767517079 [10] GUTMAN I. A property of the Wiener number and its modifications[J]. Indian J Chem A, 1997, 36: 128–132. [11] GUTMAN I, RADA J, ARAUJO O. The Wiener index of starlike trees and a related partial order[J]. Match Commun Math Comput Chem, 2000, 42: 145–154. [12] ILIĆ A, STEVANOVIĆ D, FENG L, et al. Degree distance of unicyclic and bicyclic graphs[J]. Discrete Appl Math, 2011, 159: 779–788. DOI:10.1016/j.dam.2011.01.013 [13] TOMESCU I. Ordering connected graphs having small degree distances[J]. Discrete Appl Math, 2010, 158: 1714–1717. DOI:10.1016/j.dam.2010.05.023 [14] FENG L, LIU W. The maximal Gutman index of bicyclic graphs[J]. MATCH Commun Math Comput Chem, 2011, 66: 699–708. [15] MUKWEMBI S. On the upper bound of Gutman index of graphs[J]. MATCH Commun Math Comput Chem, 2012, 68: 343–348. [16] LATORA V, MARCHIORI M. Efficient behavior of small-world networks[J]. Phys Rev Lett, 2001, 87: 198701. DOI:10.1103/PhysRevLett.87.198701 [17] MARCHIORI M, LATORA V. Harmony in the small-world[J]. Physica A, 2000, 285: 539–546. DOI:10.1016/S0378-4371(00)00311-3 [18] ALIZADEH Y, IRANMANESH A, DOŠLIĆ T. Additively weighted Harary index of some composite graphs[J]. Discrete Math, 2013, 313: 26–34. DOI:10.1016/j.disc.2012.09.011 [19] PATTABIRAMAN K, VIJAYARAGAVAN M. Reciprocal degree distance of product graphs[J]. Discrete Appl Math, 2014, 179: 201–213. DOI:10.1016/j.dam.2014.07.020 [20] NIKOLIĆ S, KOVAČEVIĆ G, MILIČEVIĆ A, et al. The Zagreb indices 30 years after[J]. Croat Chem Acta, 2003, 76: 113–124. [21] ASHRAFI A R, DOŠLIĆ T, HAMZEH A. The Zagreb coindices of graph operations[J]. Discerete Appl Math, 2010, 158: 1571–1578. DOI:10.1016/j.dam.2010.05.017 [22] ALON N, LUBETZKY E. Independent set in tensor graph powers[J]. J Graph Theory, 2007, 54: 73–87. DOI:10.1002/(ISSN)1097-0118 [23] ASSAF A M. Modified group divisible designs[J]. Ars Combin, 1990, 29: 13–20. [24] BREŠAR B, IMRICH W, KLAVŽAR S, et al. Hypercubes as direct products[J]. SIAM J Discrete Math, 2005, 18: 778–786. DOI:10.1137/S0895480103438358 [25] IMRICH W, KLAVŽAR S. Product Graphs: Structure and Recognition[M]. New York, John Wiley and Sons, 2000. [26] MAMUT A, VUMAR E. Vertex vulnerability parameters of Kronecker products of complete graphs[J]. Inform Process Lett, 2008, 106: 258–262. DOI:10.1016/j.ipl.2007.12.002 [27] HOJI M, LUO Z, VUMAR E. Wiener and vertex PI indices of Kronecker products of graphs[J]. Discrete Appl Math, 2010, 158: 1848–1855. DOI:10.1016/j.dam.2010.06.009 [28] KHALIFEH M H, YOUSERI-AZARI H, ASHRAFI A R. Vertex and edge PI indices of Cartesian product of graphs[J]. Discrete Appl Math, 2008, 156: 1780–789. DOI:10.1016/j.dam.2007.08.041 [29] PATTABIRAMAN K, PAULRAJA P. On some topological indices of the tensor product of graphs[J]. Discrete Appl Math, 2012, 160: 267–279. DOI:10.1016/j.dam.2011.10.020