IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 50 (2012), 1175
ISSN 2232-2094
WIENER INDEX VERSUS SZEGED INDEX IN NETWORKS
Sandi Klavžar M. J. Nadjafi-Arani
Ljubljana, April 12, 2012
1—1
Wiener index versus Szeged index in networks
"in
a	Sandi Klavzar
Faculty of Mathematics and Physics University of Ljubljana, SI-1000 Ljubljana, Slovenia
and
Faculty of Natural Sciences and Mathematics University of Maribor, SI-2000 Maribor, Slovenia
M. J. Nadjafi-Arani Faculty of Mathematics, Statistics and Computer Science University of Kashan, Kashan 87317-51167, I. R. Iran
Abstract
Let (G,w) be a network, that is, a graph G = (V(G), E(G)) together with the weight function w : E(G) ^ R+. The Szeged index Sz(G,w) of the network (G,w) is introduced and proved that Sz(G,w) > W(G, w) holds for any connected network where W(G, w) is the Wiener index of (G, w). Moreover, equality holds if and only if (G, w) is a block network in which w is constant on each of its blocks. Analogous result holds for vertex-weighted graphs as well.
lO IN
o Ö
cm
i
cm 00 cm cm
¡5 CO CO
co CD
Key words: Wiener index, Szeged index, network, block network AMS subject classification (2000): 05C12, 92E10
1 Introduction
The Wiener index of a graph is the most famous and one of the most studied topological indices in mathematical chemistry. It was introduced back in 1947 but is nevertheless still a very active research topic, cf. [14, 15, 17, 18, 19].
The Szeged index of a graph was introduced in [8] and has received a lot of attention immediately after its introduction, cf. [4]. After that, a period of not so intensive research followed, but in the last years we are faced with a big revival of the interest for this index. Let us mention only a couple of recent developments. A conjecture from [10] led to a proof that the graphs G for which the Szeged index equals	tG)l axe precisely connected, bipartite, distance-balanced graphs. (See [7] for distance-balanced graphs.) This result was independently obtained in [1] a and in [6]. Pisanski and Randic [16] proposed to use the Szeged index (combined with the revised Szeged index) as a measure of bipartivity of a graph, see also [20]. For more recent results on the Szeged index we refer to [2, 5, 9, 14].
o
cm
cm
u
A network (G, w) is a graph G = (V(G), E(G)) together with the weight function w : E(G) — R+. In this paper we consider the Wiener index and the Szeged index on networks (alias edge-weighted graphs). This seems to be a very natural framework, the weight of an edge could, for instance, measure the Euclidean distance between atoms in a molecular graph. However, this line of research seems not to be (widely) studied earlier, in particular, as far as we know, the Szeged index of a network (G, w), that we define as
Sz(G, w) = ^ w(e)nu(e)nv(e),
e=uv
IN	has not yet been defined on networks. (See below for the definition of nu(e).) In
this paper we compare the Szeged index of a network (G, w) with its Wiener index W(G, w) and prove the following:
o
£ CO CO
Theorem 1 Let (G, w) be a connected network. Then
Sz(G,w) > W(G, w).
Moreover, equality holds if and only if (G, w) is a block network in which w is constant on each of its blocks.
i
In the special case of graphs (that is, for networks in which w = 1), the inequality part of Theorem 1 was proved in [13], see also [11], while the equality part was established in [3].
cm	In the rest of the section we give definitions and concepts needed here. Then,
is Section 2, a proof of Theorem 1 is given. In the concluding section we give some remarks on the theorem and observe that an analogous result holds for vertex-weighted graphs.
Let (G,w) be a connected network. The distance between vertices u and v of (G,w) is denoted by d(u, v) and it is defined as the minimum sum of the weights of edges over all u, v-paths. The Wiener index W(G, w) is the sum of the distances between all unordered pairs of vertices of (G, w). Every edge e = uv € E(G) induces the partition of the vertex set V(G) of (G,w) into V(G) = Nu(e) U Nv (e) U N0(e) that
Nu(e) = {x € V(G) | d(x,u) < d(x,v)}, Nv(e) = {x € V(G) | d(x, u) > d(x,v)}, N0(e) = {x € V(G) | d(x,u) = d(x,v)}.
&
Set nu(e) = |Nu(e)| and nv(e) = |N(e)|.
Finally, a block of a network is its maximal (with respect to inclusion) biconnected subnetwork. A network is called a block network if all of its blocks are complete.
CM 1—1
o
2 Proof of Theorem 1
CM
CO CD
U
a
CD
Let |V(G)| = n and |E(G)| = m. Select shortest paths PbP2, ...,P(n) in (G,w) such that for every pair of vertices a, b € V(G), a = b, there exists a unique shortest a, b-path in the list. Let e1,..., em be an ordered list of edges of (G, w). Then define
/n\
the path-edge matrix D = [dj] of dimension (2) x m as follows
d i w(ej); ej € E(Pt), dij = \ 0; ej € E(Pi).
IN	th
It is clear that the summation of the entries of the i row of D is the length of the path Pi. Thus, the summation of all the entries of D is W(G, w).
Suppose that P is a shortest a, b-path containing the edge ej = uv. Traverse the path P from the source vertex a to the destination vertex b. If we traverse the vertex u before v, then d(a, v) = d(a, u) + d(u, v). This implies that a € Nu(ej) and b € Nv (ej). It means that the number of non-zero entries in the jth column of D is at most nu(ej)nv (ej) and consequently, the summation of the entries of the jth column of D is at most w(ej)nu(ej)nv(ej). It follows that Sz(G,w) > W(G, w).
It also follows from the above double counting that Sz(G, w) = W(G, w) if and only if for every 1 < j < m, the summation of the jth column is w(ej)nu(ej)nv(ej). This is in turn true if and only if the following conditions are fulfilled:
CO
(1)	Any two vertices of (G, w) are connected by a unique shortest path.
(2)	For every edge e = uv of (G,w) and every vertices a € Nu(e) and b € Nv (e), the shortest a, b-path contains e.
CO
To complete the proof we will show that (G,w) is a block network and w is constant on each of its blocks if and only if conditions (1) and (2) hold. If (G, w) is a block network with w constant on blocks, (1) and (2) clearly holds. To prove the converse assume in the rest that (G, w) is an arbitrary network for which (1) and (2) hold.
Note first that the conditions imply that if uv is an edge, then the unique shortest u, v-path is the edge uv itself. It follows that if e = uv and f = ab are two edges of G such that a € Nu(e), then b / Nv (e).
Let e = uv and let P1 : u, t1, t2,..., tk, z be the shortest u, z-path, such that ti € Nu(e), 1 < i < k, and z € N0(e). Let P2 : v, w1, w2,..., wr, yr+1,..., = z be the shortest v,z-path, where wi € Nv(e), 1 < i < r, and yi € N0(e),r + 1 < i < s. Set also f = tkz and g = wryr+1. The situation is shown in Fig. 1.
Claim 1: The edges e, f and g form a triangle and w(e) = w(f) = w(g).
Since P1 is a shortest path, u € Ntk(f). Therefore either v € Ntk(f) or v € N0(f). Suppose v € Ntk(f). Then since z € Nz(f), the shortest v,z-path does not pass f which is not possible by condition (2). Therefore v € N0(f). By a similar argument it follows that if x € Nv(e) then x € N0(f). We conclude that
cu
Nv (e) C N0(f). Using a similar argument for the edge g, we also get Nu(e) C Na(g).

o
u
a
10 in
0 o
1
CO ^
CO CO

Nv(e)
m
CD
Jh
CD
m
u
a
CD U
cu
No(e)
Figure 1: Situation from the proof
Since Wr € N0(/) we have d(tk,wr) = w(g) + d(ys,yr+i)- Moreover, as tk we have d(tk, wr) = w(/) + d(ys,yr+1), Therefore w(/) = w(g).
We next prove that wr = v and tk = u. Since (e) C N0(/) and P2 is a shortest path, the computation
d(tk ,wr-1) = d(z,wr-1)
= d(z, yr+l) + w(g) + d(wr,wr-l) = d(tk ,wr)+ d(wr ,wr-1) > d(tfc ,wr-1)
gives a contradiction. Thus v = wr. By a similar argument tk = u. On the other hand, we have w(/) = w(g). Then d(u, z) = d(v,yr+1). But we also have d(u, z) = d(v,z) = d(v,yr+1)+d(z,yr+1) = d(v, z)+d(z, yr+1). Hence z = ys = yr+1.
We conclude that the edges e, /, and g form a triangle in G and since v € N0(/) we have w(e) = w(/) = w(g).
Claim 2: There is no vertex w € (e),w = v, such that w is adjacent to some vertex in N0(e).
Suppose on the contrary that there is a vertex w = v adjacent to z' € N0(e). Set I = wz'. Since the shortest u, w-path passes e, we infer that u € N0(l). So, if w(e) = a and d(v, w) = ^ then d(z', u) = a + Let z € N0(e) be the last vertex of path P : z',..., z, u. We proved before that z is adjacent to v and w(uz) = w(vz) = a, hence d(z,z') = On the other hand, v € (I). Indeed, if v / (I) then the shortest v, z'-path is of length at most On the other side, the distance between u and z' is a + so d(v,z') > a contradiction. Similarly, z € Nz'(I). But the shortest v,z-path does not pass I, a contradiction with condition (2).
Claim 3: If z, z' € N0(e) are adjacent to u and v, then z and z' are adjacent.
o
CM
CM
u
Suppose z and z' are not adjacent. By Claim 1 we know that w(uv) = w(uz) = w(vz) = w(uz') = w(vz') = a. The two distinct paths z,u, z' and z,v,z' have the same length 2a. By condition (1), there exists a (unique) shortest z,z'-path L : z, zi,..., zn = z' such that the length of L is less than 2a. By Claim 2, V(L) C N0(e). We now claim that d(z,z') = a. For this sake we show that z € N0(vz'). If z € Nv (vz') (or z € Nz' (vz')), then the shortest z, z'-path (z,v-path) does not pass the edge vz', a contradiction. Therefore z € N0(vz') and hence d(z,z') = d(v,z') = a. If z1 = z' nothing is to be proved. Suppose z = z', then by a similar argument as above we see that u, v € N0(zn-1z'). Thus d(zn-1,u) = d(zn-1,v) = a. On the other hand, zn-1 € Nz'(vz') and v € Nv(vz'), but the shortest v, zn-1-path does not contain the edge vz', a contradiction. Therefore, z and z' are adjacent.
From Claims 1, 2, and 3 we conclude that (G, w) is a block network and w is constant on each of its blocks.
o
3 Concluding remarks
Consider the network (K3,w), where V(K3) = {x,y,z} and w(xy) = w(yz) = 2 and w(xz) = 3. Note first that condition (1) from the previous section holds on (K3,w).
CM
On the other hand, let e = xy, then z € Ny(e) and (clearly) x € Nx(e), but the shortest x, z-path does not contain the edge e. So condition (2) does not hold. And indeed, W(K?,w) = 7 = 11 = Sz(K?,w).
Suppose now that (G, wV) is a vertex-weighted graph, that is, the graph G together with a weight function wV : V(G) — R+. In this case, the Wiener index W(G, wV) of (G, wV) is the sum, over all unordered pairs of vertices, of products of weights of the vertices and their distance [12], that is,
£ CO CO
CO
u
W(G,wv) = ^ uv(u)wv(v)d(u,v). 2
u=v
Let e = uv be an edge of (G, wV), then define nu(e) = ^teNu(e) wV(t) and set
Sz(G, wV) = ^ nu(e)nv (e).
e=uv
Theorem 2 Let (G,wV) be a vertex-weighted graph. Then Sz(G, wV) = W(G,wV)
if and only if every block of (G, wV) is a complete.
■ i
Proof. Similarly as in the beginning of the proof of Theorem 1, select shortest paths P^ P2,..., P(n) in (G, wV). Let Pi from this list be a shortest a, b-path, then we will denote it Pi(a, b). Define the path-edge matrix E = [eij] as follow:
wV(a)wV(b); ej € E(Pi(a, b)),
ij \0	ej € E(Pi(a,b)).
It is clear that the summation of the entries of the ith row of E is wV(a)wV(b)d(a, b). Thus, the summation of the entries of E is W(G,wV). It is easy to see that the
CM
i-H
o
CM CM
u
a
summation of the entries of the jth column of E is at most nu(ej)nv(ej), where ej = uv. It follows that Sz(G,wv) > W(G,wv)• So, equality holds if and only if the conditions (1) and (2) are fulfilled. Clearly, these conditions are equivalent to the condition that every block of (G, wv) is complete.	□
Acknowledgments
Supported in part by the Ministry of Science of Slovenia under the grant P1-0297. The first author is also with the Institute of Mathematics, Physics and Mechanics, Ljubljana. The second author would like to express his sincere gratitude to Professors A. R. Ashrafi and G. Y. Katona for their supervision and guidance.
References
[1]	M. Aouchiche, P. Hansen, On a conjecture about the Szeged index, European J. Combin. 31 (2010) 1662-1666.
[2]	M. Arezoomand, B. Taeri, Applications of generalized hierarchical product of graphs in computing the Szeged index of chemical graphs, MATCH Commun. Math. Comput. Chem. 64 (2010) 591-602.
CO
[3]	A. Dobrynin, I. Gutman, Solving a problem connected with distances in graphs, Graph Theory Notes New York 28 (1995) 21-23.
[4]	I. Gutman, A. A. Dobrynin, The Szeged index—a success story, Graph Theory Notes N. Y. 34 (1998) 37-44.
CO
[5]	H. Hua, S. Zhang, A unified approach to extremal trees with respect to geometric-arithmetic, Szeged and edge Szeged indices, MATCH Commun. Math. Comput. Chem. 65 (2011) 691-704.
[6]	A. Ilic, S. Klavzar, M. Milanovic, On distance-balanced graphs, European J. Combin. 31 (2010) 733-737.
[7]	J. Jerebic, S. Klavzar, D. F. Rall, Distance-balanced graphs, Ann. Combin. 12 (2008) 71-79.
[8]	P. Khadikar, N. Deshpande, P. Kale, A. Dobrynin, I. Gutman, G. Domotor, The Szeged index and an analogy with the Wiener index, J. Chem. Inf. Comput. Sci. 35 (1995) 547-550.
£
[9]	M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi, A matrix method for computing Szeged and vertex PI indices of join and composition of graphs, Linear Algebra Appl. 429 (2008) 2702-2709.
Jh
i-H
o
u
a
u
a
CD U
[10]	M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi, S. G. Wagner, Some new results on distance-based graph invariants, European J. Combin. 30 (2009) 1149-1163.
[11]	H. Khodashenas, M. J. Nadjafi-Arani, A. R. Ashrafi, I. Gutman, A new proof of the Szeged-Wiener theorem and a new characterization of block graphs, Kragu-jevac J. Math. 35 (2011) 165-172.
[12]	S. KlavZar, I. Gutman, Wiener number of vertex-weighted graphs and a chemical application, Discrete Appl. Math. 80 (1997) 73-81.
lO
[13]	S. KlavZar, A. Rajapakse, I. Gutman, The Szeged and the Wiener index of graphs, Appl. Math. Lett. 9 (1996) 45-49.
i—l
[14]	M. J. Nadjafi-Arani, H. Khodashenas, A. R. Ashrafi, On the differences between Szeged and Wiener indices of graphs, Discrete Math. 311 (2011) 2233-2237.
£
[15]	M. J. Nadjafi-Arani, H. Khodashenas, A. R. Ashrafi, Graphs whose Szeged and Wiener numbers differ by 4 and 5, Math. Comput. Modelling 55 (2012) 1644-1648.
o
[16]	T. Pisanski, M. Randic, Use of the Szeged index and the revised Szeged index for measuring network bipartivity, Discrete Appl. Math. 158 (2010) 1936-1944.
(N
[17]	S. Wagner, H. Wang, On the parity of the Wiener index, European J. Combin. 30 (2009) 996-1004.
CO
[19]	Z. You, B. Liu, Note on the minimal Wiener index of connected graphs with n vertices and radius r, MATCH Commun. Math. Comput. Chem. 66 (2011) 343-344.
[20]	R. Xing, B. Zhou, On the revised Szeged index, Discrete Appl. Math. 159 (2011) 69-78.
m
CD
$H
CD
m
[18] X. Wu, H. Liu, On the Wiener index of graphs, Acta Appl. Math. 110 (2010) 535-544.