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 d_G(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×K_{m0, m1, …, mr-1} and the strong product GK_{m0, m1, …, mr-1}, where K_{m0, m1, …, mr-1} is the complete multipartite graph with partite sets of sizes m₀, m₁, …, m_r-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×K_r, the strong product GK_r and the wreath product G₁oG₂ 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 K_r 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 K_n, C_n and P_n denote the n-vertex complete graph, cycle and path, respectively. We call C₃ 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(G)×V(H) in which (g₁, h₁) and (g₂, h₂) are adjacent whenever g₁g₂ is an edge in G and h₁h₂ 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 (ⅰ)u=v and xy∈E(H), or (ⅱ) uv∈E(G) and x=y, or (ⅲ) uv∈E(G) and xy∈E(H). Similarly, the wreath product (also known as the composition) of the graphs G and H, denoted by GoH, has vertex set V(G)×V(H) in which (g₁, h₁)(g₂, h₂) is an edge whenever g₁g₂∈E(G), or g₁=g₂ and h₁h₂∈E(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)={v₀, v₁, …, v_n-1} and V(K_r)={u₁, u₂, …, u_r-1}. For convenience, let x_ij denote the vertex (v_i, u_j) of G×K_r. The following lemma, which follows easily from the properties and structure of G×K_r, 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 x_ij, x_kp be any pair vertices of the graph G′=G×K_r, where r≥3.

(ⅰ)If v_iv_k∈E(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 v_iv_k$\notin $E(G), then d_G′(x_ij, x_kp)=d_G(v_i, v_k).

(ⅲ)d_G′(x_ij, x_ip)=2.

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

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

Theorem 1 Let G be a connected graph with n≥2 vertices and E₂ 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×K_r. 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 A₁ to A₃ are the sums of the above terms, in order. In what follows, we compute A₁ to A₃ 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 E₁={uv∈E(G)|uv is on a triangle of G} and E₂=E(G)-E₁.

$ \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 d_G(v_i, v_k)=1, if v_iv_k∈E₁ and v_iv_k∈E₂,

$ \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 v_iv_k of G is being counted twice in the sum, that is, v_iv_k and v_kv_i.

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 E₂=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 M₁(K_n)=n(n-1)², ${M_2}\left( {{K_n}} \right) = \frac{{n{{\left( {n-1} \right)}^3}}}{2} $; M₁(P_n)=4n-6, M₂(P_n)=4n-8, n≥2; M₁(C_n)=M₂(C_n)=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 K_n, P_n and C_n: $ {H_M}\left( {{K_n}} \right) = \frac{{n{{\left( {n-1} \right)}^3}}}{2}$, H_A(K_n)=n(n-1)²; ${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 H_M(C_n)=H_A(C_n)=4H(C_n).

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 K_r. Let G be a connected graph with V(G)={v₀, v₁, …, v_n-1} and V(K_r)={u₁, u₂, …, u_r-1}. For convenience, let x_ij denote the vertex (v_i, u_j) of GK_r. Firstly, we give the following lemma, which follows directly from the properties and structure of GK_r, is used in the proof of our main result in this section.

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

(ⅰ)For any pair of vertices x_ij, x_kp∈V(G′), d_G′(x_ij, x_ip)=1 and d_G′(x_ij, x_kp)=d_G(v_i, v_k).

(ⅱ)The degree of a vertex (v_i, u_j) in G′ is δ_G′((v_i, u_j))=rδ_G(v_i)+(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′=GK_r. 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 A₁, A₂ and A₃ are the sums of the above terms, in order.

In what follows, we calculate A₁, A₂ and A₃ 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, P_nK₂ and C_nK₂.

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 G₁oG₂. Let G₁ and G₂ be two connected graphs with V(G₁)={v₀, v₁, …, v_n1-1} and V(G₂)={u₀, u₁, …, u_n2-1}. For convenience, let x_ij denote the vertex (v_i, u_j) of G₁oG₂. The following lemma, which follows easily from the properties and structure of G₁oG₂, is used in the proof of our main result in this section.

Lemma 4 Let G₁ and G₂ be two connected graphs and let G′=G₁oG₂. Then the degree of a vertex (v_i, u_j) in G′ is δ_G′((v_i, u_j))=n₂δ_G1(v_i)+δ_G2(u_j).

Theorem 3 Let G₁ and G₂ be two connected graphs. The number of vertices and edges of graph G_i is denoted by n_i and e_i 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′=G₁oG₂. 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 A₁ to A₃ are the sums of the above terms, in order.

In what follows, we compute A₁, A₂, A₃ 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 G₂ 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 d_G′(x_ij, x_kp)=d_G1(v_i, v_k)for all i and k, and further the distance between the corresponding vertices of the layers is counted in A₂,

$ \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 G₁ be a connected graph and G₂ be a connected k-regular graph. The number of vertices and edges of graph G_i is denoted by n_i and e_i 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} $