IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 49 (2011), 1145
ISSN 2232-2094
RELATIONSHIP BETWEEN EDGE-WIENER INDEX AND GUTMAN INDEX OF A GRAPH
Martin Knor Primoz Potocnik Riste Skrekovski
Ljubljana, March 14, 2011
o u ti
£
co co
CO
RELATIONSHIP BETWEEN EDGE-WIENER INDEX AND GUTMAN
INDEX OF A GRAPH
MARTIN KNOR, PRIMOZ POTOCNIK, AND RISTE SKREKOVSKI
Abstract. Wiener index W(G) of a connected graph G is defined to be the sum v d(u, v) of the distances between the pairs of vertices in G. Similarly, edge-Wiener index of G is defined to be the sum Y1 e f d(e,f) of the distances between the pairs of edges in G, or equivalently, the Wiener index of the line graph L(G). Finally, the Gutman index Gut(G) is defined to be the sum u v deg(u)deg(v)d(u, v), where deg(u) denotes the degree of a vertex u in G. In this paper we prove an inequality involving the edge-Wiener index and the Gutman index of a connected graph. In particular, we prove that We (G) > ± Gut(G) - ± | E(G) | + f k3 (G) + 3k4 (G) where nm (G) denotes the number of all m-cliques in G. Moreover, the equality holds if and if G is a tree or a complete graph. Using this result we show that We(G) > ^f±W(G) where 6 denotes the minimum degree in G.
cd
1. Introduction
i
For a graph G with vertex set V = V(G) and edge set E = E(G), let deg(u) and d(u, v) denote the degree of u a vertex u € V and the distance between vertices u,v € V, respectively. Let L(G) denote the line graph of G, that is, the graph with vertex set E and two distinct edges e, f € E adjacent in L(G) whenever they share an endpoint in G. Furthermore, for e, f € E, we let d(e, f) denote the distance between e and f in the line graph L(G).
In this paper we consider three important graph invariants, called Wiener index (denoted by W(G) and introduced in [10]), edge-Wiener index (denoted by We(G)) and Gutman index (denoted by Gut(G)), which are defined as follows:
w(G) = Yl = \ E
{u,v}CV	(u,v)eV2
1 2
[e,f}QE	(e,/)€E2
We(G) = Y d(e'/) = 2 £ d(e'/}'
Gut(G) = Y^ d,(u)d(v)d(u,v) = ^	d,(u)d(v)d(u,v).
z—j	2 —J
{u,v}cv	(«,v)ev2
CD
Note that edge-Wiener index of G is nothing but the Wiener index of the line graph L(G) of G. Note that in the literature a slightly different definition of the edge-Wiener index is sometimes used; for example, in [8] edge-Wiener index is defined to be We(G) + where We(G) is as defined above and n is the order of G.
Oh
Date: December 14, 2010.
Besides applications in chemistry (see for example [7]), Wiener index of a graph was studied also from a purely graph-theoretical point of view (for early results, see for example [6, 9], and [3] for a nice survey). Generalizations of Wiener index and relationship between these were studied in a number of papers (see for example [1, 4, 5, 8]).
The main result of the paper is the following inequality, involving the edge-Wiener index and the Gutman index of a connected graph:
A
o
lO
113 We(G) > -Gut(G) --\E{G)I + -K3(G) + 3k,4(G),	(*)
where by Km(G) we denote the number of m-cliques in G. In addition, we show that the
equality holds in (*) if and only if G is a tree or a complete graph.
As a consequence of (*), we prove the following inequality involving the Wiener index
and the edge-Wiener index of a connected graph G: i
We(G)>^-W(G), where 5 = 5(G) denotes the minimum degree in G.
2. The proof
Throughout this section, let G be a connected graph with vertex set V and edge set E. Further, we let A = {(u, v) : uv € E} stand for the arc set of G. Recall that for any two edges e = u\u2 and f = viv2 in E, the distance between e and f is defined as the distance dL(G)(e, f) between e and f in the line graph L(G), and observe that
(1)	d(uivi,U2v2) = min{d(ui,vj) : i, j € {1, 2}} + 1.
In addition to the distance between two edges, we will also consider the average distance
between the endpoints of two edges, defined by
1
s(u\u2,viv2) = ~(d,(ui,vi) +d(ui,v2) +d,(u2,v i) + d,(u2,v2)).
CO
The average distance of endpoints has an interesting relationship with the Gutman index of a graph. Namely, if one wants to consider the version of edge-Wiener index where the distances of edges in the sum are substituted by average distances of endpoints, then what one gets is essentially the Gutman index. More precisely, the following holds.
Lemma 2.1. Let G be a connected graph with vertex set V and edge set E. Then
\ E s(e,f) = -4Gut(G).
(e,f )eE2
CD
U
CD
Proof. Let A be the arc set of G. Then:
\ E s(e'/) = ^ E E \{d(uiA'i)+d(u2,vi)+d(ui,v2)+d,(u2,v2)). (+)
(e,f)eE2	(ui,U2)€A (vi,V2)eA
Now for each pair i, j € {1,2}, we see that
E E d(ui ,vj	E E d(u,v) =
(u1,u2)eA (v1 ,v2)eA	ueVu'ew(u) veVv'eN(v)
= Y^ ^deg(u)deg(v)d(u,v) = 2Gut(G). «ev vev
By plugging this into (+), we get
\ E s(e.,f) = 4-2-Gut(G) = -4Gut(G),
(e,f )eE2
as required.	□
Lemma 2.3 below will be needed in the proof of the main theorem. Since it might be be of independent graph-theoretical interest, we state it separately. But first we define the following notions.
Definition 2.2. Let G be a graph with vertex set V and edge set E. For a pair of distinct edges e = u\u2, f = v^2 of G we say that they form a triangle whenever |{ui,u2}n{vi,v2 }| = 1 and the graph induced on the set {u1 , u2, v1 , v2 } of the endvertices is K3. Similarly, we say that e and f form a K4 provided that the graph induced on {u1,u2, v1, v2} is the complete graph K4. Finally, we will say that edges u1u2 and v1v2 are on a straight line provided that the difference between the maximum and minimum value of d(ui,vj), i,j € {1,2}, is 2.
Lemma 2.3. Let G be a connected graph such that every pair of distinct edges of G either lies on a straight line or forms a triangle or a K4. Then G is a tree or a complete
CSI
I
CSI 00 CSI CSI
CD
graph.
Proof. Suppose that G is not a tree. We will first show that for every cycle C in G the subgraph G[V(C)], induced by the vertices of C, is a complete graph. Suppose that this is not the case and let C = vov1... vm-1v0 be a shortest cycle in G for which G[V(C)] is not a complete graph. Clearly m > 4. Let k be the integer part, of t?. If C is isomet.rically embedded into G (that is, if dG(vi,vj-) = dC(vi,vj-) for all i, j € {0,1,... ,m — 1}), then the pair of "opposite" edges v0v1 and vkvk+1 does not lie on a straight line and thus forms a K4. But this contradicts the assumption that C is isometrically embedded into G. Therefore there exists a path P = u0u1... ,ut in G between some vertices u0 = va and ut = v^ on C of length t < dC(va,v@). We may assume without loss of generality that no interior vertex of P intersects C, for otherwise we can substitute P with the part of P between two consecutive intersections of P with C. The path P, together with the two parts of C between va and v^, then forms two cycles, say C1 and C2, which are shorter than C. It follows from the minimality of C that both G[V(C1)] and G[V(C2)] are complete graphs. In particular, any two vertices of C which both lie in C1 or both CO in C2 are adjacent. Now take two vertices x,y € V(C) such that x € V(C1) \ V(P) and y € V(C2) \ V(P). Since both x and y are adjacent to va and v^ and since also va ~ v^,
the edges xva and yv^ do not lie on a straight line. But then they form a K4, implying that also x is adjacent to y. This finally shows that any two vertices of C are adjacent in G, which contradicts our assumptions on C. We have thus proves that any cycle in G induces a complete graph.
Now let C be the longest cycle in G. If C contains all the vertices of G, then G = G[V(C)] is a complete graph, as required. We may thus assume that there exists a vertex v € V(G) \ V(C) which is adjacent to a vertex u € V(C). By considering any edge e
of C not incident with u we see that e and uv do not lie on a straight line, implying that they form a K4. But then we can find a cycle with vertex set V(C) U {u} of length larger than that of C. This contradiction finally shows that G is a complete graph. □
i—l
The following lemma describes the relationship between the distance d(e, f) and the average distance of endpoints s(e, f) in more detail.
Lemma 2.4. Let u\u2, viv2 be a pair of edges of a connected graph G. Then
ctf
(2)	d(uiu2, V1V2) > s(uiu2, viV2) + D(uiu2,viv2),
where
(	if u\u2 = v\v2
,„,.	n, , , \ _ J ii if tbe pair u\u2,v\v2 forms a triangle
( )	( , ) ' 1; if the pair uiu2, viv2forms a K4
0; otherwise
Moreover, the equality holds in (2) if and only if the pair uiu2, viv2 forms a triangle or K4, or if uiu2 and viv2 lie on a straight line. In particular, the equality in (2) holds for every pair of distinct edges of G if and only if G is a tree or a complete graph.
CO
max{d(u ,vj) : i,j € {1, 2}} = d(u3- ,v3-t).
CSI
If uiu2 and viv2 form a triangle, then d(us,vt) = 0 while d(us, v3-t) = d(u3-s,vt) = d(u3-s, v3-t) = 1. Therefore
s(uiu2,viv2) = ^(d(us,Ut)+d(us,V3-t)+d(U3-s,Vt)+d(U3-s,V3-t)) = ^ = l-D(uiu2,viv2).
On the other hand d(uiu2,viv2) = 1, and thus (3) holds with the equality, as claimed.
If uiu2 and viv2 form a K4, then d(us, vt) = d(us, v3-t) = d(u3-s, vt) = d(u3-s, v3-t) = 1, and so s(uiu2,viv2) = 1 = 2 — D(uiu2, viv2). On the other hand d(uiu2,viv2) = 2, and again the equality in (3) holds.
Finally, suppose that uiu2 and viv2 do not form a triangle or a K4. Then
(4)	d(u3-s,v3-t) — d(us,vt) < 2,
(5)	d(us,v3-t) — d(us ,vt) < 1,
(6)	d(u3-s ,vt) — d(us ,vt) < 1.
J-l
By summing up these inequalities (together with the equality d(vs,vt) — d(vs,vt) = 0) and dividing by 4 one obtains
CO
Proof If U1U2 = v\v2, then d{u\u2,v\v2) = 0 and s(uiu2, v\v2) = Hence d(uiu2, v\v2) = s(uiu2, viv2) + D(uiu2, viv2) in this case. We may thus assume that uiu2 = viv2.
Suppose that the minimum value of d(u^ ,vj) is attained for i = s and j = t and consequently the maximum at i = 3 — s and j = 3 — t; that is
min{d(ui,vj) : i, j € {1, 2}} = d(us,vt),
vj)
s(uivi,u2v2) — d(us,vt) < 1. Using formula (1) we may thus conclude that
d(uivi,u2v2) = d(us,vt) + 1 > s(uiu2,viv2).
Since D(u\u2, viv2) = 0 in this case, this proves that the inequality in (3) holds. Observe also that, in this case, the equality holds in (3) if and only if we have equality in (4), which happens if and only if u1u2 and v1v2 lie on a straight line.
We have thus proved that (3) holds in all cases, and that we have equality in (3) if and only if u1u2 and v1v2 lie on a straight line or form a triangle or a K4. The second part of the claim now follows directly from Lemma 2.3.	□
Recall that Km(G) denotes the number of all m-cliques in G. Similarly, for an edge uv of G, we let Km(uv) denote the number of m-cliques of G that contain uv. Note that
lO
o
(7)	E Km(uv) = ( j Km(G).
uv€E(G)	^ '
In particular, for m = 2 we obtain k2(G) = |E(G)|. We are now ready to prove the main result of the paper.
Theorem 2.5. Let G be a connected graph. Then
1	1	3
(8)	We(G) > -Gut(G) --\E{G)\ + -nz{G) + 3«4(G)
with the equality in (8) if and only if G is a tree or a complete graph.
Proof. Let V and E denote the vertex set and the edge set of G respectively, and let A be the arc set of G, that is, the set of all ordered pairs of adjacent vertices in G. Then it follows directly from the definition of the edge-Wiener index that
(9)	We(G) = i Y d(uiu2,viv2) = ^ E E d(uiu2,viv2).
(e,/)eE2	(ui,U2)€A (vi,v2)eA
By Lemma 2.4, for a fixed (u1,u2) € A, we have that d(u1u2,v1v2) > s(u1u2,v1v2) + D(u1u2,v1 v2). Hence, by (9), we see that
1 1
(10)	We(G)>-J] E ^.Wl + g E E d(uIu2,viv2),
CO
(ui,U2) (vi,v2 )	(ui ,U2) (vi,v2)
HH
Let us now compute the two sums in (10). Observe first that in view of Lemma 2.1, for the first sum we have that
i E E s(uiu2,viv2) = ^ E s(e,f) = ^Gut(G).
(ui,U2) (vi,v2)	(e,/)eE2
To determine the second sum in (10), note that D(u1u2,v1v2) equals 0 unless one of the following holds: (i) v1v2 = u1u2 (note that there are precisely 2 arcs (v1,v2) for
CO
which this holds); (ii) v1v2 shares an endpoint with u1u2 and forms a triagle with it (note that there are precisely 4k3(u1u2) such arcs (v1,v2)); (iii) v1v2 forms a K4 with
u1u2 (note that there are precisely 2k4(u1u2) such arcs (v1,v2). Hence
1 1
E E D(ulu'2,VlV2) = ~~ E 2 + | E 4K3(ttltt2) + E 2K'i(UiU2).
(ui,u2) (vi ,v2)	(ui ,u2)	(ui ,u2)	(ui,u2)
In view of (7), we see that the above sum equal:
a
—2|E(G)| + 6ks(G) + 24K4 (u1u2).
A
o u ti
io
0 o
1
CO
£ co co
Therefore, by (10), it follows that
We(G) > i(2Gut(G) -2\E(G)\ + 6k3(G) + 2Ak4(uiu2)), 8
as required. Moreover, in view of Lemma 2.4, the equality holds if and only if G is a tree or a complete graph.	□
Corollary 2.6. Let G be a connected graph of minimal degree 5 > 2. Then
52	i	52 — 1
W(L(G)) > —W(G) --\E{G)\ > - W(G).
Proof. Note that Gut(G) =
E
{u,v}CV (G)
deg(u)deg(v)d(u, v) >	52d(u,v) = 52W(G).
{u,v}CV (G)
Now, since 5 > 2, the graph G is not a tree, and so Theorem 2.5 implies the first inequality in the corollary. The second inequality then follows, if one observes that, since every pair of adjacent vertices contributes exactly 1 to the Winner index of the graph (while the non-adjacent ones contribut even more), we have that |E(G)| < W(G).	□
References
1. P. Dankelmann, I. Gutman, S. Mukwembi, H.C. Swart, The edge-Wiener index of a graph, Discrete Mathematics 309 (2009), 3452-3457. . A.A. Dobrynin, Distance of iterated line graphs, Graph Theory Notes of New York 37 (1999), 50-54. . A.A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: Theory and applications, Acta
Appl. Math. 66 (2001), 211-249. . A.A. Dobrynin, L.S. Mel'nikov, Some results on the Wiener index of iterated line graphs, Electronic
Notes in Discrete Mathematics 22 (2005), 469-475. . A.A. Dobrynin, L.S. Mel'nikov, Wiener index for graphs and their line graphs with arbitrary large
cyclomatic numbers, Applied Mathematics Letter 18 (2005), 307-312. . R. C. Entringer, D. E. Jackson, D. A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976), 283-296.
. I. Gutman, I. G. Zenkevich, Wiener index and vibrational energy, Z. Naturforsch. 57 A (2002), 824-828.
. M.H. Khalifeh, H. Yousefi-Azari, A.R. Ashrafi, S.G. Wagner, Some new results on distance-based
graph invariant, European Journal of Combinatorics 30 (2009), 1149-1163. . J. Plesnlk, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984), 1-21. . H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), 17-20.
7
9 10
m
CD
$H
CD
m
u
a
CD U
(Martin Knor) Slovak University of Technology, Faculty of Civil Engineering, Department of Mathematics, RadlinskEho 11, 813 68, Bratislava, Slovakia E-mail address, Martin Knor: knorSmath. sk
(PrimoZ Potocnik and Riste Skrekovski) Faculty of Mathematics and Physics, University of Ljubljana, and, Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
E-mail address, PrimoZ Potocnik: primoz.potocnik@fmf.uni-lj.si
E-mail address, Riste Skrekovski: skreko@fmf.uni-lj.si