ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 153-160
Revised and edge revised Szeged indices of
graphs
Morteza Faghani, Ali Reza Ashrafi *
Department of Mathematics, Faculty of Mathematical Science, University ofKashan, Kashan 87317-51167, I. R. Iran
4=
Received 31 October 2011, accepted 19 August 2012, published online 8 April 2013
Abstract
The revised Szeged index is a molecular structure descriptor equal to the sum of products [nu(e) + n0(e)/2] x [nv(e) + n0(e)/2] over all edges e = uv of the molecular graph G, where n0(e) is the number of vertices equidistant from u and v, nu(e) is the number of vertices whose distance to vertex u is smaller than the distance to vertex v and nv (e) is defined analogously. In this paper, new formula for computing this molecular descriptor is presented by which it is possible to reprove most of results given in [M. Aouchiche and P. Hansen, On a conjecture about the Szeged index, European J. Combin. 31 (2010), 16621666]. We also present an edge version of this graph invariant. At the end of the paper an open question is presented.
Keywords: Szeged index, edge Szeged index, revised Szeged index, edge revised Szeged index. Math. Subj. Class.: 05C12
1 Introduction
We first describe some notations which will be kept throughout. Let G be a simple graph with vertex set V(G) and edge set E(G). If e = uv G E(G) then d(u, v) stands for the distance between u and v in G. A topological index is a graph invariant applicable in chemistry. A topological index x is called distanced-based, if x is related to the distance function d(-, -). The first use of a distance-based topological index occurred in the year 1947 in a seminal paper by an American chemist Harold Wiener [14].
Suppose G is a connected graph and e = uv G E(G). The quantities n0(e), nu(e) and nv (e) are defined to be the number of vertices equidistant from u and v, the number of vertices whose distance to vertex u is smaller than the distance to vertex v and the number
* Corresponding author.
E-mail addresses: m faghani@pnu.ac.ir (Morteza Faghani), ashrafi@kashanu.ac.ir (Ali Reza Ashrafi)
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
153
ArsMath. Contemp. 7 (2014) 123-140
of vertices closer to v than u, respectively. Similarly, the quantities m0(e), mu(e) and m, (e) are defined to be the number of edges equidistant from u and v, the number of edges whose distance to vertex u is smaller than the distance to vertex v and the number of edges closer to v than u, respectively. Here, for an edge e = xy and vertex u, the distance between e and u is defined as dG(e, u) = Min{dG(x, u), dG(y, u)}.
The Szeged, edge Szeged, edge-vertex Szeged, vertex-edge Szeged, revised Szeged and edge revised Szeged indices of G are defined as follows:
Sz(G)	= X^[n«(e) x n„(e)],
Sze(G)	= E[m«(e) x m,(e)], e=uv
Szev (G)	= 1/2^[m„(e) x n,(e) + m,(e) x n„(e)],
Sz,e(G)	= 1/2 ^ [m„(e) x n„(e) + m,(e) x n,(e)],
Sz*(G)	= ^ [(n„(e) + no(e)/2) x (n,(e) + no(e)/2)],
sz:(G)	= E I(m«(e) + mo(e)/2) x (m,(e) + mo(e)/2)] e=u,
It is worth mentioning here that the Szeged index was introduced by Ivan Gutman [4] and the name Szeged index was given in [5]. For the mathematical properties of this topological index we refer to [3, 9, 10]. The concept of edge Szeged index was introduced in [6] and mathematical properties of this graph invariant are studied in [2, 7, 8]. The revised Szeged index was introduced by Milan Randic [13] as a modification of the classical Wiener index. Nowadays the scientists prefer the name revised Szeged index for this distance-based topological index. The interested readers can consult [1, 11, 12, 15] for mathematical properties of this new topological index.
Throughout this section graph means finite simple connected graph. The notation is standard and can be taken from the standard books on graph theory.
2 Main results
In this section, we first present a new formula for computing revised Szeged index of graphs. Then apply this new formula to reprove all results given by Aouchiche and Hansen [1]. We also present an edge version of the revised Szeged index and extend the results given in the mentioned article to this new graph invariant. We begin by an example.
Example 2.1. Suppose Gi = Kn, G2 = Cn and G3 = Wn denote the complete, cycle and wheel graphs of order n, and G4 = Km,n is the complete bipartite graph with partitions of size m and n, respectively. Then,
•	If e = uv € E(G1) then mu = m, = n — 2 and m0 = "2-5"+8. Therefore, Sze(Gi) = "("-1)2("-2)2 andSz*(Gi) = "3("-1)3.
•	Suppose e = uv is an arbitrary edge of G2. If n = 2k +1, then mu = m, = k and so mo = 1. Therefore, Sze(G)) = (2k + 1)k2 = "("-1)2 and Sz*(G)) = "3.
M. Faghani and A. R. Ashrafi: Revised and edge revised Szeged indices of graphs	155
If n = 2k then mu = mv = k — 1 and so m0 = 2. This implies that Sze(G2) = n(k — 1)2 = ff-2- and Sz*(G2) = f3.
•	Consider the n—vertex wheel graph G3, n > 5. If e = uv is an edge of G3 such that the vertex v is the center of G3, then mu = 3, mv = 2n — 7 and m0 = 3. If both of u and v are not the center of G3, then mu = 3 , mv = 3 and m0 = 2n — 8. Therefore Sze(G3) = (n — 1)(4n — 5) and Sz*(G3) = (n — 1)(n2 + 5n — 73/4).
•	Suppose G4 = , x + y = n, is the complete bipartite graph containing an arbitrary edge e = uv, where deg(u) = x and deg(v) = y. Then we have mu =
x—1, mv = y—1, m0 = xy— x—y+2. This implies that Sze(G4) = xy(x—1)(y—1) and Sz*(Gi) = f (x2y2 — x2 — y2 + 2xy).
Theorem 2.2. Let G be an n-vertex and m-edge graph. Then
Sz*(G) = — 1 £ (nU + nV) + 1 Sz(G)
e=uv
Proof. Since nu(e) + n (e) = n — n0(e) we have:
02 n«n„ + y(n„ + n„) + 4 n0
Sz*(G) =	+ n0)(nv + ^f0)
e=uv
= Er
e=uv = £
n«n„ + -((n — (n„ + n„ )))(n„ + n„) + -(n — (n„ + n„ ))2
£
n, \ 1 / ^
n«n„ + -(n„ + n„) — (n„ + n„)
2
2
n2 1	1	2
+ -4 — 2 n(n„ + n„) + 4 (n„ + n„)
£
n2 1 2 2 n«n„ + 4 — 4(n„ + n„ + 2(n„)(nv))
1	mn2 1	2 2
_Sz(G) + — — 4 £>U + nV].
proving the result.
The next Corollary is already known result that stated and proven in [1].
□
Corollary 2.3. Sz(G) < Sz*(G) < ^f-.
mn 4
/ „2
Proof. Since nu + nv < n, (nu + nv)2 < n2. So, J2e=uv [nu + nv]2 < mn2 and therefore
'JU I ' ''v
mf- — |Ee=uv n+nv]2 = mf- — iEe=uv[nU +n2] — 1 Sz(G) > 0. Now, Theorem 2.2 implies that Sz(G) < Sz* (G), the left hand side of inequality. The right hand side is a direct consequence of Theorem 2.2 and the following inequality:
^Sz(G) — 4 £ [nU + nV] = — ^ ^ — nv]2 < 0.
□
151
ArsMath. Contemp. 7 (2014) 123-140
By a similar argument as Theorem 2.2, one can prove:
Theorem 2.4. Let G be an n-vertex and m-edge graph. Then
S*:(G) = m3 - 4 E [mU + mV] + 2Sze(G).
e=uv
Corollary 2.5. Sze(G) < Sz*(G) < mr
Proof. The proof is similar to the proof of Corollary 2.3 and so omitted.	□
Suppose G is a connected graph and u is a vertex of G. Define
D(u, G) =	[dc(u,x)].
x£V(G)
The graph G is called distance-balanced (or transmission-regular according to [1]) if for every u, v e V(G), D(u, G) = D(v, G). Similarly for a vertex u and an edge e = xy define De(u, G) = e£E(G) [dG(e, u). A graph G is called edge-distance-balanced if for every vertices u, v e V(G), De(u, G) = de(v, G).
Theorem 2.6. Suppose u and v are vertices of a connected graph G. Then mu = mv if and only if De(u, G) = de(v, G).
Proof. Let e = uv be an arbitrary edge of G. We partition the edge set of G into three parts as follows:
•	M (u) is the set of all edges that are closer to u than v.
•	M(v) is the set of all edges that are closer to v than u.
•	M(o) is the set of all edges that are equidistant from u and v.
Suppose mu(e) = |M(u)|, mv (e) = |M(v)| and m0(e) = |M(o)|. Then we have :
De(u, G) = ^ dG(e,u)
e£E(G)
= E dG(e, u) + ^ dG(e,u)+ ^ dG(e,u)
e£M (u)	e£M(v)	e£M (0)
= E dG(e, u) + ^ (1 + dG(e,v))+ ^ dG(e,u)
e£M (u)	e£M (v)	e£M (0)
= X/ dG(e, u) + mv(e) + ^ dG(e, v) + ^ dG(e,u).
e£M (u)	e£M (v)	e£M (0)
A similar argument shows that
De(v, G) = ^ dG(e, u) + m,(e)^ dG(e, v) + ^ dG(e,v).
e£M(u)	e£M(v)	e£M(0)
But De(u, G) - De(v, G) = mv(e) - mu(e) and so mu(e) = mv(e) if and only if De(u, G) = De(v, G). This complete our argument.	□
M. Faghani and A. R. Ashrafi: Revised and edge revised Szeged indices of graphs	157
Corollary 2.7. If Sze(G) = mr then G is an edge-distance-balanced graph. Proof. If Sze(G) = then by Corollary 2.5, Sz*(G) = m-. Thus
^Sze(G) - ^ E tm« + m2] = - ^ E [m« - mv]2 =°.
uveE(G)	uveE(G)
Therefore mu = mv. Now Theorem 2.6 implies that G is an edge-distanced-balanced graph.	□
In the end of this paper, we compute an exact formula for the edge revised Szeged index of Cartesian product of graphs. To do this, we assume that G and H are connected graphs with vertex sets V(G) = {u^ u2,..., ur} and V(H) = {v^ v2,..., vs}. We also assume that |E(G)| = ei and |E(H)| = e2. Then by definition V(G x H) = V(G) x V(H) and we have:
E(G x H) = {(u, v)(a, b) | [u = a, vb G E(H)] or [ua G E(G), v = b]}.
Clearly, |E(G x H)| = |V(G)||E(H)| + |V(H)||E(G)|. To compute the edge revised Szeged index of G x H we partition the edge set of this graph into the following parts:
Am = {(um,x)(um,y) | xy G E(H)} ;1 < m < r, Bt = {(a, vt)(b, vt) | ab G E(G)} ; 1 < t < s.
Theorem 2.8. (See [15, Lemmas 2 and 3]). With above notations we have:
(a)	If e = (um, vj)(um,v9) G Am) then
m(um,v,-)(e) = |V(G)|mvj (vjvq) + |E(G)|nv3- (vjvq) = rmv; (H) + e^ (H),
m(Um,Vq ) (e) = |V (G)|mvq (vj vq )+ |E(G)|nvj (vj vq ) = rmvq (H) + e1«v, (H).
(b)If	e = (ui,vt)(up,vt) G Bt then
m(u,,vt)(e) = |V (H )|mui (ujup) + |E(H )|n^ (ujup) = smu, (G) + e2nu, (G), m(up,vt)(e) = |V (H )|mup (u^) + |E(H )|nup (u^) = smup (G) + e2«-up (G).
Theorem 2.9. With notation of Theorem 2.8, the edge revised Szeged index of Cartesian product of G and H can be computed as follows:
Sz:(G x H) = 2r3Sze(H)+ r2eiSzev(H) + 2re2Sz(H) + 1 re2(re2 + sei)2
r2eiSzve(H) - 1 r3 E [mX(H) + m2(H)]
xyeE(H)
1 re2 E [nX (H)+ ™y (H)] + 1 s3 Sze (G) + s2e2^zev (G)
xyeE(H)
+ 1 se2Sz(G) + isei(sei + re2)2 - s2e2^Zve(G)
4s3 E [m^(G) + m2(G)] - 4se2 E [^(G) + n2(G)].
abeE(G)	abeE(G)



153
ArsMath. Contemp. 7 (2014) 123-140
Proof. Let e = (um,x)(um, y) e Am. Then mo(e) = re2 + sei - r(mx(H) + my(H)) - ei(nx(H) + ny(H)). Set,
A= B =
m(um,x)(e) + m(a,vt)(e) +
mo(e) 2
mo(e) 2
e) +
m(um,y m(b,vt) (e) +
mo(e) 2
mo (e)
2
Then we have:
A = 2 r2mx(H )my (H) + 1 eir(nx(H )my (H) + ny (H)ma(H))
+ 1 e2nx(H)ny(H) + 4(re2 + sei)2 - 2eir(nx(H)mx(H) + ny(H)my(H))
1
1
- -r2(mX(H) + m2y(H)) - -e2(nX(H) + n2(H)).
Thus,
E
(um,x)(um,y)eA„
m(u
(e) +
(e)
/ \ , mo(e) m(um,y)(e) + —2""
1
1
1/2r2Sze(H) + eirSzev(H) + -e2Sz(H) + -e2(re2 + sei)
2
4
-	eirSzve(H) - 4r2 ]T [mX(H)+ m^(H)]
xyeE(H)
-	1 e2 E [nX(H) + ny (H)].
xyeE(H)
Using a similar argument for the edge e = (a, vt)(b, vt) e Bt, we have:
(2.1)
B
m(a
e) +
mo (e)
m(b,vt)(e) +
mo (e)
1
= os mui(G)mup(G) + -e2s [na(G)mb(G) + nb(G)ma(G)]
2
2
+ 1 e2na(G)nb(G) + 4(sei + re2)2 - 2e2s [na(G)ma(G) + nb(G)mb(G)] - 1 s2 [m;l(G) + m2(G)] - 1 e2 [^(G) + n2(G)] .
So,
E
(a,vt)(b,vt)EBt
m(a,vt)(e) +
mo(e) 2
m(b,vt)(e) +
mo(e)
2
2 s2 Sze (G) + e2 sSzev (G) + 2 e2 Sz(G) + 1 ei(sei + re2)2
- e2sSzve(G) - 1 s2 £ [mii(G)+ m2(G)]
(2.2)
abeE(G)
- 1 e2 E [na(G) + n2(G)] .
abeE(G)
X
m
2

2
2
2
M. Faghani and A. R. Ashrafi: Revised and edge revised Szeged indices of graphs	157
Now multiplying Eq. (2.1) by r and Eq. (2.2) by s and summation of these values, the formula given in the theorem will be obtained.	□
3 Conclusions
Some of mathematicians recently focus on the revised Szeged index of graphs. In this paper a new formula for computing this topological index is presented by which it is possible to reprove some earlier results. We also investigate an edge version of this interesting topological index. We proved that the edge version of this graph invariant is more complicated than its vertex version. In the case of vertex version, it is easy to find an exact formula for the Cartesian product of graphs but in the edge version it is too difficult.
In Theorem 2.6 and Corollary 2.7, it is proved that Sze(G) = m implies that G is an edge-balanced-distance graph. We end the paper with the following open question:
Question: Characterize graphs G such that Sze(G) = m3/4. Acknowledgements
The authors are indebted to the referees for their suggestions and helpful remarks. This research has been supported by the research affair of the University of Kashan, I. R. Iran under grant number 159020/4.
References
[1]	M. Aouchiche and P. Hansen, On a conjecture about the Szeged index, European J. Combin. 31 (2010), 1662-1666.
[2]	E. Chiniforooshan and B. Wu, Maximum values of Szeged index and edge- Szeged index of graphs, Electronic Notes Discrete Math. 34 (2009), 405-409.
[3]	K. Ch. Das and I. Gutman, Estimating the Szeged index, Appl. Math. Lett. 22 (2009), 16801684.
[4]	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.
[5]	I. Gutman, P. V. Khadikar, P. V. Rajput and S. Karmarkar, The Szeged index of polyacenes, J. Serb. Chem. Soc. 60 (1995), 759-764.
[6]	I. Gutman and A. R. Ashrafi, The edge version of the Szeged index, Croat. Chem. Acta 81 (2008), 277-281.
[7]	M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi and I. Gutman, The edge Szeged index of product graphs, Croat. Chem. Acta 81 (2008), 277-281.
[8]	M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi and S. G. Wagner, Some new results on distance-based graph invariants, European J. Combin. 30 (2009), 1149-1163.
[9]	S. Klavzar and I. Gutman, A theorem on Wiener-type invariants for isometric subgraphs of hypercubes, Appl. Math. Lett. 19 (2006), 1129-1133.
[10]	T. Mansour and M. Schork, The vertex PI index and Szeged index of bridge graphs, Discrete Appl. Math. 157 (2009), 1600-1606.
[11]	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.
155
ArsMath. Contemp. 7 (2014) 123-140
[12]	T. Pisanski and J. Zerovnik, Edge-contributions of some topological indices and arboreality of molecular graphs, Ars Mathematica Contemporánea 2 (2009), 49-58.
[13]	M. Randic, On generalization of Wiener index for cyclic structures, Acta Chim. Slovenica 49 (2002), 483-496.
[14]	H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947), 17-20.
[15]	R. Xing and B.Zhou, On the revised Szeged index, Discrete Appl. Math. 159 (2011), 69-78.