2 Weighted Szeged Index of G(U ) u H

www.i-csrs.org

Available free online at http://www.geman.in

Weighted Szeged Index of Generalized Hierarchical Product of Graphs

S. Nagarajan¹, K. Pattabiraman²and M. Chandrasekharan³

1Department of Mathematics, Kongu Arts and Science College Erode - 638 107, India

E-mail: [email protected]

2Department of Mathematics, Annamalai University Annamalainagar - 608 002, India

E-mail: [email protected]

3Department of Mathematics, Erode Arts and Science College Erode - 638 009, India

E-mail: [email protected] (Received: 16-4-14/Accepted: 26-5-14)

Abstract

The Szeged index of a graph G, denoted by S z(G) = P

uv=e∈E(G)

n^G_u(e)n^G_v(e). Simi- larly, the Weighted Szeged index of a graph G,denoted by S zw(G)= P

uv=e∈E(G)

dG(u)+ dG(v)

n^G_u(e)n^G_v(e),where dG(u)is the degree of the vertex u in G. In this paper, the exact formulae for the weighted Szeged indices of generalized hierarchical product and Cartesian product of two graphs are obtained.

Keywords:Generalized hierarchical product, Cartesian product, Szeged index, weighted Szeged index.

1 Introduction

All the graphs considered in this paper are connected and simple. A vertex x ∈ V(G) is said to beequidistant from the edge e = uv of G if dG(u,x) = dG(v,x), where dG(u,x) denotes the distance between u and x in G. The edges e = uv and f = xy of G are said to be equidistant edges if min{dG(u,x),dG(u,y)} =

min{dG(v,x),dG(v,y)}.The degree of the vertexuinGis denoted bydG(u).

For an edge uv = e ∈ E(G), the number of vertices of G whose distance to the vertexu is smaller than the distance to the vertex v inG is denoted by n^G_u(e);

analogously,n^G_v(e) is the number of vertices ofGwhose distance to the vertexvin Gis smaller than the distance to the vertexu; the vertices equidistant from both the ends of the edgee=uvare not counted.

Graph theory successfully provides the chemists with a variety of very useful tools, namely, different topological indices. A topological index of a graph is a parameter related to the graph; it does not depend on labeling or pictorial represen- tation of the graph. In theoretical chemistry, molecular structure descriptors (also called topological indices) are used for modeling physicochemical, pharmacologic, toxicologic, biological and other properties of chemical compounds [14]. Several types of such indices exist, especially those based on vertex and edge distances.

One of the most intensively studied topological indices is the Wiener index.

The two topological indices, namely, the Szeged index ofG,denoted byS z(G), and, weighted Szeged index ofG,denoted byS zw(G),are defined as follows:

S z(G)= P

e=uv∈E(G)

n^G_u(e)n^G_v(e), S zw(G)= P

e=uv∈E(G)

dG(u)+dG(v)

n^G_u(e)n^G_v(e).

A graphGwith a specified vertex subsetU ⊆V(G) is denoted byG(U).Barriere et al. [1, 2] defined a new product of graphs, namely, the generalized hierarchical product, as follows: Let G and H be two graphs with a nonempty vertex subset U ⊆V(G).Then thegeneralized hierarchical product,denoted byG(U)uH,is the graph with vertex setV(G)×V(H) and two vertices (g,h) and (g⁰,h⁰) are adjacent if and only ifg = g⁰ ∈ U andhh⁰ ∈ E(H) or, gg⁰ ∈ E(G) and h = h⁰ (see Fig.1).

TheCartesian product, GH, of graphsG and H has the vertex set V(GH) = V(G)×V(H) and (u,x)(v,y) is an edge ofGHifu= vandxy∈E(H) or,uv∈E(G) andx=y,see Fig.2.

Fig.1. P₅(U)uP₄,whereU ={2,3,4}

To each vertexu ∈ V(G), there is an isomorphic copy of H inGH and to each vertexv ∈V(H),there is an isomorphic copy ofGinGH.But in the generalized

hierarchical product, to each vertexu∈U,there is an isomorphic copy of Hand to each vertexv∈V(G),there is an isomorphic copy ofG.In particular, ifU = V(G), thenGH=G(U)uH.

Fig.2. P₅P₄

LetGandHbe simple connected graphs with vertex setsV(G)={u1,u2, . . . ,un}

and V(H) = {v1,v2, . . . ,vm}, respectively, and let U be a nonempty subset of G.

ThenV(G(U)uH)=V(G)×V(H); for our convenience, we writeV(G(U)uH)= Sn

i=1Xi,whereXi = {ui} ×V(H); we may also writeV(G(U)uH)= Sm

j=1Yj,where Yj = V(G)× n

vj

o. We denote the vertices of Xi by {(ui,vj) |1 ≤ j ≤ m} and the vertices ofYj by {(ui,vj)|1 ≤ i ≤ n} and we call Xi,1 ≤ i ≤ n, the i-th layer of G(U)uHandYj,1≤ j≤m,the j-thcolumnofG(U)uH.

Weighted Szeged index of graphG has been introduced by Illi´c and Milosavl- jevi´c [11]. They are given the upper and lower bounds for weighted vertex PI index of graph. Also the exact formula for weighted vertex PI index of Cartesian product of graphs is obtained in [11]. The Szeged index studied by Gutman [5], Gutman and Dobrynin [6] and Khadikar et. al. [9] is closely related to the Wiener index of a graph. Basic properties of Szeged index and its analogy to the Wiener index are discussed by Klavˇzar et. al.[8] . It is proved that for a treeT the Wiener index of T is equal to its Szeged index. Ashrafi et. al. [10] have explained the differences between Szeged and Wiener indices of graphs. The mathematical properties and chemical applications of Szeged index are well studied by Dobrynin et. al. [3], Gutman et. al. [4] and Randic et. al. [13]. Recently Pisanski and Randic [12]

studied the measuring network bipartivity using Szeged index. In this paper, the exact formulae for the weighted Szeged indices of generalized hierarchical product and Cartesian product of two graphs are obtained.

2 Weighted Szeged Index of G(U ) u H

LetG = (V,E) be a graph and U ⊆ V. In G(U), an u - v path through Uis an u- v path inG containing some vertex w ∈ U(vertex w could be the vertex u or v).

LetdG(U)(u,v) denote the length of a shortest u-vpath through U inG. Note that, if one of the vertices u and v belongs to U, then d_G(U)(u,v) = dG(u,v). A vertex x ∈ V(G(U)) is said to be equidistant from e = uv ∈ E(G(U)) throughU inG(U),

ifdG(U)(u,x) = dG(U)(v,x). For an edgeeinG(U), let NG(U)(e) denote the number of equidistant vertices ofethroughU inG(U). ThenS z(G(U)) andS zw(G(U)) are defined as follows:

S z(G(U)) = X

e=uv∈E(G)

n^G(U)_u (e)+n^G(U)_v (e)

S zw(G(U)) = X

e=uv∈E(G)

dG(U)(u)+dG(U)(v)

n^G(U)_u (e)+n^G(U)_v (e) .

For an edgee = uv∈ E(G), letTG(e,u) be the set of vertices closer touthanvand TG(e,v) be the set of vertices closer tovthanu.That is,

TG(e,u) = {x∈V(G)|dG(u,x)< dG(v,x)}

TG(e,v) = {x∈V(G)|dG(u,x)> dG(v,x)}. Similarly, for an edgee= uv∈ E(G(U)),

T_G(U)(e,u) = {x∈V(G(U))|d_G(U)(u,x)<d_G(U)(v,x)}

T_G(U)(e,v) = {x∈V(G(U))|d_G(U)(u,x)>d_G(U)(v,x)}.

The proof of the following lemma is left to the reader as it follows easily from the structure ofG(U)uH. The lemma is used in the proof of the main theorem of this section.

Lemma 2.1. Let G and H be graphs with U ⊆V(G).Then

(i)|V(G(U)uH)|= |V(G)| |V(H)|,|E(G(U)uH)|=|E(G)| |V(H)|+|E(H)| |U|. (ii)The degree of the vertex(g,h) ∈V(G(U)uH)is d_G(U)(g)+φU(g)dH(h), where φU denote the characteristic function on the set U which is 1 on U and 0 outside U.

(iii)dG(U)uH((g,h)(g⁰,h⁰))=











d_G(U)(g,g⁰)+dH(h,h⁰), i f h,h⁰,

dG(g,g⁰), i f h=h⁰.

Next we compute the weighted Szeged index of the generalized hierarchical product of two connected graphsGandH.

Theorem 2.2. Let G and H be two connected graphs with n,m vertices and p,q edges and let U be a nonempty subset of V(G).Then S zw(G(U)uH)=

2n²S z(H) P

u_r∈U

d_G(U)(ur)

+n²|U|S zw(H)+mS zw(G)+m(m−1)²S zw(G(U))+m(m−

1) P

uiuk∈E(G)

dG(U)(ui)+dG(U)(uk)

n^G_ui(e)n^G(U)_uk (e)+n^G(U)ui (e)n^G_u

k(e)

+2q P

uiuk∈E(G)

φU(ui)+ φU(uk)

n^G_u

i(e)n^G_u

k(e)+2q(m−1) P

u_iu_k∈E(G)

φU(ui)+φU(uk) n^G_u

i(e)n^G(U)u_k (e)+n^G(U)u_i (e)n^G_u

k(e)

+2q(m−1)² P

u_iu_k∈E(G)

φU(ui)+φU(uk)

n^G(U)u_i (e)n^G(U)u_k (e).

Proof. Let V(G) = {u1,u2, . . . ,un}, V(H) = {v1,v2, . . . ,vm} and let U be a nonempty subset ofV(G).For our convenience, we partition the edge set ofG(U)u Hinto two sets,E₁= {(ur,vi)(ur,vk)|ur ∈U, vivk ∈E(H)}andE₂ ={(ur,vi)(us,vi)| urus∈E(G), vi ∈V(H)},that is,E1 = ∪_ui∈UE(hXii) andE2 = ∪^m_j=1E(hYji).

Let e = vivk ∈ E(H) and let vj ∈ TH(e;vi). Then, for any ur ∈ U and e⁰ ∈ E₁ ⊂ E(G(U) u H), the distance of (ur,vi) to each vertex of Yj, is less than its distance to the vertex (ur,vk) inG(U)uH. It can be observed that if some vertex vs<TH(e,vi),then all the vertices of the columnYsare not inT_G(U)uH(e⁰; (ur,vi)) in G(U)uH. Also ifvr is equidistant toeinH,then every vertex of Yr is equidistant toe⁰.Consequently, for the edgee⁰ ∈E1( ofG(U)uH) corresponding toe( in H),

n^G(U)uH_(u

r,vi) (e⁰)=n n_v^H_i(e) (1)

and similarly,

n^G(U)uH_(u

r,vk) (e⁰)= n n^H_vk(e). (2)

Hence forE₁defined as above, X

(ur,vi)(ur,vk)=e⁰∈E₁

dG(U)uH((ur,vi))+dG(U)uH((ur,vk))

n^G(U)uH_(u

r,vi) (e⁰)n^G(U)uH_(u

r,vk) (e⁰)

= X

(ur,vi)(ur,vk)=e⁰∈E₁

d_G(U)(ur)+dH(vi)+d_G(U)(ur)+dH(vk)

n²n^H_vi(e)n_v^H

k(e)

, by (1) and (2), wheree=vivk ∈E(H),

= n² X

ur∈U

X

v_iv_k=e∈E(H)

2dG(U)(ur)

n_v^H_i(e)n^H_vk(e) +n² X

u_r∈U

X

v_iv_k=e∈E(H)

dH(vi)+dH(vk) n_v^H_i(e)n_v^H_k(e)

, since |E₁|=|U| |E(H)|,

= 2n²S z(H) X

u_r∈U

d_G(U)(ur)

+n²|U| S zw(H). (3)

Lete = uiuk ∈ E(G(U)). Then, for any v` ∈ V(H) e<sup>0</sup> = (ui,v`)(uk,v`) ∈ E<sub>2</sub> ⊂ E(G(U)uH).Ifuj ∈TG(e,ui) then (uj,v`)∈TG(U)uH(e⁰,(ui,v`)).Hence{(uj,v`)|uj ∈ TG(e,ui)} ⊆ T_G(U)uH(e⁰,(ui,vr)). If ` , s then since d<sub>G(U)uH</sub>((ui,v<sub>`</sub>),(uj,vs)) <

d_G(U)uH((uk,v`),(uj,vs)) if and only if d<sub>G(U)</sub>((ui,vj) + dH(v`,vs) < d_G(U)((uk,vj)+ dH(v_`,vs) if and only ifdG(U)((ui,vj)<dG(U)((uk,vj).

Therefore{(uj,vs)|uj ∈T_G(U)(e,ui)} ⊆T_G(U)uH(e⁰,(ui,v_`)).

Hence,

T_G(U)uH(e⁰,(ui,v_`))=

{(uj,v_`)|uj ∈TG(e,ui)}

+

{(uj,vs)|uj ∈T_G(U)(e,ui)}

.

Consequently,

n^G(U)_(u ^uH

i,v`) (e⁰)=n^G_ui(e)+(m−1)n^G(U)_ui (e) (4)

and similarly,

n^G(U)uH_(u

k,v`) (e⁰)=n^G_u

k(e)+(m−1)n^G(U)_u

k (e). (5)

Hence forE2 defined as above X

(ui,v`)(uk,v`)=e⁰∈E₂

d_G(U)uH((ui,v_{`</sub>))+d<sub>G(U)uH</sub>((uk,v<sub>`}))

n^G(U)uH_(u

i,v`) (e⁰)n^G(U)uH_(u

k,v`) (e⁰)

= X

v`∈V(H)

X

u_iu_k∈E(G)

d_G(U)(ui)+d_G(U)(uk) n^G_u

i(e)+(m−1)n^G(U)u_i (e)

n^G_uk(e)+(m−1)n^G(U)_uk (e)

!

+ X

v`∈V(H)

X

u_iu_k∈E(G)

dH(v`)

φU(ui)+φU(uk) n^G_u

i(e)+(m−1)n^G(U)u_i (e)

n^G_u

k(e)+(m−1)n^G(U)u_k (e)

! ,

by (4) and (5), wheree=uiuk ∈E(G(U))

= S₁+S₂, whereS₁andS₂are the sums of the above terms, in order. (6) We shall calculateS1andS2 of (6) separately.

S₁ = X

v`∈V(H)

X

uiuk∈E(G)

d_G(U)(ui)+d_G(U)(uk)

n^G_ui(e)n^G_uk(e)

+(m−1) X

v`∈V(H)

X

u_iu_k∈E(G)

d_G(U)(ui)+d_G(U)(uk) n^G_u

i(e)n^G(U)u_k (e)+n^G(U)_ui (e)n^G_uk(e) +(m−1)² X

v`∈V(H)

X

uiuk∈E(G)

d_G(U)(ui)+d_G(U)(uk)

n^G(U)_ui (e)n^G(U)_uk (e)

= m X

u_iu_k∈E(G)

d_G(ui)+d_G(uk) n^G_u

i(e)n^G_uk(e) +m(m−1) X

uiu_k∈E(G)

d_G(U)(ui)+d_G(U)(uk)

n^G_ui(e)n^G(U)u_k (e)+n^G(U)_ui (e)n^G_uk(e)

+m(m−1)² X

u_iu_k∈E(G)

d_G(U)(ui)+d_G(U)(uk)

n^G(U)_ui (e)n^G(U)u_k (e)

= mS zw(G)+m(m−1)²S zw(G(U)) +m(m−1) X

uiuk∈E(G)

d_G(U)(ui)+d_G(U)(uk)

n^G_ui(e)n^G(U)_uk (e)+n^G(U)_ui (e)n^G_uk(e) . (7)

S₂ = X

v_`∈V(H)

X

u_iu_k∈E(G)

d_H(v`)

φU(ui)+φU(uk) n^G_u

i(e)n^G_uk(e) + (m−1) X

v`∈V(H)

X

u_iu_k∈E(G)

dH(v`)

φU(ui)+φU(uk) n^G_u

i(e)n^G(U)u_k (e)+n^G(U)_ui (e)n^G_uk(e) + (m−1)² X

v_`∈V(H)

X

u_iu_k∈E(G)

d_H(v`)

φU(ui)+φU(uk)

n^G(U)_ui (e)n^G(U)u_k (e) (8)

Using (6) and the sumsS1andS2in (7) and (8), respectively, we have,

S z_w(G(U)uH)

=2n²S z(H) X

u_r∈U

d_G(U)(ur)

+n²|U| S z_w(H)+mS z_w(G)+m(m−1)²S z_w(G(U)) +m(m−1) X

u_iu_k∈E(G)

d_G(U)(ui)+d_G(U)(uk) n^G_u

i(e)n^G(U)u_k (e)+n^G(U)_ui (e)n^G_uk(e) +2q X

u_iu_k∈E(G)

φU(ui)+φU(uk) n^G_u

i(e)n^G_uk(e) +2q(m−1) X

u_iu_k∈E(G)

φU(ui)+φU(uk) n^G_u

i(e)n^G(U)u_k (e)+n^G(U)_ui (e)n^G_uk(e) +2q(m−1)² X

u_iu_k∈E(G)

φU(ui)+φU(uk)

n^G(U)_ui (e)n^G(U)u_k (e).

In the above theorem, if we setU =V(G),we obtain the following corollary.

Corollary 2.3. [11] Let G and H be connected graphs. Then S zw(GH) =

|V(H)|³ S zw(G)+|V(G)|³ S zw(H)+4|V(H)|²|E(H)|S z(G)+4|V(G)|²|E(G)|S z(H).

Let G₁,G₂, . . . ,Gn be graphs with vertex set V(Gi) and edge set E(Gi), 1 ≤

i ≤ n. Denote by en

i=1

Gi the Cartesian product of graphs G1,G2, . . . ,Gn. Clearly,

V(

en

i=1

Gi)

=Qⁿ

i=1|V(Gi)|.By induction onn,one can see that

E(

en

i=1

Gi)

=Qⁿ

i=1|V(Gi)|

n

P

i=1

|E(Gi)|

|V(Gi)|.In [8], S, Klavˇzar et al. have provedS z(

n

e

i=1Gi)= Pⁿ

i=1

S z(Gi)

n

Q

j=1,j,i

V(Gj)

3.

Next we compute a similar result for the weighted Szeged index.

Theorem 2.4. Let G₁,G₂, . . . ,Gnbe connected graphs. Then S zw(

n

e

i=1

Gi)=

n

P

i=1S zw(Gi)

n

Q

j=1,j,i

V(Gj)

3+4

n

P

i,j=1i,j

S z(Gi) V(Gj)

2 E(Gj)

n

Q

k=1,i,k,j

|V(Gk)|³.

Proof. The casen = 2 was proven in Theorem 2.2. We continue our argument by

mathematical induction. Suppose that the results is valid for somengraphs.

S zw n+1

m

i=1

Gi=S zw n

m

i=1

GiGn+1

= V

n

m

i=1

Gi

3

S zw(Gn+1)+|V(Gn+1)|³S zw n

m

i=1

Gi

+4 V

n

m

i=1

Gi

2 E

n

m

i=1

Gi

S z(Gn+1)+|V(Gn+1)|²|E(Gn+1)|S z

n

m

i=1

Gi

= S zw(Gn+1)

n

Y

i=1

|V(Gi)|³+|V(Gn+1)|³

n

X

i=1

S zw(Gi)

n

Y

j=1,j,i

V(Gj)

3

+4

n

X

i,j=1i,j

S z(Gi) V(Gj)

2 E(Gj)

n

Y

k=1,i,k,j

|V(Gk)|³

+4

S z(Gn+1)

n

X

i=1

|V(Gi)|²|E(Gi)|

n

Y

j=1,j,i

V(Gj)

3+

|V(Gn+1)| |E(Gn+1)|

n

X

i=1

S z(Gi)

n

Y

j=1,j,i

V(Gj)

3

=

n+1

X

i=1

S zw(Gi)

n+1

Y

j=1,j,i

V(Gj)

3+4

n

X

i,j=1,i,j

S z(Gi) V(Gj)

2 E(Gj)

n+1

Y

k=1,i,k,j

|V(Gk)|³

+ X

i≤j≤n

S z(Gi) V(Gj)

2 E(Gj)

n+1

Y

k=1,i,k,j

|V(Gk)|³

=

n

X

i=1

S zw(Gi)

n

Y

j=1,j,i

V(Gj)

3+4

n

X

i,j=1i,j

S z(Gi) V(Gj)

2 E(Gj)

n

Y

k=1,i,k,j

|V(Gk)|³.

The proof of the following corollary directly follows from Theorem 2.4.

Corollary 2.5. Let G be a connected graph. Then S zw(e

Gⁿ) = S zw(

n

e

i=1

G) = n|V(G)|³ⁿ⁻⁴|V(G)|S zw(G)+4(n−1)|E(G)|S z(G) . Example 2.6. Suppose Qndenotes the hypercube of dimension n.Then by Theo- rem 2.4, S zw(Qn)= S zw(e

K₂ⁿ)=n²2⁽³ⁿ⁻²⁾.

Let us consider the graph G whose vertices are the N−tuplesb₁b₂. . .bN with bi ∈ {0,1, . . . ,ni − 1},ni ≥ 2, and two vertices be adjacent if the corresponding tuples differ in precisely one place; such a graph is called a Hamming graph. It is well-known fact that a graphGis a Hamming graph if and only if it can be written

in the formG= e^N

i=1Kn_iand so the Hamming graph is usually denoted byHn₁n₂...nN.In the following lemma, the weighted Szeged index of a Hamming graph is computed.

It is easy to see thatS z(Kn) = ⁿ⁽ⁿ⁻¹⁾₂ andS zw(Kn) = n(n−1)².The proof of the following lemma follows from Theorem 2.4.

Lemma 2.7. Let G be a Hamming graph with above parameter. Then S zw(Hn1n2...n_N)= P^N

i=1

1− _n¹

i

2

+ P^N

i,j=1,i,j

(ni−1)(nj−1) n²

i

! _N Q

i=1

ni3.

LetCn andPndenote the cycle and path onnvertices, respectively. It is known thatS z(Cn) = ⁿ₄³ whennis even, and ⁿ⁽ⁿ⁻¹⁾₄ ² otherwise andS z(Pn) = (ⁿ₃⁺¹); see [7].

It can be easily verified thatS zw(Cn) = n³ whennis even, and n(n−1)² otherwise andS zw(Pn)= ^2(n−1)(n₃²⁺ⁿ⁻³⁾.

Using Theorems 2.2, 2.4 and S zw(Pn),S zw(Cn),S z(Pn) and S z(Cn), we obtain the exact weighted Szeged indices of the following graphs.

Example 2.8. The graphs Ln = PnK₂,R= PnCm,S =CmCnand T = PmPn

are known as ladder, C4 nanotubes, C4nanotorus and grid, respectively. The exact weigted Szeged indices of these graphs are given below.

1. S zw(Ln)= 14n³−4n²−24n+16.

2. S zw(R)=











m³

3 (10n³−3n²−10n+6) if m is even

2m³

3 (n³+n²−5n+3)+m(m−1)²n²(2n−1) if m is odd.

3. S zw(S)=























2n³m(m−1)²+2m³n(n−1)² if m is odd n is odd 2n³m(2m²−2m+1) if m is odd n is even

2m³n(2n²−2n+1) if m is even n is odd 4m³n³ if m is even n is even.

4. S zw(T)= ^2m2(n−1)₃ (2mn²+2mn−3m−n²−n)+^2n2(m−1)₃ (2nm²+2mn−3n−m²−m).

5. S zw(Cn₁Cn₂. . .Cn_k)=













 k²

k

Q

i=1

n³_i if each niis even k

k

Q

i=1

n³_i

k

P

i=1

1− _n¹

i

2

if each ni is odd.

If each ni =n,then S zw(e C^k_n)=











k²n^3k if each niis even

k²(n−1)²n^3k−2 if each ni is odd.

Example 2.9. Let G = Cn₁Cn₂. . .Cn_k and H = Cm₁Cm₂. . .Cm_r, where ni, 1≤ i≤ k are even and mj, 1≤ j≤r are odd. Using Theorem 2.2 and the above example we obtain the weighted Szeged index of the graph GH.

S zw(GH)=Q^k

i=1n³_iQ^r

j=1m³_j

k²+kr+(k+r)P

i=1r(1− ¹

m_i)² . If each ni =n≥3is even and mj =m≥3is odd, then G =e

C_n^kand H = e C_m^r and S zw(GH)=n^3km^3r

k²+kr+(k+r)r(1− _m¹)² .

Example 2.10. Using Theorem 2.4, we obtain the exact weighted Szeged index of the grid graph Pn₁Pn₂. . .Pn_k.

S zw(Pn₁Pn₂. . .Pn_k)= ²₃Q^k

i=1n³_iP^k

i=1

(ni−1)(n²_i+n_i−3)

n³_i + P^k

i,j=1,i,j

(1− ¹

n_i)(1+ _n¹_i)(1−

1 n_j)

.

If each ni = n,then S zw(e

P^k_n)= ^2k(n−1)n₃ ^3(k−1) (n²+n−3)+(k−1)(n+1).

References

[1] L. Barriere, F. Comellas, C. Dalfo and M.A. Fiol, The hierarchical product of graphs,Discrete Appl. Math., 157(2009), 36-48.

[2] L. Barriere, C. Dalfo, M.A. Fiol and M. Mitjana, The generalized hierarchical product of graphs,Discrete Math., 309(2009), 3871-3881.

[3] A.A. Dobrynin, I. Gutman and G. Domotor, A Wiener-type graph invariant for some bipartite graphs,Appl. Math. Lett., 8(1995), 57-62.

[4] I. Gutman, P.V. Khadikar, P.V. Rajput and S. Karmarkar, The Szeged index of polyacenes,J. Serb. Chem. Soc., 60(1995), 759-764.

[5] I. Gutman, A formula for the Wiener number of trees and its extension to graphs containing cycles,Graph Theory Notes, New York, 27(1994), 9-15.

[6] I. Gutman and A.A. Dobrynin, The Szeged index- A success story, Graph Theory Notes, New York, 34(1998), 37-44.

[7] M.H. Khalifeh, H.Y. Azari, A.R. Ashrafi and I. Gutman, The edge Szeged index of product graphs,Croatica Chemica Acta, 81(2008), 277-281.

[8] S. Klavˇzar, A. Rajapakse and I. Gutman, The Szeged and the Wiener index of graphs,Appl. Math. Lett., 9(1996), 45-49.

[9] P.V. Khadikar, N.V. Deshpande, P.P. Kale, A.A. Dobrynin and I. Gutman, The Szeged index and an analogy with the Wiener index, J. Chem. Inf. Comput.

Sci., 35(1995), 547-550.

[10] M.J. Nadjafi-Arani, H. Khodashenas and A.R. Ashrafi, On the differences be- tween Szeged and Wiener indices of graphs,Discrete Math., 311(2011), 2233- 2237.

[11] A. Ili´c and N. Milosavljevi´c, The Weighted vertex PI index,Math. Comput.

Model., 57(2013), 623-631.

[12] T. Pisanski and M. Randi´c, Use of Szeged index for measuring bipartivity, Discrete Appl. Math., 158(2010), 1936-1944.

[13] M. Randi´c, M. Novi´c and D. Plavsi´c, Common vertex matrix: A novel char- acterization of molecular graphs by counting, J. Comput. Chem., 34(2013), 1409-1419.

[14] I. Gutman and O.E. Polansky,Mathematical Concepts in Organic Chemistry, Springer-Verlag, Berlin, (1986).