IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 51 (2013), 1192
ISSN 2232-2094
IMPROVED BOUNDS ON
THE DIFFERENCE BETWEEN THE SZEGED INDEX AND THE WIENER INDEX OF GRAPHS
Sandi Klavzar M. J. Nadjafi-Arani
Ljubljana, October 29, 2013
Improved bounds on the difference between the Szeged index and the Wiener index of graphs
O
Sandi Klavzar a'b'c	M. J. Nadjafi-Arani* d
October 22, 2013
a Faculty of Mathematics and Physics, University of Ljubljana, Slovenia sandi.klavzar@fmf.uni-lj.si
b Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia c Institute of Mathematics, Physics and Mechanics, Ljubljana d Department of Mathematics, Sungkyunkwan University, Suwon 440-746, Republic of
CO
Let W(G) and Sz(G) be the Wiener index and the Szeged index of a connected graph G. It is proved that if G is a connected bipartite graph of order n > 4, size m > n, and if i is the length of a longest isometric cycle of G, then Sz(G) - W(G) > n(m - n + i - 2) + (i/2)3 - i2 + 2i. It is also proved if G is a connected graph of order n > 5 and girth g > 5, then Sz(G) - W(G) > PIv(G) - n(n - 1) + (n - g)(g - 3) + P(g), where PIv(G) is the vertex PI index of G and P is a cubic polynomial. These theorems extend related results from [Chen, Li, Liu, European J. Combin. 36 (2014) 237-246]. Several lower bounds on the difference Sz(G) - W(G) for general graphs G are also given without any condition on the girth.
Key words: Wiener index; Szeged index; isometric cycle; girth
HH
AMS Subject Classification (2000): 05C12, 05C35, 92E10
U _
* Corresponding author
CD U
Korea
mjnajafiarani@gmail.com Abstract
1 Introduction
The Wiener index W (cf. the surveys [6, 8]) and the Szeged index Sz (cf. the survey [9])
CM
CD
O
r
CM Gï
£ CO CO
are among the central graph invariants studied in mathematical chemistry. The Wiener
index is the first such index, it was introduced back in 1947 and extensively investigated
in the last decades. Clearly, the study of the Wiener index is equivalent to the study of the average distance, cf. [5, 28]. The Szeged index also received a lot of attention. In particular, it was recently applied for measuring network bipartivity [32] and to characterize connected graphs G or order n and size m with Sz(G) = mn2/4 as the connected, bipartite, distance-balanced graphs [1, 15]. It was earlier conjectured in [18] that these graphs can be characterized as regular bipartite graphs.
The introduction of the Szeged index was in particular motivated by the classical Wiener algorithm that for a given tree returns its Wiener index. Consequently, the Wiener index and the Szeged index coincide on trees, hence it is not surprising that a lot of research has been done on the relation between these two indices on general graphs. First, Sz(G) > W(G) holds for any connected graph [24], see [19] for an alternative short proof of this fact. The so-called Szeged-Wiener theorem states that Sz(G) = W(G) holds if and only if G is a block graph [7]. The theorem was recently and apparently independently rediscovered in [2]; yet another proof of it, together with a new characterization of block graphs, can be found in [19]. Very recently, in [23], the Sz(G) > W(G) result was extended to networks, more precisely, it was proved that Sz(G, w) > W(G, w) holds for any connected network, where Sz(G, w) and W(G, w) are the Szeged index and the Wiener index of the network (G, w). An analogous result holds for vertex-weighted graphs.
In [30, 31] a matrix method was applied in order to classify the graphs G for which Sz(G) — W(G) G {2,4, 5}. In addition, it is proved that there exists no graph G for which Sz(G) — W(G) G {1,3}, and that for any positive integer n = 1,3 there exists a graph G with Sz(G) — W(G) = k. In this direction, the computer program Auto-GraphiX conjectured (as reported at the talk [13]) that for a connected nonbipartite graph G of order n > 5 and girth g > 5, the inequality Sz(G) — W(G) > 2n — 5 holds. The same program also conjectured that for a connected bipartite graph G of order n > 4 and size with m > n, Sz(G) — W(G) > 4n — 8 holds. Very recently Chen, Li, and Liu [4] proved these two conjectures, see also [3] for an alternative proof in the bipartite case.
The main results of this paper are improvements of the above mentioned theorems from [4]. In Section 2 we prove a lower bound on the difference Sz(G) — W(G) for bipartite graphs G that involves the order n, the size m, and the length £ of a longest isometric cycle of G. The new bound extends the 4n — 8 bound as soon as at least one of the conditions m > n + 2 and £ > 6 hold. In the remaining small cases explicit expressions for Sz(G) — W(G) can be given. Then, in Section 3, we extend the 2n — 5 bound for general graphs G of order n > 5 and girth g > 5 with a bound that involves the order and the girth of G and extends the 2n — 5 bound in all cases. We conclude the paper with several lower bounds without any condition on the girth and use them to give a partial answer to a conjecture from [31].
o
o
o
In the rest of the section we define concepts used in this paper and recall some known related results.
We consider the usual shortest path distance and write dG(u, v) for the distance in a graph G between u and v and simplify the notation to d(u, v) when the graph is clear from the context. A subgraph of a graph is called isometric if the distance between any
CD
two vertices of the subgraph is independent of whether it is computed in the subgraph or in the entire graph. The Wiener index W(G) of a (connected) graph G is defined with
W(G) = ^ d(u,v).
{u,v}CV (G)
If G is a connected graph and e = uv e E(G), then set
Nu(e) = {x e V(G) | d(x, u) < d(x, v)} ,
i—l
and
Nv(e) = {x e V(G) | d(x, u) > d(x,v)} .
d
Let in addition nu(e) = |Nu(e)| and nv(e) = |Nv(e)|. Then the Szeged index of G and the vertex PI index of G (the latter index being introduced in [17], see also [25] and references therein) are respectively defined with
o	^
Sz(G) =	n«(e) ■ nv(e),
e=uveE(G)
and
Plv(G) = ^ nu(e)+ nv(e).
e=uv€E(G)
Considering a BFS-tree for each of the vertices of G if follows easily that
CO
Plv (G) > n(n - 1).
I-H
For the class of graphs Xn that attain this bound see [29, Theorem 2].
Finally, we will also make use of the first Zagreb index which is defined as
Mi(G)= £ deg(u)2,
vev (G)
where deg(u) is the degree of the vertex u.
CD
2 The bipartite case
V)
For bipartite graphs, Chen, Li, and Liu proved the following result, verifying a conjecture posed by the computer program AutoGraphiX:
This result is also proved in [3, Theorem 2.2]. Note that the lower bound involves the number of vertices but not the number edges. In addition, the family of extremal graphs is unicyclic with the unique cycle being of length four. These observations motivated us to search for a lower bound that would involve also the number of edges and were able to prove:
o O
cm
o
Gï
co
Theorem 2.1 [4, Theorem 3.2] Let G be a connected bipartite graph of order n > 4 and size m > n. Then Sz(G) — W(G) > 4n — 8. Moreover, the equality holds if and only if G is composed of a cycle C4 on 4 vertices and a tree T on n — 3 vertices sharing a single vertex.
Theorem 2.2 Let G be a connected bipartite graph of order n > 4 and size m > n. If £ is the length of a longest isometric cycle of G, then
Sz(G) - W (G) > n(m - n + £ - 2) + ^ 0 - £2 + 2£.
Pro of. Let V (G) = [x\,... ,xn}, E (G) = (ei,... ,em}, and let Y be an ordered list of all (n) unordered pairs of vertices of G. Define the matrix A = [a^] of dimension (n) xm
as follows. Its rows correspond to the elements of Y, its columns to the elements of E(G). If the row i corresponds to the pair {x, y} and the column j to the edge ej = uv, then set
i
( 1; {x,y}(l{u,v} = 0 and 00	aij = < (x € Nu(ej) and y e Nv(ej)) or (x e Nv(ej) and y G Nu(ej)),
cm	0; otherwise.
CM
Note that the sum of the entries of the jth column is equal (nu(ej) — 1)(nv(ej) — 1). Hence
(n)
(2) m	m
aij = ^(nu(e3 ) — 1)(nv (ej) — 1) i=1 j=1 j=1
mm
= nu(ej)nv (ej) — ^ (nv(ej) + nv (ej)) + m
= Sz(G) — PIv (G) + m,	(1)
= Sz(G) — m(n — 1),	(2)
•in
where we have used the fact that since G is bipartite, PIv(G) = mn holds.
Let ^x,y be the sum of the entries of the row of A corresponding to the pair {x, y},
so that eH Em=1 aij = T,{x,y} Px,y. Set
, ( ^x,y - d(x, y) + 2; d(x,y) > 2, x,y ;	otherwise.
CD
o
c^
$H
CD
o
O
o
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
$H
a
CD Jh
Then we have
(x,y}€(V 2G))
{x,y}	{x,y}
xy/E(G)	xyeE(G)
Y1 + d(x,y) - 2) + X)

{x,y} xy / E(G)
{x,y} xy e E(G)
nN
£ + (W(G) - m) - 2^ (n)
{x,y}	V V 7
m
E + W(G) + m - n(n - 1).
(3)
{x,y}
Combining (2) with (3) we obtain
Sz(G) - W(G) = ^ + n(m - n + 1).
(4)
{x,y}
Let C = ... u^ui be a longest isometric cycle of G and set - = 2k. Such a cycle exists since G contains cycles (because m > n) and since a shortest cycle of a graph is always isometric, cf. [12, Proposition 3.3]. Let xy be an edge of C and let e' = x'y' be the antipodal edge of xy on C, where d(x,x') < d(x,y'). Then x e nx/(e') and y e ny(e'), hence > 1. Therefore, ^{x,y},xyee(c) > - Similarly, if x,y e V(C) and d(x, y) = 2 with z a common neighbor of x and y on C, then considering the antipodal edges to xz and zy we infer that > 2. Since there are - pairs of vertices at distance 2 on C, we thus have ^{x y} x yeV(C) d(x y)=2 > 2-. Proceeding analogously we find out that {x y} x (C) d(x y)=r ^X , y > r- holds for r < k - 1. Finally, there exist k pairs of vertices at distance k on C, and we infer that for any such pair, > k - 2. Putting this together we obtain:
fc-i
E > - ' E i + k(k - 2) = k(k2 - 2) = - ((-/2)2 - 2) .
(5)
{x,y}
x,y e V (C)
i=1
Let next y be an arbitrary vertex from V(G) \ V(C). Let z be a vertex from C such that d(y,z) = d(y,C). (There can be more than one such vertex but we select and fix one of them.) We may assume without loss of generality that z = u1. Let x e V(C), x = z. Let P be a shortest x,y-path and let P' = P be a x,y-path that is shortest among all x, y-paths different from P. (So P' actually need not be a shortest x, y-path.) Note that P' exists because the cycle C guarantees that there exist at least two x, y-paths. If there are more selections for P' we select one that has most common vertices with P. Then P A P' is a cycle, denote it C'. Let x' be the vertex of C' n P n P' closest to x and let y' be the vertex of C' n P n P' closest to y.
Suppose first that |C'| > 4. If e = uv is an edge of C' n P, then for its opposite edge e' = u'v' e C' n P' we can use the same argument as in the proof of [4, Lemma
o
2.4] that x G N'u(e') and y G NV(e') (or vice versa). As |C"| > 4, at least one of these edges is incident to neither x nor y, hence ^'x,y > 1. Assume now that |C'| = 4. If d(x', y') = 1 then consider the edge of C' opposite to x'y' to reach the same conclusion, that is, > 1. If d(x',y') = 2, then P' is also a shortest x,y-path. Now, if x = x' then we consider the edge x't such that t G P' n C'. In this case x G NX (x't) and y G Nt(x't). The case when y = y' is treated analogously. It means that ^'x,y > 1 holds also in this case.
Consider finally the case x = x', y = y', |C'| = 4 and d(x,y) = 2. Then |P| = |P'| = 2. We may without loss of generality assume that P does not pass the edge e = uiu2. Since G is bipartite and C is isometric, u G NU2 (e) and y G NU1 (e) holds for i = 3,..., k + 1. Consequently, ^'Ui,y > 1 holds for i = 3,..., k + 1. Using a parallel argument for the edge f = u1ug we also find out that ^'Ui,y > 1 holds for i = k + 2,...,£ - 1.
In conclusion, for any of the (n — £) vertices y not on C there are £ — 3 vertices x on C such that ^'xy > 1, therefore,
O	,
^,y > (n — £)(£ — 3).	(6)
{x,y} xeC,y(/C
c^
u
CD
o
o
r
CSI
£ CO CO
CD
Plugging (6) and (5) into (4) we get
2
which is equivalent to the claimed result.	□
o
Sz(G) - W(G) > - ((0/2)2 - ^ + (n - 0)(0 - 3) + n(m - n + 1),
CSI
Note that the bound of Theorem 2.2 extends the bound of Theorem 2.1 as soon as at least one of the conditions m > n + 2 and - > 6 hold. For instance, if - = 6, then Theorem 2.2 reduces to Sz(G) - W(G) >
then the theorem asserts Sz(G) - W(G) > 4n. In the small cases in which Theorem 2.2 does not extend the bound of Theorem 2.1, exact expressions for the difference between the Szeged and the Wiener index can be stated (and so there is no need to give a bound on the difference.) Let's have a brief look to these cases.
Suppose that m = n and - = 4. In other words, suppose that G is a connected unicyclic graph whose only cycle is a 4-cycle u\u2u3u4. Then G isometrically embeds into a hypercube and hence the cut method (see [20, 22] for more on the method) applies for the Szeged index [10] as well as for the Wiener index [21]. More precisely, let n' be the number of vertices in one of the connected components of G - |uiu2, u3u4} and let n'' be the number of vertices in one of the connected components of G - {u1u4,u2u3}. Then it readily follows from the main theorems of [10] and [21] that Sz(G) - W(G) = n'(n-n')+ n''(n-n'') = W(G) and hence Sz(G) = 2W(G). This fact was also noticed in [16] for unicyclic graph with even cycles, while the expression for Sz(G) - W(G) in arbitrary unicyclic graph is given in [11, Eq. (8)].
Assume now that m = n + 1 and - = 4. Then G contains (at least) two 4-cycles C' and C''. If C' and C'' are in different blocks of G or if they share exactly one edge, then
o
o
o
o
o
CO
$H
a
CD
$H
G again embeds isometrically into a hypercube and hence the main theorems of [10] and [21] can be applied once more to obtain an explicit expression for Sz(G) — W(G). Finally, if C' and C'' share two edges, then G consists of a K2,3 with trees attached to each of its vertices. Then it is not difficult to express Sz(G) — W(G) as a function of the orders of the trees attached to each of the vertices of K23. We omit the details.
Jh
CD
We conclude the section with the following remarks.
Remark 2.3 One could replace the length of a longest isometric cycle in G in the statement of Theorem 2.2 with a more common girth of G. In this way a weaker bound would be obtained with a more common invariant involved. However, no such replacement is needed because also from the practical point of view the length of a longest isometric cycle is not an obstruction. The reason is that Lokshtanov [27] proved an appealing result that one can find a longest isometric cycle in a graph in polynomial time.
Remark 2.4 Let Sz*(G) be the so-called revised Szeged index. This graph invariant was introduced in [33] (under the name revised Wiener index) and named revised Szeged index in [32], see also [26, 34]. Since Sz*(G) = Sz(G) holds for any bipartite graph G, the results of this section apply to the difference Sz*(G) — W(G).
3 The general case
i
For general graphs, Chen, Li, and Liu proved the following result, again verifying a conjecture posed by AutoGraphiX:
Theorem 3.1 [4, Theorem 3.1] If G is a connected, nonbipartite graph of order n > 5 and girth g > 5, then Sz(G) — W(G) > 2n — 5. Moreover, equality holds if and only if G is composed of C5 and one tree rooted at a vertex of the cycle C5 or two trees, respectively, rooted at two adjacent vertices of the cycle C5.
For an integer t set
f 2 ((t/2)2 — 2) ; t even,
£ CO CO
P(t) = \ 2(¥)(); todd. We now extend Theorem 3.1 as follows:
Theorem 3.2 If G is a connected graph of order n > 5 and girth g > 5, then
CD
Sz(G) — W(G) > PIV (G) — n(n — 1) + (n — g)(g — 3) + P(g).
CD
Proof. Define the matrix A = [aj] in the same way as in the proof of Theorem 2.2. Then Equations (1) and (3) hold for arbitrary graphs (that is, not only for bipartite) and give us
Sz(G) — W(G) > PIV(G) — n(n — 1) + ^ , y .	(7)
x,y
Let C = uoui...ug-1u0 be a shortest cycle of G. Then C is an isometric cycle. If g is even and x,y e C, then by analogous argument as in the proof of Theorem 2.2 we see that
E <y > 2 ((g/2)2 - 2) .	(8)
x,yea
Suppose next that C is odd and let g = 2k + 1. If x,y e V(C) and d(x,y) = 2 with z a common neighbor of x and y, then, since C is an isometric odd cycle, for the edge e = uv that is antipodal to z on C we have d(z,u) = d(z,v). Therefore, x e Nu(e) and y e (e) (or the other way around), thus ^X,y > 1. When d(x,y) = i > 3, the same reasoning yields > i — 1. Since there are g pairs of vertices of C that are at distance i, we conclude that
S	E <y > gE (i — D = 2 (^^)(Sr).	(9)
o

x,y€C	i=2
Next, suppose that x e V(C) and y e V(C). Let z be a vertex from C such that d(y, z) = d(y, C). We may without loss of generality assume that z = u0. Suppose that P is a shortest x,y-path and let P' be an x,y-path that is shortest among all other paths. Among all possible such paths select P' such that it has the largest possible number of common vertices with P. Then C' = P A P' is a cycle. Let x' (resp. y') be the vertex of C' n P n P' closest to x (resp. y). Then dC'(x', v) = dG(x', v) (resp. (dc(y', v) = dG(y', v)) holds for any vertex v e C'.
Case 1. C' is an even cycle.
Suppose that e e P n C' and f = ab e C' is the edge opposite to e. By [4, Lemma 2.4 (1)], x e Na(f) and y e Nb(f) (or the other way around). Since g > 5 we get that
^x,y > 1.
Case 2. C' is an odd cycle.
By [4, Lemma 2.4 (2)], if |E(P) n V(C')| > 2, then > 1. We now claim that if x = ui, where i = 0,1,g — 1, then |E(P) n E(C')| > 2. Assume on the contrary that P and C' share only one edge. Set m = d(x,y) and t = d(y,z). Then since |C'| > g, we have |P'| > m + g — 2. On the other hand (recalling that x = ui, i = 0,1,g — 1), we observe that |P'| < t + g — 2. It follows that m + g — 2 < |P'| < t + g — 2. Since clearly t < m, we conclude that t = m and |P'| = t + g — 2. Consider now the path Q from y to x = ui that is a concatenation of a shortest y, z-path and a shortest z, x-path on C. Since t = m and d(y, C) = t, the path P uses no edge of C. It follows that Q = P. But since |Q| < t + (g — 1)/2 we have a contradiction because Q is shorter than P' (which is a second shortest y, x-path). This proves the claim which in turn implies that ^'Ui,y > 1 holds for any i = 0,1,g — 1. It follows that
E
CO
<y > (n — g)(g — 3).	(10)
{x,y}
xeC,y</C
u
The theorem now follows by combining Equations (7), (8), (9), and (10).	□
o

CO CD
Jh
CD CO
Jh
a
CD
$H
As we have already observed, PIv(G) > n(n — 1) holds for any graph G. Hence the bound of Theorem 3.2 is better than the bound of Theorem 3.1 for any graph G.
Note that in the proof of Theorem 3.2 we did not use the assumption on girth in order to obtain Equations (7), (8), and (9). Since in addition n > g clearly holds, the following result holds for arbitrary graphs:
£1
Corollary 3.3 If G is a connected graph of order n and girth g, then § ...........
Modifying the arguments from the proof of Theorem 3.2 to general graphs we also
get:
Corollary 3.4 If G is a connected graph of order n and girth g, then
Sz(G) — W(G) > (n — g)(g — 3) + P(g) .
o
Proof. Define the matrix B = [bij] as follows:
b i 1; (x e Nu(ej) and y e Nv(ej)) or (x e Nv(ej) and y e Nu(ej)), ij 0; otherwise.
o	1 ;
Then the sum of the entries of the column ej is nu(ej)nv (ej) and the sum of the entries from the row which corresponds to the pair {x,y} is the number of edges e = uv
such that x and y respectively belong to Nu(e) and Nv(e). Let lx,y be the row sum corresponding to the pair {x,y}. Setting yX y = Yx,y — d(x,y) we find that
Sz(G) = ^ nu(ej)nv(e3) = ^ lx,y = £ ix>y + W(G).	(11)
J'i'vy^j )
x,y	x,y
CO
CO As already mentioned, to obtain Equations (8) and (9) we do not need the girth assumption, that is,
£ yX,v > p(g).
x,y£V (C)
Let next x e V(C) and y e V(C). If C is an even cycle, then yX,y > 1 holds by [4, Lemma 2.4 (1)], and if C is odd, then by an argument similar to Case 2 in the proof of Theorem 3.2 we get that Yui>y > 1 holds for each i = 0,1,g — 1. It follows that
ix y > (n - g)(g - 3)
xeV (C),y<£V (C)
Plugging the above inequalities into (11) the result follows.	□
For a graph G, let t(G) denote the number of triangles of G. Then we also have:
o
o
o
o
CO CD
CD CO
Corollary 3.5 If G is a connected graph of order n > 5 and girth g > 5, then
Sz(G) - W(G) > Mi(G) - n(n - 1) + (n - g)(g - 3) + P(g). In particular, if G is a k-regular, then
Sz(G) - W(G) > n(k2 - n + 1) + (n - g)(g - 3) + P(g).
Proof. Combine Theorem 3.2 with the fact proved in [14] that PIv(G) > Mi(G)-6i(G) holds for any connected graph G. Since g > 5, we have t(G) = 0 as desired. The assertion for regular graphs then follows because M1(G) = nk2 when G is k-regular. □
For the cases g = 3 and g = 4 weaker bounds can be obtained using Corollary 3.3. We conclude the paper with some comments on the following conjecture from [31].
Conjecture 3.6 Let G be a graph of order n and let Bi,..., Bk be blocks of G, none of them being complete. Let |V(Bj)| = m, 1 < i < k. Then Sz(G) - W(G) > ¿k=1(2ni - 6) = 2n - 8k + 2.
The conjecture was proved in [31] for chordal graphs. Using Theorems 2.2 and 3.2 it is easy to see that the conjecture is true when G is bipartite or g > 5. Also if g = 4 and ¿(G) is the minimum degree of G, then Corollaries 3.3 and 3.5 together with a simple calculation yield the validity of Conjecture 3.6 for graphs G with ¿(G) > a/|V(G)| + 1.
ro
Acknowledgments
This work has been financed by ARRS Slovenia under the grant P1-0297 and within the EUROCORES Programme EUROGIGA/GReGAS of the European Science Foundation.
HH
References
[1]	M. Aouchiche, P. Hansen, On a conjecture about the Szeged index, European J. Combin. 31 (2010) 1662-1666.
[2]	A. Behtoei, M. Jannesari, B. Taeri, A characterization of block graphs, Discrete Appl. Math. 158 (2010) 219-221.
[3]	L. Chen, X. Li, M. Liu, I. Gutman, On a relation between Szeged and Wiener indices of bipartite graphs, Trans. Comb. 1 (2012) 43-49.
[4]	L. Chen, X. Li, M. Liu, The (revised) Szeged index and the Wiener index of a nonbipartite graph, European J. Combin. 36 (2014) 237-246.
[5] P. Dankelmann, Average distance in weighted graphs, Discrete Math. 312 (2012) 12-20.
[6] A. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001) 211-249.
CM	[7] A. A. Dobrynin, I. Gutman, Solving a problem connected with distances in graphs,
Graph Theory Notes New York 28 (1995) 21-23.
[8] A. A. Dobrynin, I. Gutman, S. KlavZar, P. Zigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002) 247-294.
o O
o Ö
CO CO
u
[9] I. Gutman, A. A. Dobrynin, The Szeged index—a success story, Graph Theory Notes N. Y. 34 (1998) 37-44.
CM [10] I. Gutman, S. Klavzar, An algorithm for the calculation of the Szeged index of benzenoid hydrocarbons, J. Chem. Inf. Comput. Sci. (35) (1995) 1011-1014.
[11] I. Gutman, L. Popovic, P. V. Khadikar, S. Karmarkar, S. Joshi, M. Mandloi, Relations between Wiener and Szeged indices of monocyclic molecules, MATCH Commun. Math. Comput. Chem. 35 (1997) 91-103.
[12]	R. Hammack, W. Imrich, S. Klavzar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
[13]	P. Hansen, Computers and conjectures in chemical graph theory, Plenanry talk at the International Conference on Mathematical Chemistry, August 4-7, 2010, Xiamen, China.
[14] A. Ilic, Note on PI and Szeged indices, Math. Comp. Model. (2010) 1570-1576.
cm
[15]	A. Ilic, S. Klavzar, M. Milanovic, On distance-balanced graphs, European J. Com-bin. 31 (2010) 733-737.
[16]	P. V. Khadikar, P. P. Kale, N. V. Deshpande, V. K. Agrawal, On the Szeged index of monocyclic graphs J. Indian Chem. Soc. 77 (2000) 449-452.
[17]	P. V. Khadikar, S. Karmarkar, V. K. Agrawal, A novel PI index and its applica-tionsto QSRP/QSAR studies, J. Chem. Inf. Comput. Sci. 41 (2001) 934-949.
[18]	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.
[19]	H. Khodashenas, M. J. Nadjafi-Arani, A. R. Ashrafi, I. Gutman, A new proof of the Szeged-Wiener theorem, Kragujevac J. Math. 35 (2011) 165-172.
[20]	S. Klavzar, A bird's eye view of the cut method and a survey of its applications
CO
in chemical graph theory, MATCH Commun. Math. Comput. Chem. 60 (2008) 255-274.
[21] S. Klavzar, I. Gutman, B. Mohar, Labeling of benzenoid systems which reflects the vertex-distance relations, J. Chem. Inf. Comput. Sci. 35 (1995) 590-593.
CD
[22]	S. Klavzar, M. J. Nadjafi-Arani, Wiener index in weighted graphs via unification of 8*-classes, European J. Combin. 36 (2014) 71-76.
[23]	S. KlavZar, M. J. Nadjafi-Arani, Wiener index versus Szeged index in networks, Discrete Appl. Math. 161 (2013) 1150-1153.
CD
[24]	S. KlavZar, A. Rajapakse, I. Gutman, The Szeged and the Wiener index of graphs, Appl. Math. Lett. 9 (1996) 45-49.
o O
£ CO CO
[25] Z. Kovijanic Vukicevic, D. Stevanovic, Bicyclic graphs with extremal values of PI index, Discrete Appl. Math. 161 (2013) 395-403.
[26]	X. Li, M. Liu, Bicyclic graphs with maximal revised Szeged index, Discrete Appl. Math. 161 (2013) 2527-2531.
i—l
[27]	D. Lokshtanov, Finding the longest isometric cycle in a graph, Discrete Appl. Math. 157 (2009) 2670-2674.
o
[28]	S. Mukwembi, Average distance, independence number, and spanning trees, J. Graph Theory, in press, DOI: 10.1002/jgt.21758.
[29]	M. J. Nadjafi-Arani, G. H. Fath-Tabar, A. R. Ashrafi, Extremal graphs with respect to the vertex PI index, Appl. Math. Lett. 22 (2009) 1838-1840.
[30]	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.
CO
[31]	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.
[32]	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.
[33]	M. Randic, On generalization of Wiener index for cyclic structures, Acta Chim. Slovenica 49 (2002) 483-496.
[34]	R. Xing, B. Zhou, On the revised Szeged index, Discrete Appl. Math. 159 (2011) 69-78.
CO CD
$H
CD CO
$H
a
CD
$H