2 Revised Szeged Index of G H

(1)

www.i-csrs.org

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

Revised Szeged Index of Product Graphs

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

1Department of Mathematics Kongu Arts and Science College

Erode - 638 107, India

E-mail: [email protected]

2Department of Mathematics Faculty of Engineering and Technology

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: 13-3-14/Accepted: 3-5-14)

Abstract

The Szeged index of a graph G is defined as S z(G)= P

uv=e∈E(G)

nu(e)nv(e),where nu(e) is number of vertices of G whose distance to the vertex u is less than the distance to the vertex v in G. Similarly, the revised Szeged index of G is defined as S z^∗(G) = P

uv=e∈E(G)

nu(e)+ ⁿ^G₂^(e) nv(e)+ ⁿ^G₂^(e)

, where nG(e) is the number of equidistant vertices of e in G. In this paper, the revised Szeged index of Cartesian product of two connected graphs is obtained. Using this formula, the revised Szeged indices of the hypercube of dimension n,Hamming graph, grid, C₄ nanotubes and nanotorus are computed.

Keywords:Cartesian product, Szeged index, revised Szeged index.

1 Introduction

All the graphs considered in this paper are connected and simple. TheCartesian product, GH,of graphsGandHhas the vertex setV(GH)= V(G)×V(H) and

(2)

(u,x)(v,y) is an edge ofGHifu=vand xy∈E(H) or,uv∈E(G) and x=y,that is, to each vertexu ∈V(G),there is an isomorphic copy ofH inGH and to each vertexv∈V(H),there is an isomorphic copy ofGinGH,see Fig.1.

LetG be a connected graph with vertex setV(G) and edge setE(G).Foru,v ∈ V(G),dG(u,v) denotes the distance betweenuandvinG.TheWiener indexofGis defined asW(G)= ¹₂ P

u,v∈V(G)dG(u,v).

This topological index has been extensively studied in the mathematical litera- ture; see [4, 5]. A vertexx∈V(G) is said to beequidistant from the edgee= uvof GifdG(u,x) = dG(v,x), wheredG(u,x) denotes the distance betweenuand xinG.

For an edgeuv= e∈ E(G),the number of vertices ofGwhose distance to the vertex uis smaller than the distance to the vertex vinGis denoted bynu(e); analogously, nv(e) is the number of vertices of Gwhose distance to the vertexvinG is smaller than the distance to the vertexu; the vertices equidistant from both the ends of the edgee = uvare not counted. Similarly, the number of equidistant vertices ofe is denoted bynG(e).

Fig.1. Cartesian Product ofC5andP4

A long time known property of the Wiener index is the formula [7, 15],W(G)= P

e=uv∈E(G)

nu(e)nv(e), which is applicable for trees. Motivated by the above formula, Gutman [6] introduced a graph invariant, named as theSzeged index, as an extension of the Wiener index and defined byS z(G)= P

e=uv∈E(G)

nu(e)nv(e).

Randi´c [14] observed that the Szeged index does not take into account the con- tributions of the vertices at equal distances from the endpoints of an edge, and so he conceived a modified version of the Szeged index which is named as the revised Szeged index. Therevised Szeged indexof a connected graph G is defined as S z^∗(G)= P

e=uv∈E(G)

nu(e)+ ⁿ^G₂^(e) nv(e)+ ⁿ^G₂^(e) .

The Szeged index studied by Gutman [?], Gutman et. al. [9] and Khadikar et.

al. [10] 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. [11] . It is proved that for a treeT the Wiener index ofT is equal to its Szeged index. The mathematical properties and chemical applications of Szeged and revised Szeged indices are well studied in [3, 8, 2, 12, 13]. In [1], Aouchiche and Hansen showed

(3)

that for a connected graphGof order nand sizem, an upper bound of the revised Szeged index ofG is ⁿ²₄^m. In [16], Xing and Zhou determined the unicyclic graphs of ordern with the smallest and the largest revised Szeged indices for n ≥ 5, and they also determined the unicyclic graphs of ordernwith the unique cycle of length r(3 ≤ r ≤ n), with the smallest and the largest revised Szeged indices. In [12], Li and Liu have identified those graphs whose revised Szeged index is maximal among bicyclic graphs. In this paper, the revised Szeged index of Cartesian product of two connected graphs is obtained. Using this formula, the revised Szeged indices of the hypercube of dimensionn, Hamming graph, grid,C₄ nanotubes and nanotorus are computed.

2 Revised Szeged Index of G H

The proof of the following lemma is left to the reader as it follows easily from the structure ofGH.The lemma is used in the proof of the main theorem of this paper.

Lemma 2.1. Let G and H be two graphs. Then

(i)|V(GH)|=|V(G)| |V(H)|,|E(GH)|= |E(G)| |V(H)|+|E(H)| |V(G)|.

(ii)dGH((g,h)(g⁰,h⁰))=dG(g,g⁰)+dH(h,h⁰).

For an edgee = uv ∈ E(G),letTG(e,u) be the set of vertices closer touthanv andTG(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)}.

Theorem 2.2. Let G and H be two connected graphs. Then S z^∗(GH)= |V(G)|³ S z^∗(H)+|V(H)|³ S z^∗(G).

Proof.LetV(G)= {u₁,u₂, . . . ,un},V(H)={v₁,v₂, . . . ,vm}.For our convenience, we partition the edge set ofGHinto two sets, E1 = {(ur,vi)(ur,vk)|ur ∈ V(G), vivk ∈ E(H)}andE2= {(ur,vi)(us,vi)|urus∈E(G), vi ∈V(H)},that is,

E₁ =∪_u_i_∈V(G)E(hXii) andE₂ =∪^m_j₌₁E(hYji).

Lete = vivk ∈ E(H) and letvj be equidistant from einH.Then, for ur ∈ V(G) ande⁰ = (ur,vi)(ur,vk) ∈ E(GH), d_GH((ur,vi),(ur,vj)) = d_GH((ur,vk),(ur,vj)).

Further, both (ur,vi) and (ur,vk) are equidistant to all the vertices ofYj; so, if (us,vj)∈Yj, then

dGH((ur,vi),(us,vj)) = dG(ur,us)+dH(vi,vj), by Lemma 2.1,

= dG(ur,us)+dH(vk,vj),

sincevjis equidistant from the edgevivk,

= d_G_H((ur,v_k),(us,v_j)), by Lemma 2.1.

(4)

Thus to each edgee=vivk ∈ E(H) and a vertexvjequidistant fromeinH,there correspond|V(G)|edgese⁰ ∈ E(Yi,Yk) ⊆ GH such that all the vertices of Yj are equidistant frome⁰.Ifvj is not equidistant frome= vivk inH, then we can observe that each of the corresponding |V(G)|, edgese⁰ ∈ E(Yi,Yk) are not equidistant to any of the vertices ofYj.Hence

nGH(e⁰)= |V(G)|nH(e). (2.1) Thus we have computed the number of equidistant vertices of the edges of E₁ ⊆ E(GH).

Lete = vivk ∈ E(H) and letvj ∈ TH(e;vi). Then, for any ur ∈ V(G) ande⁰ ∈ E₁ ⊂ E(GH),the distance of (ur,vi) to each vertex ofYj, is less than its distance to the vertex (ur,vk) inGH. It can be observed that if some vertexvs < TH(e,vi), then all the vertices of the columnYsare not inTGH(e⁰; (ur,vi)) inGH.Also ifvr

is equidistant toein H, then every vertex ofYr is equidistant toe⁰. Consequently, for the edgee⁰∈ E₁(ofGH) corresponding toe(inH),

n_(u_r,vi)(e⁰)= |V(G)|nvi(e) (2.2) and similarly,

n_(u_r,vk)(e⁰)= |V(G)| nvk(e). (2.3) Hence forE1defined as above,

P

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

n_(u_r_,v_i₎(e⁰)+ ⁿ^GH₂^(e⁰⁾ n_(u_r_,v_k₎(e⁰)+ ⁿ^GH₂^(e⁰⁾

= X

(ur,v_i)(ur,v_k)=e⁰∈E1

|V(G)|nv_i(e)+|V(G)|nH(e)

2

!

|V(G)| nv_k(e)+|V(G)|nH(e)

2

! ,

by (2.1) (2.2) and (2.3), wheree=vivk ∈E(H),

= |V(G)| X

v_iv_k=e∈E(H)

|V(G)|² n_v_i(e)+ n_H(e)

2

!

n_v_k(e)+ n_H(e) 2

! ,

since |E₁|=|V(G)| |E(H)|,

= |V(G)|³ S z^∗(H). (2.4)

Since Cartesian product is commutative, for any edgee⁰ = (ur,vi)(us,vi)∈E₂⊂ E(GH),

n_GH(e⁰) = |V(H)|nG(e).

n_(u_r,vi)(e⁰) = |V(H)| nur(e)

n_(u_s,v_i)(e⁰) = |V(H)| nu_s(e). (2.5)

(5)

Hence forE2defined as above, P

(ur,vi)(us,vi)=e⁰∈E2

n_(u_r_,v_i₎(e⁰)+ ⁿ^GH₂^(e⁰⁾ n_(u_s_,v_i₎(e⁰)+ ⁿ^GH₂^(e⁰⁾

= X

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

|V(H)| n_u_r(e)+|V(H)|nG(e)

2

!

|V(H)| n_u_s(e)+|V(H)|nG(e)

2

! ,

by (2.5), wheree=u_ru_s∈E(G),

= |V(H)| X

urus=e∈E(G)

|V(H)|² nu_r(e)+ nG(e)

2

!

nu_s(e)+ nG(e) 2

! ,

since |E₂|=|V(H)| |E(G)|,

= |V(H)|³ S z^∗(G). (2.6)

Now we shall obtain theS z^∗(GH).By the definition, S z^∗(GH) = X

(ur,vi)(us,vk)=e⁰∈E(GH)

n_(u_r_,v_i₎(e⁰)+nGH(e⁰) 2

!

n_(u_s_,v_k₎(e⁰)+nGH(e⁰) 2

!

= X

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

n_(u_r_,v_i₎(e⁰)+nGH(e⁰) 2

!

n_(u_r_,v_k₎(e⁰)+ nGH(e⁰) 2

!

+ X

(ur,v_i)(us,v_i)=e⁰∈E2

n_(u_r_,v_i₎(e⁰)+ nGH(e⁰) 2

!

n_(u_s_,v_i₎(e⁰)+ nGH(e⁰) 2

!

= |V(G)|³ S z^∗(H)+|V(H)|³ S z^∗(G), by (2.4) and (2.6).

Denote byen

i=1Gi the Cartesian product of graphsG1,G2, . . . ,Gn.In [11], Klavˇzar et al. have provedS z(en

i=1Gi)= Pⁿ

i=1

S z(Gi)

n

Q

j=1,j,i

|V(Gi)|³. Using Theorem 2.2, we have the following corollaries.

Corollary 2.3. Let G1,G2, . . . ,Gnbe connected graphs. Then S z^∗(en

i=1Gi)=

n

P

i=1

S z^∗(Gi)

n

Q

j=1,j,i

V(Gj)

3.

Corollary 2.4. Let G be a connected graph. Then S z^∗(e

Gⁿ) = S z^∗(en

i=1G) =

n|V(G)|³⁽ⁿ⁻¹⁾ S z^∗(G).

Example 2.5. Suppose Qn denotes a hypercube of dimension n.Then by Corollary 2.4, S z^∗(Qn)= S z^∗(K₂ⁿ)=n2³⁽ⁿ⁻¹⁾.

Let us consider the graph G whose vertices are the N−tuplesb1b2. . .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 aHamming graph. It is well-known fact that a graphGis a Hamming graph if and only if it can be written in the formG= eN

i=1Kn_i and so the hamming graph is usually denoted asHn₁n₂...nN. In the following lemma, the revised Szeged index of a Hamming graph is computed.

(6)

Lemma 2.6. Let G be a hamming graph with above parameter. Then S z^∗(Hn₁n₂...nN)=

N

Q

j=1

ni3 (

N

P

i=1 n_i

8)− ^N₈

! .

Proof.It is easy to see thatS z^∗(Kn)= ⁿ³⁽ⁿ⁻¹⁾₈ .Since Hamming graph is a product of complete graphs, by Corollary 2.3,

S z^∗(Hn₁n₂...nN) = S z^∗(

N

m

i=1

Kn_i)

=

N

X

i=1

S z^∗(Kn_i)

N

Y

j=1,j,i

nj3

=

N

X

i=1

ni3(ni−1) 8

N

Y

j=1,j,i

nj3

=

N

Y

j=1

ni3 N

X

i=1

(ni−1) 8

=

N

Y

j=1

ni3





(

N

X

i=1

ni

8)− N 8





.

LetCn and Pn denote the cycle and path onn vertices, respectively. It can be easily verified thatS z^∗(Cn)= ⁿ₄³ andS z^∗(Pn)= (ⁿ₃⁺¹).

Fig.2. Ladder graph of 2nvertices

Example 2.7. Using Corollary 2.3, we obtain the exact revised Szeged index of the grid graph Pn₁Pn₂. . .Pn_k.

S z^∗(Pn₁Pn₂. . .Pn_k)= ¹₆Q^k

i=1

n³_iP^k

i=1

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

i) . If each ni = n,then S z^∗(e

P^k_n)= ^kn^3k−2₆ (n+1)(n−1).

Example 2.8. Using Corollary 2.3, we obtain the exact revised Szeged index of the graph Cn₁Cn₂. . .Cn_k.

S z^∗(Cn₁Cn₂. . .Cn_k)= ^k₄Q^k

i=1

n³_i. If each ni = n,then S z^∗(e

C^k_n)= ^kn₄^3k.

(7)

Example 2.9. The graphs Ln = PnK2, R= PnCm,S = CmCnand T = PmPn

are known as ladder, C₄ nanotubes, C₄nanotorus and grid, respectively. The exact revised Szeged indices of these graphs are given below.

1. S z^∗(Ln)= ⁿ⁽⁹ⁿ₃²⁺⁴⁾. 2. S z^∗(R)= ^nm³⁽⁵ⁿ₁₂²⁻²⁾. 3. S z^∗(S)= ⁿ₈³.

4. S z^∗(T)= ¹₆(2n³m³−nm(n²−m²)).

References

[1] M. Aouchiche and P. Hansen, On a conjecture about the Szeged index, Euro- pean J. Combin., 31(2010), 1662-1666.

[2] L. Chen, X. Li and M. Liu, The (revised) Szeged index and the Wiener index of a nonbipartite graph, arXiv:1210.6460, (2012).

[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, S. Klavzar and B. Mohar (Eds), Fifty years of the Wiener index, MATCH Commun. Math. Comput. Chem., 35(1997), 1-259.

[5] I. Gutman, Y.N. Yeh, S.L. Lee and Y.L. Luo, Some recent results in the theory of the Wiener number,Indian J. Chem., 32A(1993), 651-661.

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

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

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

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

[10] 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.

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

(8)

[12] X. Li and M. Liu, Bicyclic graphs with maximal revised Szeged index,Dis- crete Appl. Math., 161(2013), 2527-2531.

[13] T. Pisanski and M. Randic, Use of the Szeged index and the revised Szeged index for measuring network bipartivity,Discrete Appl. Math., 158(2010), 1936- 1944.

[14] M. Randi´c, On generalization of Wiener index for cyclic structures, Acta Chim. Slov., 49(2002), 483-496.

[15] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem.

Soc., 69(1947), 17-20.

[16] R. Xing and B. Zhou, On the revised Szeged index, Discrete Appl. Math., 159(2011), 69-78.