IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 50 (2012), 1174
ISSN 2232-2094
WIENER INDEX IN WEIGHTED GRAPHS VIA UNIFICATION OF e*-CLASSES
Sandi Klavžar M. J. Nadjafi-Arani
Ljubljana, April 12, 2012
Wiener index in weighted graphs via unification of
0*-classes
$H
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
in
c
o
csr
i
csr 00
Abstract
It is proved that the Wiener index of a weighted graph (G, w) can be expressed as the sum of the Wiener indices of weighted quotient graphs with respect to an arbitrary combination of ©""-classes. Here ©" denotes the transitive CM	closure of the Djokovic-Winkler's relation ©. A related result for edge-weighted
CM	graphs is also given and a class of graphs studied in [19] is characterized as
partial cubes.
CO	Key words: Wiener index; weighted graph; Djokovic-Winkler's relation; partial
cube
AMS Subject Classification (2000): 05C12, 92E10 1 Introduction
l-H
The cut method (see the survey [14]) turned out to be utmost handy when dealing with distance-based graph invariants which are in turn among the central concepts of chemical graph theory. The method was initiated in [16] where it was shown how cuts can be used to compute the Wiener index (alias average distance) of graphs which admit isometric embeddings into hypercubes. These graphs are know as partial cubes. About ten years later, the result was extended in [13] to general graphs by establishing a connection between the Wiener index of a graph and its canonical metric representation. (The result of [16] is then obtained by specializing
Oh
'Corresponding author

o
csf
to bipartite graphs.) The latter representation is due to Graham and Winkler [9], while in [1] a recent application of the main result from [13] can be found.
Our primary motivation for this paper was the recent paper [19] in which it is demonstrated that the cut method is applicable also to the edge-Wiener index [6, 12] and the edge-Szeged index [10]. The results in [19] are stated for graphs that admit certain edge partitions. In Section 2 we show that these graphs are precisely partial cubes, a class of graphs extensively studied by now, cf. [2, 8, 17].
The main result of this paper, stated and proved in Section 3, is a generalization of the above mentioned theorem from [13]. The generalization is two-fold. First, the variety of factor graphs is extended by allowing arbitrary combinations of the edge classes from the canonical metric representation. Second, the result is extended
IN	to weighted graphs. We add here that very recently, Dankelmann [5] studied the
Wiener index (alias average distance) on trees, cycles, and graphs with minimum degree at least 2.
A special case of our main result should be mentioned here. In [4] it was demonstrated that the Wiener index of benzenoid graphs can be computed in linear time. The main idea is to merge all parallel cuts into a single set and to deduce the Wiener index from the three corresponding quotient graphs (that turned out to be trees [3]), cf. [4, Proposition 2]. This can be seen as another motivation for our investigation.
o
2 Preliminaries
C^
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 will be clear from the context. The Wiener index of G is the sum of distances between all pairs of vertices of G.
A subgraph of a graph is called isometric if the distance between any two vertices of the subgraph is independent of whether it is computed in the subgraph or in the entire graph. A subgraph of a graph is called convex if for any two vertices of the subgraph all shortest path (from the entire graph) between then belong to the subgraph. For a connected graph G and an edge ab of G we set Wab = {x € V(G) | d(x, a) < d(x, b)}. Note that if G is bipartite then V(G) = Wab U Wba holds for any edge ab. By abuse of language we consider (when appropriate) Wab also as the subgraph induced by Wab.
The Cartesian product G □ H of graphs G and H is the graph with vertex set V(G) x V(H) where the vertex (g,h) is adjacent to the vertex (g',h') whenever gg' € E(G) and h = hh, or g = g' and hhh € E(H).
For a graph G, the Djokovic-Winkler's relation 0 [7, 18] is defined on E(G) as
¡5 CO CO
CD
follows. If e = xy € E(G) and f = uv € E(G), then e©f if d(x,u) + d(y,v) = d(x, v) + d(y,u). Relation © is reflexive and symmetric, its transitive closure ©* is hence an equivalence relation. The partition of E(G) induced by ©* will be called the ©*-partition.
A weighted graph (G,w) is a graph G = (V(G),E(G)) together with the weight
i-H
o
u
o
CSF
CO CD
U
CD
function w : V(G) ^ R+. The Wiener index W(G, w) of (G, w) is defined as [15]:
1
W(G,w) = - y	u'(u) w(v) dc(u,v)
«ev(G) vev(G)
Clearly, if w = 1 then W(G, w) = W(G).
As already mentioned in the introduction, the cut method was developed in [19] for the edge-Wiener/Szeged index. More precisely, the method was developed for graphs G that admit a partition {Fi} of the edge set such that G \ Fi is a two component graphs with convex components. We close this section by pointing out that these graphs are precisely partial cubes.
IN
Proposition 2.1 Let G be a connected graph. Then G admits a partition {Fi} of E(G) such that G \ Fi is a two component graphs with convex components if and only if G is a partial cube.
o
Proof. It is well-known that if G is a partial cube, then the 0*-partition has the required property.
Suppose now that G is an arbitrary connected graph that admits a partition as stated. Then G is bipartite cf. [19, Theorem 2]. Indeed, consider a shortest odd cycle C of G. Since G\Fi has two (convex) components, either |CnFi| = 0 or |CnFi| > 2 holds for any i. As C is odd, there exists an index j such that |C n Fj| > 3. But then G \ Fj cannot consist of two convex components.
00	We now claim that if e = ab € Fi, then the two connected components C' and
C" of G \ Fi are induced by the sets Wab and Wba. Clearly, a and b are in different components, hence assume without loss of generality that a € C' and b € C". Let x € V(G), x = a,b. Since G is bipartite, d(x,a) = d(x,b). We may assume without loss of generality that d(x, a) < d(x, b). If x € C" then a shortest x, a-path together with the edge ab is a shortest x, b-path. But then C" is not convex. Therefore, x € C' which in turn implies that C' = Wab and similarly C" = Wba. The proof is complete by recalling the classical Djokovic's theorem from [7] asserting that a connected graph is a partial cube if and only if it is bipartite and all the subgraphs Wab are convex.	□
3 The main result
In this section we prove that the Wiener index of a connected weighted graph can be expressed as the sum of the Wiener indices of weighted quotient graphs with respect to an arbitrary combination of 0*-classes. Hence let G be a connected graph and let F = {Fi,..., Fk} be the 6*-partition of G. Let E = {Ei,..., Er} be a partition of E(G), where each set Ei is the union of one or more 6*-classes. Then we say that E is a 0*-merging (and that E is a refinement of F).
Then every connected component of G \ Ej, 1 < j < r, induces a convex subgraph of
i
csf 00
£ CO CO
Lemma 3.1 Let G be a connected graph and let E = (Ei,..., Er} be a &*-merging. Th G.
Proof. Let C be a connected component of G \ Ej and suppose it is not convex in G. Then there exists vertices x, y € C and a shortest x, y-path P not all of its edges belonging to C. Let e be an edge from (P \ C) n Ej and assume that e is from the 6*-class Fi. Let Q be a x,y-path in C. Since P is a shortest path, e is in relation 0 with no edge on P, hence by [11, Lemma 11.4], e is in relation 0 with an edge f on Q. But this is not possible because then f does not belong to C.	□
Lemma 3.2 Let G be a connected graph and let E = (Ei,..., Er} be a 0*-merging. Let C and C' be connected components of G \ Ej and let x,y € V(C) and x',y' € V(C'). If P1 and P2 are shortest x,x'- and y,y'-paths in G, respectively, then
|E(Pi) n Ej| = |E(P2) n Ej|.
Proof. From the key lemma of [9] (see [11, Lemma 13.1]) we know that if R is a shortest u,v-path in G and Q is an arbitrary u,v-path in G, then |E(R) n F| < |E(Q) nF| holds for any 0*-class F. Because Ej is a union of one or more 0*-classes it follows that |E(R) n Ej| < |E(Q) n Ej|, 1 < j < r.
Consider now the shortest paths P1 and P2. Let in addition Q1 be an x,x'-path that is a concatenation of a shortest x,y-path in C, the path P2, and a shortest y',x'-path in C'. Similarly, let Q2 be a y,y'-path that is a concatenation of a shortest y,x-path in C, the path P1, and a shortest x',y'-path in C'. By the above, |E(P1) n Ej| < |E(Q1) n Ej| and |E(P2) n Ej| < |E(Q2) n Ej|. On the other hand, |E(P2) n Ej| = |E(Q1) n Ej| and |E(P1) n Ej| = |E(Q2) n Ej|. Therefore, |E(P1) n Ej| < |E(Q1) n Ej| = |E(P2) n Ej| < |E(Q2) n Ej| = |E(P1) n Ej| so that the equality holds everywhere.	□
Let G be a connected graph and let F1,..., Fk be a partition of E(G). Then the quotient graph G/Fi, 1 < i < k, is defined follows. Its vertices are the connected components of G \ Fi, two vertices C and C' being adjacent if there exist vertices x € C and y € C' such that xy € Fi.
We are now ready for the main result of this paper.
Theorem 3.3 Let (G, w) be a connected, weighted graph, and let E = (E1,..., Er} be a 0*-merging. Then
U	r
W(G, w) = £ W(G/Ej, wj), j=1
where wj : V(G/Ej) ^ R+ is defined with wj(C) = ^xeC w(x), for any connected component C of G \ Ej.
i-H
o
u
a
in
0 Ö
o
1
CO ^
CO CO
Proof. Let C and C' be two vertices of (G/Ei, wi) (that is, connected components of G\Ej), then by Lemma 3.2, d(G/Ej,Wj)(C, C') = |E(P)nEjwhere P is a shortest x, x'-path in G and x € C, x' € C'.
Select shortest paths Y = (Pi, P2,..., P(n)} in G such that for every pair of vertices u, v € V(G), u = v, there exists a unique shortest u, v-path in the list. Let M = [mjj] be the (2) x r matrix with entries mj = w(u)w(v)|E(Pj) n Ej |, where u and v are the endvertices of the path Pj.
Since ^j=1 |E(Pj) nEj| is equal to the distance between the endpoints of Pi, the sum of the entries of the ith row of M equals w(u)w(v)|E(Pi)|. Therefore, the sum of all entries of M is equal to W(G,w).
Let Cj,1,..., Cj,ij be the connected components of G\Ej and let |Cj,t| = The number of non-zero elements in the jth column of M is equal to the number of shortest path from Y that pass through the edges of Ej. By Lemma 3.1 every component Cj,t is convex, hence this number is equal to Y^p=1 %q=p+1 nj,pnj,i. Moreover, for any vertex u € Cj,p and any vertex v € Cj,q we have d(G/Ej,Wj)(Cj,p, Cj,q) = |E(Pi) nEj|, where u and v are the endvertices of Pi. Thus the summation of the jth column of M gives
Ew(Cj ,p)w(Cj,q)d(G/Ej,Wj)(Cj,p, Cj,q) • p,q
Summing over all columns we thus get:
jj
W (G, w)	w(Cj,p)w(Cjq )d(G/Ej ,Wj) (Cj,p, Cj,q) = ^ W (G/Ej ,wj )
j=i p,q
which completes the argument.
□
For an example illustrating Theorem 3.3 consider the family of graphs Gn, n > 3, illustrated in Fig. 1. Here n denotes the number of inner faces in one layer, so that the total number of the inner faces of Gn is 2n.
CO CD
$H
CD CO
u
a
CD U
Figure 1: Graphs Gn
Gn has 2(n — 2) + 1 = 2n — 3 B*-classes. We refine them to classes E1, E', E2, where E1 is shown in Fig. 2, E1' is constructed symmetrically (that is, containing the other horizontal edges of the hexagons), and E2 is formed by the remaining edges. In other words, E2 is the 6*-class that contains the edges of the pentagons and the vertical edges of the hexagons, see Fig. 3.
1
j
CM
i-H
O
CM
cm
u
a <
in
0 Ö
o
cm
1
cm CO cm cm
£ CO CO
e e 9 e ó
e e e e 10
Figure 2: Graphs On \ Ei and (On/Ei,w)
Figure 3: Graphs On \ E2 and (On/E2, w)
Now we have
m
CD
Jh
CD
m
u
a
CD U
W (On/Ei ,w) W (On/E2 ,w)
= W(On/Ei,w)=3(n - 2)(2n2 + 5n - 3)
16n2 + 76n - 28, so that
W (On) = W (O/Ei, w) + W (O/Ei, w) + W (O/E2, w) = 12n3 + 22n2 - 2n + 8.
o
CM
CM
u
o Ö
u
a
4 Concluding remarks
It is also natural to consider edge-weighted graphs, that is, pairs (G,wE), where G is a graph and wE : E(G) ^ R+. The Wiener index W(G, wE) of an edge-weighted graph (G,wE) is defined just as the usual Wiener index, that is, W(G,wE) = l'52u€V{G)'52v€V{G)d{u>v)> where the distance function is of course computed in (G,wE). Again, if all the edges have weight 1, then W(G,wE) = W(G).
With the methods parallel to those from Section 3 the following result can be proved:
Theorem 4.1 Let (G, wE) be a connected, edge-weighted graph. If E = [E\,..., Er} is a 0*-merging such that for any j = 1,... ,r, the edges from Ej have the same weight, w(Ej), then
W(G,wE) = £ w(Ej)W(G/Ej,wj). j=i
Acknowledgments
This work has been financed by ARRS Slovenia under the grant P1-0297 and within the EUROCORES Programme EURO GIGA / GReGAS of the European Science Foundation. The second author is also with the Institute of Mathematics, Physics and Mechanics, Ljubljana.
CM
References
[1]	A. R. Ashrafi, M.A. Zohreh, On Wiener index of one-heptagonal nanocone, Current Nanosci. 8 (2012) 180-185.
[2]	B. Bresar, T. Kraner Sumenjak, ©-graphs of partial cubes and strong edge colorings, Ars Combin. 93 (2009) 417-429.
[3]	V. Chepoi, On distances in benzenoid systems, J. Chem. Inf. Comput. Sci. 36 (1996) 1169-1172.
HH
[4]	V. Chepoi, S. KlavZar, The Wiener index and the Szeged index of benzenoid systems in linear time, J. Chem. Inf. Comput. Sci. 37 (1997) 752-755.
[5]	P. Dankelmann, Average distance in weighted graphs, Discrete Math. 312 (2012) 12-20.
CO
P. Dankelmann, I. Gutman, S. Mukwembi, H. C. Swart, The edge-Wiener index of a graph, Discrete Math. 209 (2009)3452-3457.
[7] D. Djokovic, Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263-267.
Jh
r
CM
i-H
o
CM cm
CO
CO CD
$H
CD CO
$H
a
CD Jh
[8]	D. Eppstein, Recognizing partial cubes in quadratic time, J. Graph Algorithms Appl. 15 (2011) 269-293.
[9]	R. L. Graham and P. M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (1985) 527-536.
[10]	I. Gutman, A. R. Ashrafi, The edge version of the Szeged index, Croat. Chem. Acta. 81 (2008) 277-281.
a
[11]	R. Hammack, W. Imrich, S. KlavZar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, 2011.
[12]	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.
i—l
[13]	S. KlavZar, On the canonical metric representation, average distance, and partial Hamming graphs, European J. Combin. 27 (2006) 68-73.
£
[14]	S. KlavZar, A bird's eye view of the cut method and a survey of its applications in chemical graph theory, MATCH Commun. Math. Comput. Chem. 60 (2008)
cm
[16]	S. KlavZar, I. Gutman and B. Mohar, Labeling of benzenoid systems which reflects the vertex-distance relations, J. Chem. Inf. Comput. Sci. 35 (1995)
2	590-593.
[17]	N. Polat, Netlike partial cubes. V. Completion and netlike classes, Discrete Math. 309 (2009) 4362-4376.
255-274.
[15] S. Klavzar and I. Gutman, Wiener number of vertex-weighted graphs and a chemical application, Discrete Appl. Math. 80 (1997) 73-81.
[18]	P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225.
[19]	H. Yousefi-Azari, M. H. Khalifeh, A. R. Ashrafi, Calculating the edge Wiener and Szeged indices of graphs, J. Comput. Appl. Math. 235 (2011) 4866-4870.