IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 48 (2010), 1128
ISSN 2232-2094
WIENER INDEX IN ITERATED LINE GRAPHS
M. Knor P. Potocnik R. Skrekovski
Ljubljana, August 31, 2010
00
CO CO
Wiener index in iterated line graphs
M. Knor* P. PotocnikJ R. Skrekovski*
July 23, 2010
00
Abstract
For a graph G, denote by Li(G) its i-iterated line graph and denote by W(G) its Wiener index. We prove that the function W(L%(G)) is convex in variable i. Moreover, this function is strictly convex if G is different from a path, a claw K1,3 and a cycle. As an application we prove that W(L%(T)) = W(T) for every i > 3 if T is a tree in which no leaf is adjacent to a vertex of degree 2, T = Ki and T = K2.
1 Introduction
i
Let G = (V(G), E(G)) be a graph. For any two of its vertices, say u and v, we let d(u,v) denote the distance from u to v in G. The Wiener index of G, W(G), is defined as
W(G) = J2 d(u, v),
u=v
where the sum is taken through all unordered pairs of vertices of G, see [8]. Wiener index has many applications in chemistry, see e.g. [5], therefore it is widely studied by chemists. It attracted the attention of mathematicians in 1970's and it was introduced under the name of transmission or the distance of a graph, see [4] and
[7].
The line graph of G, L(G), has vertex set identical with the set of edges of G, i.e. V(L(G)) = E(G). Two vertices of L(G) are adjacent if and only if the corresponding
* Slovak University of Technology, Faculty of Civil Engineering, Department of Mathematics, CD Radlinskeho 11, 813 68, Bratislava, Slovakia, knor@math.sk.
^Faculty of Mathematics and Physics, University of Ljubljana, and Institute of Mathematics, Physics and Mechanics, Jadranska 21, 1111 Ljubljana, Slovenia, CO primoz.potocnik@fmf.uni-lj.si.
^Faculty of Mathematics and Physics, University of Ljubljana, and Institute of Mathematics, Physics and Mechanics, Jadranska 21, 1111 Ljubljana, Slovenia, skrekovski@gmail.com.
• I
K	1
00 CSI
r
i
CSI 00
£ CO CO
CO CD
$H
CD CO
edges are adjacent in G. Iterated line graphs are defined inductively as follows:
G	if i = 0
o
Li (G) =
L(Li-1(G)) if i> 0.
A connected graph is trivial if it contains no edges, i.e., if it has at most one vertex. As shown in [1], for any nontrivial tree T on n vertices we have W(L(T)) = W(T) — (n). Hence, there is no nontrivial tree for which W(L(T)) = W(T). However, there are trees T satisfying W(L2(T)) = W(T), see e.g. [2]. In [3], the following problem was posed:
<
Problem 1.1 Is there any tree T satisfying equality W(Ll(T)) = W(T) for some i > 3?
If G is a trivial graph, then clearly W(Ll(G)) = W(G) = 0 for all i > 0. Therefore it is reasonable to consider only nontrivial graphs. However, there are also other graphs, which behave "trivially". If G is a cycle, then L(G) = G and consequently W(Ll(G)) = W(G) for every i > 0. For a claw K13 the graph L(K13) is a triangle, so that L(K1>3) = Li(K1,3) and consequently W(L(K1>3)) = W(Li(K1,3)) for every i > 1. Finally, for a path on n vertices, Pn, we have L(Pn) = Pn-1 if n > 1, while L(P1) is the empty graph. Hence, W(Li(Pn)) = 0 if i > n. These three classes of graphs are exceptional. If G is distinct from a path, a cycle and the claw K1>3, then limi^^ |V(Li(G))| = to, see [6]. Therefore graphs, different from a path, a cycle and the claw K13, are called prolific.
Define a function fG(i) = W(Li(G)). What is the behaviour of fG? If G is a connected non-prolific graph then fG is a constant function for i > iG, where iG is a constant depending on G. But, we do not know, for instance, if it can happen for some i that fG(i) > fG(0) and fG(i + 1) < fG(0). Therefore it is important to study the general behaviour of fG. We prove here the following basic statement:
Theorem 1.2 Let G be a connected graph. Then fG(i) is a convex function. Moreover, fG(i) is strictly convex if G is a prolific graph.
We remark that h(i) is convex function if h(i) + h(i + 2) > 2h(i + 1) for every i > 0, and h(i) is strictly convex if h(i) + h(i + 2) > 2h(i + 1).
By the analysis above, the first part of Theorem 1.2 is a straightforward consequence of the second. Theorem 1.2 has following consequences for Problem 1.1.
Corollary 1.3 Let T be a tree such that W(Lk(T)) > W(T) for some k. Then W(Li(T)) > W(T) for every i > k.
Computer experiments showed us that there is a big proportion of trees for which already W(L3(T)) > W(T). Although we have no formula for counting W(L3(G)) using distances in G, we can use the following corollary of Theorem 1.2.
a
CO
Corollary 1.4 Let T be a nontrivial tree such that 2W(L2(T)) > W(T)+ W(L(T)). O Then W(L3(T)) > W(T).
C^	+
By a 2+-tree we call a tree which is different from K1 and K2, and in which no leaf is adjacent to a vertex of degree 2. Using Corollary 1.4 we prove the following CO statement:
Theorem 1.5 Let T be a 2+-tree different from K^. Then W(L3(T)) > W(T).
Hence, if T is a 2+-tree different from K1>3, then W(L%(T)) > W(T) for every
1	> 3, by Corollary 1.3. As W(K1>3) = 9 and W(Lj(K1>3)) = 3 for every j > 1, we infer that W(Ll(T)) = W(T) for every 2+-tree T and every i > 3. We remark that extension of Theorem 1.5 to other trees is considered in a forthcoming paper.
The outline of this paper is as follows. In the next section we give formulae for W(G) and W(L2(G)) involving the degrees and distances in G. In the third section we prove:
Theorem 1.6 Let G be a connected graph distinct from an isolated vertex and a O cycle. Then W(L2(G)) - 2W(L(G)) + W(G) > 0.
which implies Theorem 1.2. Finally, in the last section we prove Theorem 1.5.
2	Preliminaries
and L2(G) and afterwards counting the distances in L(G) and L2(G). Instead, we 2compute distances included in W(L(G)) and W(L2(G)) already in G. For this, we C^ use the representation of vertices of L(G) and L2(G) in G.
By the definition of the line graph, every vertex w £ V(L(G)) corresponds to an edge of G. Let us denote by B1(w) this edge of G. Analogously, every vertex x £ V(L2(G)) corresponds to a path of length two in G, denote this path by B2(x). In fact, vertices of L(G) are in one-to-one correspondence with edges of G, and vertices of L2(G) are in one-to-one correspondence with paths of length two in G.
Let S1 and S2 be two edge-disjoint subgraphs of G. We define the distance d(S1, S2) to be the length of a shortest path in G joining a vertex of S1 to a vertex of S2. Further, if S1 and S2 share s > 1 edges, then we set d(S1,S2) = —s. With thus defined function d, the following holds for any w,z £ V(L(G)) and any x,y £ W V (L2(G)):
dL(G)(w,z) = d(B1(w),B1(z)) + 1,	(1)
dL2(G) (x,y) = d(B2(x),B2(y)) + 2.	(2)
CO
We remark that although there is no one-to-one correspondence between the vertices of Ll(G), i > 3, and subgraphs of G, there are tools for counting distances between vertices of L%(G) already in G, see [6].
a
CD	3
3
£ CO
In our proofs, we do not find W(L(G)) and W(L2(G)) by first constructing L(G)
Lemma 2.1 Let u,v G V(G) and let w,z G V(L(G)) such that u G V(B1(w)) and v G V(B1(z)). Then for some i G { — 1, 0,1} the following holds:
C^
dL(G)(w, z) = d(B1(w), B1(z)) + 1 = d(u, v) + i.
PROOF. The first equality follows from (1). Since B1(w) contains u and one neighbour of u, while B1(z) contains v and one neighbour of v, we have
m
d(u, v) - 2 < d(B1(w),B1(z)) < d(u,v).
Therefore, d(Bi(w), Bi(z)) + 1 = d(u, v) + i, where —1 < i <1.	□
<
00 CSI
Let u and v be two distinct vertices of G. For i G { — 1,0,1}, let ai(u,v) denote the number of pairs w,z for which u G V(B1(w)), v G V(B1(z)) and d(B1(w),B1(z)) = d(u,v) - 1 + i.
In the sequel, denote by du and dv the degrees of u and v, respectively.
o
£ Proposition 2.2 Let G be a connected graph. Then

1d
1
u=v "	" " ueV(G)
where the first sum runs through all unordered pairs u, v G V(G).
u
W(L(G)) = - E |'du dv d(u, v) - Q'_i(u, i>) + q-i(u, u) + - E ^ ^
O	V
c^
PROOF. By definition we have
W(L(G))=	dl(g)(uu , vv'),
{uu',vv'}
CO
where the sum runs through all pairs of edges uu',vv' of G. By considering the ordered choices for the vertices u,v,u',v', one gets
W(L(G)) = - E E E E dL{G)(i^,vv').
uev(G) vev(G) u'eN(u) v'eN(v)
Let us first consider the contribution of ordered pairs u, v G V(G) with u = v. Then in view of Lemma 2.1, we see that dL(G) (uu', vv') = d(u, v)+i for some i G { — 1, 0,1}. By summing over all ordered pairs (u,v), u = v, one thus gets the contribution of dudvd(u,v) minus the number of choices for u' G N(u) and v' G N(v) such that dL(G) (uu',vv') = d(u,v) — 1 plus the number of choices for u' and v' such that ^ dL(G) (uu',vv') = d(u,v) + 1. This contribution is thus
1	r
- ^^ ^^ du dv d(u, u) — Q'_i(u, u) + Q'i(u, u)
uev(G) vev(G)\{u}
a
V	4
00 4J
CO
M <
00
0 o
1
00 ^
CO CO
which clearly equals the first sum in the statement of the proposition.
On the other hand, if u = v, then dL(G)(uu', vv') = 1 if u' = v' (and 0 otherwise). The contribution of such a pair {u, v} to W(L(G)) thus equals to
E E
u'eN(u) v'eN(u)
1
1 = ~du(du - f)
f
4
g"1^"" 4 E
uev (G)
The result now follows by adding up the two contributions.
du
□
In a tree, every pair of vertices is joined by a unique path, so that a_1(u, v) = 1 and a1(u,v) = (du — 1)(dv — 1). Hence, we obtain the following consequence of Proposition 2.2.
Corollary 2.3 Let T be a tree. Then
1
W(L(T)) = -J2
u=v
du dv d(u,v) — 1 + (du — 1)(dv — 1)
nE
du 2
where the first sum runs through all unordered pairs u,v G V(G) and the second one runs through all u G V(G).
Now we turn our attention to L2 (G).
Lemma 2.4 Let u,v G V(G) and let x,y G V(L2(G)) such that u is the center of the path B2(x) and v is the center of B2(y). Then for some i G {0,1, 2}, the following holds:
dL2(G)(x,y) = d(B2(x),B2(y)) + 2 = d(u,v) + i.
PROOF. The first equality is simply a restatement of formula (2). Since B2(x) contains u and two neighbours of u, while B2(y) contains v and two neighbours of v, analogously as in the proof of Lemma 2.1 we have d(u, v) — 2 < d(B1(w), B1(z)) < d(u, v). Therefore, d(B-2(x), £>2(2/)) + 2 = d(u, v) + i, where 0 < i < 2.	□
CO CD
$H
CD CO
u
a
CD U
Let u and v be two distinct vertices of G. For i G {0,1, 2}, denote by ftj(u,v) the number of pairs x, y G V(L2(G)), for which u is the center of B2 (x), the vertex v is the center of B2(y), and d(B2(x), B2(y)) = d(u, v) — 2 + i.
Proposition 2.5 Let G be a connected graph. Then
du dv | d(u,v) + P1(u,v) + 2ft2(u,v)
W(L2(G))
E
u=v
2
du
4
+ E M"; +6
uev(G) L V /
where the first sum runs through all unordered pairs u,v G V(G).
2
PROOF. For a pair {u,v} of vertices of G, let C(u,v) be the set of all pairs {x, y} of distinct vertices of L2(G) with the centre of one of {B2(x), B2(y)} being u (N and the centre of the other being v. Then
00 m
2
00
o
W(L2(G)) = J] dL2(G)(x,y) = £ J] dL2(G)(x,y),
x=y	{u,v} {x,y}€C(u,v)
where {u, v} runs through the set of all unordered pairs of vertices of G. Let us now determine the contribution of a fixed such pair {u, v} to the above sum.
If u = v, then by Lemma 2.4, for every i G {0,1, 2} we have precisely (u, v) pairs x,y such that dL2(G) (x,y) = d(u,v) + i. Moreover-, note that |C(u,v)| = (d2) (d2). Therefore, the contribution of the pair {u, v} is
If u = v, then for a pair {x,y} G C(u,v) we see that dL2(G) (x,y) equals 0 (when B2(x) = B2(y)) or 1 (when B2(x) and B2(y) share exactly one edge) or 2 (when B2(x) and B2(y) are edge-disjoint). The number of pairs {x,y} G C(u,v) for which B2(x) and B2(y) share exactly one edge is 3 (dg) and the number of pairs {x,y} G C(u, v) for which B2(x) and B2(y) are edge-disjoint is 3 (d4u). Hence, all these pairs contribute + to W{L2(G)).	n
o
I
00 ^
CO CO
As already mentioned above, in a tree every pair of vertices is joined by a unique path. Therefore $o(u, v) = (du — 1)(dv — 1), A(u, v) = (du — 1) (dv2-1) + (du2-1) (dr — 1) and (u, v) = (du2-1) (dv2-1). Observe that $0(u, v) + $1(u, v) + $2(u, v) = (d2u) (d2v Hence, we have the following consequence of Proposition 2.5.
Corollary 2.6 Let T be a tree. Then
W (L2(T))
E
u=v
2*) (t)d(u.v) + (du — 1)('ir2 1
+ ,'du — >4 — !) + <du — M (dr — 1
+
uev (T)
^ t)d4u
where the first sum runs through all unordered pairs u, v G V(G).
3 Convexity of Wiener index
CD
c0 Define
U
a
CD U
A(G)
E
u=v
du
d \ d d
^v I	^u^v , 1 I 7/	\
2 J--2~ +
2
CO
4J
CO
M <
00
0 o
1
CO ^
CO CO
B(G) C (G)
E
u=v
E
A(u,v) + 2^2 (u, v) +
a-1(u,v) a1(u,v)

2
2
3, ^
3
4

1/i 2 V 2
where the first two sums run through all unordered pairs u, v £ V(G) and the third one runs through all u £ V(G). By Propositions 2.2 and 2.5 we have
Proposition 3.1 Let G be a connected graph. Then
W (L2 (G)) — 2W (L(G)) + W (G) = A(G) + B(G) + C (G).
We will now prove the inequality A(G) + B(G) + C(G) > 0 in two steps. First we prove the following:
Lemma 3.2 Let G be a connected graph other than an isolated vertex or a cycle. Then A(G) + C(G) > 0.
PROOF. Denote by aG(u,v) the summand of A(G) corresponding to u and v. Since
du\ I dv\ du dv
22

+1
)(d2 — dv) — 2du dv + 4
we have
A(G) = J] ac(u,v) = J2
u=v	u=v
4
du dv(du dv - du - dv - 1) + 4 4
du dv (du dv du dv 1) + 4 7/ \ U,V) = > -;-d{U,V).
4
(3)
Further, denote by cG(u) the summand of C(G) corresponding to u. Then
C(G)
CO CD
$H
CD CO
$H
a
CD U
]Ccc(u) = ]C
u E
31du
3
4

l(du 2 I 2
du(d„-l)(2d„-4)	- + 6)
4
4
4
E
du (du — 1)(dU — 3du + 1)
(4)
Let us first focus on C(G). Since x2 — 3x+1 is a quadratic function with minimum
at x = and since its values at x = 2 and x = 3 are —1 and 1, respectively, we
2
4
00 4J
CO
M <
00
0 o
1
00 ^
CO CO
have cG(u) = 0 for du = 1; cG(u) = —| for du = 2 and cG(u) > 0 for du > 3. Hence, C(G) > — n2/2, where n2 is the number of vertices of degree 2 in G.
Suppose now that the statement of the lemma is wrong, and let G be a minimal (with respect to | V(G)|) counterexample. We will now split the proof into two cases, depending on whether G has a vertex of degree 1 or not.
Let us first consider the case where G is a graph with minimum degree $(G) > 2, not isomorphic to a cycle. Let {u,v} be an unordered pair of vertices of G and assume that u is the one with smaller degree, that is, du < dv. If du > 3, then
/ x ^ du dv (du dv — du — dv — 1) + 4 3dv (3dv — dv — dv — 1) + 4
ClG\U, V) > -;- > -;- > 1.
4
On the other hand, if du = 2, then
4
aG(u,v) >
du dv (du dv — du — dv — 1) + 4 2dv (2dv — 2 — dv — 1) + 4
4
4
d2 — 3dv + 2	(dv — 1)(dv — 2)
> 0.
m
CD CD
m
u
a
CD U
Denote by n the number of vertices of G and let v be a vertex of maximum degree in G. If dv > 4, then by the above we have that aG(u,v) > 1 for every u G V(G), u = v, and therefore A(G) > n — 1 > n2. If dv = 3, then aG(u,v) > 1 for every u G V(G), u = v. In this case there is at least one more vertex of degree 3 in G, so we have A(G) > n — 1 > n2. Therefore in both cases we see that A(G) > n2, and thus A(G) + C(G) > n2 - f > 0, as claimed.
Suppose now that G has a vertex of degree 1. Then remove from G this vertex and the incident edge, and denote the resulting graph by G'. Then one of the following occurs:
(i)	G' = K1 is an isolated vertex;
(ii)	G' = Cn is a cycle;
(iii)	G' is neither an isolated vertex nor a cycle.
If (i) occurs, then G ^ I<2, and so A(G) = \ by (3) and C(G) = 0 by (4). Hence, A(G) + C(G) > 0 in this case, as claimed.
If (ii) occurs, then G is isomorphic to a cycle Cn with a pending edge attached to it. Let x and y be the vertices in G of degree 3 and 1, respectively (note that du = 2 for any u G {x, y}). Then we have
aG(u,v)
0

if {u, v} Pi {x, y} = 0,
if {u, v} = {rr, y}, 0	if {u, v} = {y, z} for z = x,
d(u, v) if {u, v} = {z, x} for z = y.
2
2
Since G has n — 1 vertices of degree 2, one vertex of degree 1 and one vertex of degree 3, the last two vertices being adjacent, we infer A(G) > —| + n — 1. As C(G) > -f = and n > 3, we conclude A(G) + C(G) > ^ > 0. Hence the ~ statement of the lemma holds in this case.
If (iii) occurs, then by minimality of G' we know that A(G') + C(G') > 0. To conclude the proof of lemma it remains to show that introducing a pendant edge to G' cannot decrease the value of A(G') + C(G').
Let u be a vertex of degree du in G' and let G be obtained from G' by adding a single edge ua, where a is a new vertex. We show that A(G) — A(G') >
Observe that C(G) = C(G') — cG' (u) + cG(u) + cG(a). We have cG(a) = 0. Moreover, cG(u) — cG/(u) > 0 if du > 2, while cG(u) — cG/(u) = — \ if du = f, see
00 +->
w
00 CSI
(4). Thus, C(G) - C(G') > -i, so that if we prove A(G) - A(G') > we obtain A(G) + C(G) > A(G') + C(G'), as desired.
To avoid fractions, we investigate the difference 4A(G) — 4A(G') and we prove that 4A(G) — 4A(G') > 2. In 4A(G) — 4A(G') the terms which do not contain neither u nor a cancel out. Hence, we need to consider only the terms corresponding to u in both A(G') and A(G) and we have to add the terms corresponding to a, together with the term corresponding to the pair (a,u), see (3). We obtain:
r
4A(G) — 4A(G') = ^ [((du+1)dv ((du+1)dv — du — dv — 2) + 4) d(u,v)
v&V (G' )\{u}
— ^du dv (du dv — du — dv — 1) + d(u, v)
+ f1dv(1dv — dv — 2)+ 4) fd(u,v) + 1)
V	J\	Ji
+ ^1(du+1)(1(du+1) — du — 3) + 4j 1
Y 2(du dv — 2)(dv — 1)d(u,v) — 2dv + 4 — 2du + 2.
veV (G' )\{u}
CO CO
Let g(u, v) = (du dv — 2)(dv — 1)d(u, v) — dv + 2. Then
4A(G) — 4A(G') = 2( J] g (u,v) — du + ^.
veV (G')\{u}
Now, if always g(u,v) > 1, then 4A(G) — 4A(G') > 2(Ev 1 — du + 1) > 2. If dv = 1, then g(u,v) = 1. On the other hand, if dv > 2, then g(u,v) = (du dv — 2)(dv — 1)d(u, v) — dv + 2 > (dv — 2) — dv + 2 = 0, with equality holding only if du = 1 (and also dv = 2 and d(u,v) = 1). Hence, if du > 1 then g(u,v) > 1 for every v and 4A(G) — 4A(G') > 2. Suppose therefore that du =1. Then 4A(G) — 4A(G') = 2 J2v g(u,v). We already know that g(u,v) > 0 for every v and that g(u,v) = 0 only if dv = 2 (and d(u,v) = 1). Hence, 2 g(u,v) = 0 only if all the vertices v £ V (G'), v = u, have degrees 2. Since du = 1, we cannot have dv = 2 for every
a
K	9
v G V(G')\{u}, so that 4A(G) — 4A(G') = 2^]v g(u,v) > 0. Since g(u,v) is integer, O we have 4A(G) — 4A(G') > 2 also in this case.
Thus, in any case A(G) - A(G') > ± so that A(G) + C(G) > A(G') + C(G'),
and the lemma is proved.
□
Lemma 3.3 Let G be a connected graph distinct from an isolated vertex and a cycle. $ Then B(G) > 0.
M
PROOF. Consider distinct vertices u,v G V(G). Partition the neighbours of u ^ into three sets S1, S2 and S3:
51	= {a; d(a, v) = d(u,v) — 1};
52	= {a; d(a,v) = d(u,v)};
53	= {a; d(a,v) = d(u,v) + 1}.
Analogously partition the neighbours of v into three sets T1, T2 and T3:
£
T1 = {b; d(b, u) = d(u,v) — 1}; T2 = {b; d(b, u) = d(u,v)};
T3 = {b; d(b,u) = d(u,v) + 1}.
Denote by b(u, v) the summand of B(G) corresponding to u and v. Further, denote by b2(u,v) the part of b(u,v) corresponding to W(L2(G)) (i.e., b2(u,v) = $1(u,v) + 2$2(u,v)) and denote by b1(u,v) the part of b(u,v) corresponding to 2W(L(G)) (i.e., b1(u,v) = (—a-1 (u,v) + a1(u,v))/2). Then b(u,v) = b2(u,v) — b1 (u, v). We find a lower bound for b2(u, v) and an upper bound for b1(u, v), and we show that b2(u,v) — b1(u,v) > 0, which establish the lemma.
Consider the vertices x and y of L2 (G) such that u is the center of B2 (x) and v CO is the center of B2(y). Moreover, denote by u1 and u2 the other vertices of B2(x) and denote by v1 and v2 the other vertices of B2(v). Then B2(x) = (u1,u,u2) and B2(y) = (v1,v,v2). There are several possibilities.
•	{u!,u2}n S1 = 0 and {v1,v2 }n T1 = 0: Then dL2(G)(x,y) = d(B2(x), B2(y)) + 2 > d(u, v) + 0. Hence, the pair x,y adds at least 0 to b2(u, v) in this case.
•	{u1,u2}nS1 = 0 and {v1 ,v2}nT1 = 0: Then dL2(G)(x,y) > d(u,v) + 1. Hence, the pair x,y adds at least 1 to b2(u,v) in this case.
• 1
•	{u1,u2} n S1 = 0, {u1,u2} n S2 = 0 and {v1,v2} n (T1 U T2) = 0: Then dL2(G) (x, y) > d(u, v) + 1.
•	{u1,u2} n S1 = 0, {u1,u2} n S2 = 0 and {vbv2} n (T1 U T2) = 0: Then dL2(G) (x, y) > d(u, v) + 2.
a
IS	10
00 4J
CO
M <
00
0 o
1
00 ^
CO CO
•	{u1,u2} H (S1 U S2) = 0 and {v1, v2} H T1 = 0: Then dL2(G) (x, y) > d(u, v) + 1.
•	{u1,u2} H (S1 U S2) = 0 and {v1, v2} H T1 = 0: Then dL2(G) (x, y) > d(u, v) + 2.
For i = 1, 2, 3, denote by sj and tj the size of Sj and Tj, respectively. Then the above bounds force that
&2 (u,v) > 0 +
+
+2
s1 + s2 + s3 2
s2 + s3
I 2 j — f2 + *)
s2 + s3

% + t3 2

+

2
+ t2 + taN 2

s1 + s2 + s3
+
+
s2 + s3


t1 + t2 + t3\ 2
2
C2 2
t2 + t3 2
t1 + t2 + t A + /V
+2
s3
t2 + t3 2

t1 + t2 + t3 + t2 + t3 2 / V 2
(5)
CD
$H
CD
m
u
a
CD U
Now consider the vertices w and z of L(G) such that u £ B1(w) and v £ B1(z).
Denote by u1 the other vertex of B1(w) and denote by v1 the other vertex of B1(z).
Then B1(w) = (u,u1) and B1(z) = (v,v1). There are two possibilities.
•	u1 £ S1: Then there is at least one v1 £ T1 such that d(B1(w), B1(z)) = d(u, v) — 2. In this case dL(G)(w,z) = d(B1(w), B1(z)) + 1 = d(u,v) — 1. For other v1 £ N(v) we have dL(G)(w,z) < d(u,v).
•	u1 £ S2 U S3: Then for every v1 £ T1 we have dL(G)(w,z) < d(u,v). For v1 £ T2 U T3 we have dL(G)(w, z) < d(u, v) + 1.
This means that (recall that b1 (u,v) = (—a-1(u,v) + a1(u,v))/2)
bi(u,v) < -— +---.
Analogously one can derive
If	N ^ il , (g2 + g3)(t2+t3)
so that
b1 (u, v) <
(s2 + S3 )(t2 + t3) S1 t1

2
2
2
In the following we prove that b(u, v) = b2(u, v) — b1(u, v) > 0. Observe that the unique negative term in b2(u, v) — b1(u, v) is (s2 + s3)(t2 +t3)/2. If we show that one of the three terms of (5) is not smaller than (s2 + s3)(t2 +t3)/2, then we are done. Observe that s1 > 1. This means that
fs 1 + S2 + sA fs 2 + S3\ fs 2 + S3 + 1\ A2 + S3\
i 2 )—{ 2 jn 2 H 2 )=s2+
If t2 + t3 > 2 then (t2+t3) >	This means that if t2 + t3 > 2 then for the first
term of (5) we have
<
00 c^
o
£
s1 + s2 + s3	s2 + s3
2 — 2
t2+t3\ > {s2 + S3){t2+t3)
22
so that b(u,v) = b2(u,v) — b1(u,v) > 0 in this case.
Obviously, if t2 + t3 = 0, then (s2 + s3)(t2 + t3)/2 = 0 and we have b(u,v) b2(u, v) — b1 (u, v) > 0 again.
Thus, consider the remaining case t2 + t3 = 1. In this case (5) reduces to
s2 + s3	s3
2 — 2
t1 2+1 + s23 t1 2+1
b2 (u,v) >
fs2 + sA Zt1 + 1\ fs2 + s3
«	=(2X2 J>l 2
^	, + X	+
as 11 > 1. Now if s2 + s3 > 2 then ( g"3} > ^^ and consequently b2(u,v) > (s2 + s3)(t2 + t3)/2. Thus, suppose that s2 + s3 = 1, as in the case s2 + s3 = 0 we
CSI
have b(u, v) > 0 trivially. Then
s1 , t1 (s2 + s3)(t2 + t311,1 1
-&!(«, 10 > ^ + T - V 2 3A2	>7 + 7- - = 0,
4 4	2	"442
HH
as both s1 and t1 are at least 1. Therefore b(u,v) = b2(u,v) — b1(u,v) > 0 also in this case.
Since we proved b(u,v) > 0 in all cases, we have B(G) > 0 and the lemma is proved.	□
Proof of Theorem 1.6. By Proposition 3.1 we have W(L2(G)) —2W(L(G)) + W(G) = A(G) + B(G) + C(G). By Lemma 3.2 we have A(G) + C(G) > 0 and by ^ Lemma 3.3 we have B(G) > 0 for every graph G distinct from an isolated vertex and a cycle. Hence A(G) + B{G) + C{G) > 0 for such a graph.	□
Jh
a
00 4J
CO
M <
00
0 o
1
00 ^
CO CO
4 Wiener index of 2+-trees
Here we prove Theorem 1.5 using Corollary 1.4. For any tree T, different from an isolated vertex, define
D(T) = 8W (L2(T)) — 4W (L(T)) — 4W (T).
If D(T) > 0 then also \D{T) > 0 and by Corollary 1.4 we obtain W(L3(T)) > W(T).
Proposition 4.1 Let T be a tree different from an isolated vertex. Then
D(T)
J] ( du dv [2(du — 1)(dv — 1) — 1] — 4) d(u, v)
u=v ^	'
+ ^ f (du — 1)(dv — 1) |~4(du — 1)(dv — 1) — 5
u=v
+1
+ ~du(du - 1) \4(du - 1 )(du - 2) - 1
where the first two sums run through all unordered pairs u, v G V(G) and the third one goes through all u G V(G).
PROOF. By Corolaries 2.3 and 2.6 we have
D(T)
8 £
N u=v
+2
d2u) (d2v) d(u,v) + (du — 1)(dv — V (du 2 r)(dv — 1)
du - 1	dv - 1
+
3 d3u + 6 d4u

Ke
22 du dv d(u,v) — 1 + (du — 1)(dv — 1)

u=v
4^ d(u, v)
+
du
u=v
CO CD
$H
CD CO
and by reordering the terms we obtain the statement of the proposition.
We start with stars.
Lemma 4.2 If G = K1;fc is a star with k > 4, then D(G) > 0.
□
U
a
CD U
2
00 4J
CO 2
00
0 o
1
00 ^
CO CO
PROOF. In there are k vertices of degree 1 and one vertex of degree k. Moreover, there are (2) pairs of vertices at distance 2 where both vertices are of degree 1, and there are k pairs of vertices at distance 1 where one of these vertices has degree 1 and the other one has degree k. Substituting these pairs and singletons into Proposition 4.1, we obtain
D(Ki,fc)
(-1 - 4)2 + 1 + k (-k - 4)1 + 1
+ k ■ 0 + ^k(k - 1) 4(fc - f)(A: - 2) - f k2 - k
/	19 7 \
(—9) + (—A:2 — 3k) + (2A:4 - 8A:3 + y A:2 - -kJ
2
(k - 4)k3 + (2k - 1)k
Since k > 4, we have D(K1k) > 0.
□
Lemma 4.2 will serve for the basis of induction, using which we prove Theorem 1.5. However, since the statement of Lemma 4.2 is not true for k = 3, we need to extend the result slightly; denote by H the tree having six vertices, out of which two have degree 3 and the remaining four have degree 1. (Then H is a graph which "looks" like the letter H.)
Lemma 4.3 It holds D(H) = -4 and W(L3(H)) > W(H).
PROOF. Observe that L(H) consists of two triangles sharing a common vertex, while L2(H) consists of a clique K4, two vertices of which are adjacent to one extra vertex of degree 2, while the other two vertices of this clique are adjacent to another extra vertex of degree 2. It is easy to calculate that W(H) = 29, W(L(H)) = 14, W(L2(H)) = 21 and W(L3(H)) = 64, where W(L3(H)) can be evaluated using distances between edges of L2(H). Hence W(L3(H)) > W(H) and D(H) = 8 ■ 21 -
4 ■ 14 - 4 ■ 29 = -4.
□
CO CD
CD CO
u
a
CD U
Observe that every vertex of degree 1 in a 2+-tree is adjacent with a vertex whose degree is at least 3.
Lemma 4.4 Let T be a 2+-tree and let a be a leaf of T. Let T' be the tree obtained from T by attaching k leaves at a, k > 2. Then D(T') > D(T) + 20.
PROOF. Many pairs of vertices have in T the same degrees and distance as in T'. These pairs we do not need to consider, as the corresponding terms will cancel
k
2
2
out. We need to consider only the pairs involving a in both D(T') and D(T), and the pairs involving pendant vertices adjacent to a. Of course, we have to take in mind that the degree of a is 1 in T and k + 1 in T'. Hence, using Proposition 4.1 we obtain (the sums go through u £ V(T) \ {a})
00
D(T') — D(T) = (du(k + 1) 2(du — 1)k — 1 — 4] d(u,a)
u V	/
+ E f (du — 1)k [4(du — 1)k — 5
uu
— Y, (du[—1] — ^ d(u, a) — J] 1
u	u
00
+ ^(du[—1] — A (d(u,a) + 1) + k^] 1
+ k((k + 1)[—1] — 4) ■ 1 + k ■ 1 + Qj (1[—1] — ^ ■ 2
+ (2) ■1 + \(k + l)k[4k(k-l)-l
-0
- A:2 - -->/, + A: - 5A:2 + 5A: + - - - + 2A:4 -2k2----
2 2 2 2
J] (2k2du (du — 1) + 2k du (du — 1)
u
— du k — du — 4 + du + 4 — kdu — 4k^ d(u, a) + S ( 4k2(du — 1)2 — 5k(du — 1) + 1 — 1 — kdu — 4k + k J
u
CO CO
k^ ((2kdu (du — 1) + 2(du — 1)2 — 6 )d(u,a)
+ 4k(du - 1) - 6(du - 1) - 4 + 2k2(k2 — 4).
Let g(u) = [2k du (du — 1) + 2(du — 1)2 — 6]d(u, a) + 4k(du — 1)2 — 6(du — 1) — 4. Then
D(T') — D(T) = k	g(u) + 2k2(k2 — 4).
ueV (T )\{o>
CO
If du > 2, then 2kdu(du — 1) + 2(du — 1)2 — 6 > 4 and (du — 1)(4k(du — 1) — 6) — 4 > — 2, so that g(u) > 4 — 2 > 0. On the other hand, g(u) = — 6d(u, a) — 4 < 0 if du =1. Nevertheless, we show that u g(u) > 10.
a
IS	15
Let S be the set of vertices of degree at least 3 in T. For every u G S denote by S(u) the set consisting of u and all pendant vertices of T adjacent to u. Then S(u) n S(u') = 0 for every u, u' G S, u = u'. Since UueSS(u) contains all vertices of V(T) \ {a}, whose degree is different from 2, and since g(v) > 0 if dv = 2, we have
"	£ g(v) > ££ g(v).
v	ues ves (u)
£
Let u G S. We find a lower bound for YIveS(u) g(v). Suppose that u is adjacent ^ to l leaves in T, where l < du — 1. Then
<	/	x
J] g(v) = (2kdu (du — 1) + 2(du — 1)2 — 6jd(u,a) + 4k(du — 1)2
ves(u)
/	x
—	6(du — 1) — 4 — 6l(d(u,a) + 1J — 4l.
Note that for every vertex v of degree 1 we have g(v) < 0. Since l < du — 1, we obtain
£ g(v) > (2k du (du — 1) + 2(du — 1)2 — 6) d(u,a) + 4k(du — 1)2
ves(u)
—	6(du — 1) — 4 — 6(du — 1) ( d(u, a) + 1) — 4(du — 1)
= ((2k du — 6)(du — 1) + 2(du — 1)2 — 6)d(u, a)
+ (4k(du — 1) — 16) (du — 1) — 4. C^	V	7
Since k > 2, du > 3 and d(u, a) > 1, we have
g(v) > 14d(u, a) — 4 > 10.
ves(u)
Notice that 2k2(k2 — 4) > 0. As T is not a path, we have |S| > 1, so that ^g(v) + 2k2(k2 — 4) > k Y YI g(v) > S 10k > 10k > 20.
v	ues ves(u)	ues
Observe that W(KM) = 9 while W(L^K^)) = 3 for i > 1, so that D(KM) =
8 ■ 3 — 4 ■ 3 — 4 ■ 9 = —24. Therefore D(H) — £(^3) = 20, so that the statement of
^ Lemma 4.4 is sharp. • 1
s	16
00 4J
CO
M <
00
0 o
1
00 ^
CO CO
Lemma 4.5 Let T be a 2 +-tree, and let a be a vertex of degree k +1 in T, k > 2, such that a is adjacent to exactly k pendant vertices in T. Denote by a' the unique vertex adjacent to a, whose degree is greater than 1. Subdivide once the edge a'a and denote the resulting graph by T'. Then D(T') > D(T) + 8.
PROOF. Analogously as in the proof of Lemma 4.4, it is enough to consider only those pairs of vertices, whose distance or degrees in T and T', are different. Denote by b the vertex subdividing the edge a'a in T'. In D(T') we need to add pairs containing b, as these pairs do not occure in terms of D(T). Moreover, for all pairs which are connected by a path containing b, we need to increase their distance by 1. Finally, we need to include a single term depending on the degree of b. Hence, using Proposition 4.1 we obtain (the sums go through u G V(T) such that u — b path in T' does not contain a, and d(u, a) is considered in T)
m
CD
$H
CD
m
u
a
CD U
D(T') — D(T)
E(2du 2(du — 1) — 1 — 4J d(u, a)
u
+ E f (du — 1) |~4(du — 1) — 5
+ ( 2(k + 1)
— 4 ■ 1 + k
4k — 5
+1
—4
2k — 1 + k(2[—1] — 4) ■ 2 + k
+ £ (du (k + 1) [2(du — 1)k — 1
u
u
E (2du [2du — 3] — 4) d(u, a)
u
+ E [(du — 1)(4du — 6) — 3du + 3 + 1 + 2du k2(du — 1)
+ du k + du k — 2du k — du k — du — 4 — kdu — 4k + 4k2 + 2k — 6 + 4k2 — 5k + 1 — 12k + k — 1 E ( (2du [2du — 3] — 4)d(u, a) + 2du k(k(du — 1) — 2)
Ot	\
+ du (du k — 4) + k(du — 4) + (du — 1)2(2du — 3)
+ 2k(4k — 7) — 6 ^h(u) + 2k(4k — 7) — 6.
Recall that k > 2. If du > 2 then 2du[2du - 3] - 4 > 0, k(du - 1) - 2 > 0, duk - 4 > 0, dU - 4 > 0 and also (du - 1)2(2du - 3) > 0. Hence, h(u) > 0 in this case. On the other hand, h(u) = -6d(u, a) - 6k - 4 < 0 if du =1. Nevertheless, we ~ show that h(u) > 10.
Analogously as in the proof of Lemma 4.4, let S be the set of vertices of degree at least 3 of V(T) \ {a}. For every u G S denote by S(u) the set consisting of u and all pendant vertices of T adjacent to u. Then S(u) if S(u') = 0 for every u,u' G S, u = u'. Observe that UueSS(u) contains all vertices v of V(T), for which v - b path in T' does not contain a and which degree is different from 2. Since h(v) > 0 if dv = 2, we have
5>(v) >£ E h(v).
v	ues veS(u)
Let u G S. We find a lower bound for veS(u) h(v). Suppose that u is adjacent 1—1 to l leaves in T, where l < du - 1. Then
o

CD CO
u
a
CD U
Y h(v) = ^2du (2du - 3) - 4) d(u,a) + 2du k(k(du - 1) - 2^
(v
veS(u)
+ du (du k - 4) + k(du - 4) + (du - 1)2(2du - 3) - 6l(d(u,a) + 1^ - 6kl - 4l.
o
Since for every vertex v of degree 1 we have h(v) < 0 and since l < du - 1, we have
i
E h(v) > ^2du (2du - 3) - 4^ d(u,a) + 2du k(k(du - 1) - 2^
veS(u)
+ du (du k - 4) + k(du - 4) + (du - 1)2(2du - 3)
- 6(du - 1) (d(u, a) + - 6k(du - 1) - 4(du - 1)
CO
= (2du (2du - 6) + d(u, a) + 2du k(k(du - 1) - 4^
+ du (2du k - 2k - 4) - 4k + (4du - 10du + 6)
u
- 6du + 6 + 6k - 4du + 4.
Since du > 3, we have 2du - 6 > 0 and consequently 2du(2du - 6) + 2 > 0. Thus,
J] h(v) > (4du - 12du + 2) + 2du k(k(du - 1) - 4)
ves(u)
+ du (2du k - 2k - 8) + (4du - 16du + 10) -h 2k + 6
= 2du ^k(du - 1) - 4)+2du (k(du - 1) - 4)
+ (8du - 28du + 12) + 2(k + 3) = 2du (k + 1) (k(du - 1) - 4) + 4(2du - 1)(du - 3) + 2(k + 3).
Since du > 3 and k > 2, we have k(du — 1) — 4 > 0 and du — 3 > 0, so that
o	_
Y h(v) > 2(k + 3) > 10.
ves(u)
i—l
Since k > 2, we have 2k(4k — 7) — 6 > —2. As T is not a path, we have |S| > 1, so that
m
Y h(v) + 2k(k — 7) — 6 > Y Y h(v) — 2 > 10 — 2 > 10 — 2 > 8.
v	ues ves (u)	ues
<
o

m
CD
i
u
□
Denote by Hs a tree obtained by subdividing the central edge of H. Since W(Hs) = 48, W(L(Hs)) = 27 and W(L2(Hs)) = 38, we have D(Hs) = 4. By Lemma 4.3 D(H) = —4, so that Lemma 4.5 is sharp for T = H.
Proof of Theorem 1.5. By induction we prove that D(T) > 0 if T is 2+-tree different from K13 and H. If T is a star K1k, k > 4, then D(T) > 0 by Lemma 4.2, while D(H) = —4 by Lemma 4.3. Thus, suppose that T has at least two vertices of Q degree at least 3 and T is different from H.
Denote by T* a subgraph of T formed by vertices of degree at least 2. Then T* is a nontrivial tree, so that it has at least two pendant vertices. Denote by a a pendant vertex of T*, whose degree in T is the smallest possible. Moreover, denote by v a vertex of T* which is adjacent to a. Consider the degree of v in T. We distinguish C^ two cases.
• dv > 3: Remove from T all pendant vertices adjacent to a, together with the corresponding edges, and denote the resulting graph by T'. In T' the vertex a has degree 1 and is adjacent to v, where dv > 3. Thus, T' is a 2+-tree. Since T = H, by the choice of a if T' has only one vertex of degree at least 3, then T' is K1;k, where k > 4, so that D(T') > 0, by Lemma 4.2. If T' has at least two vertices of degree at least 3, then D(T') = —4 if T' is H by Lemma 4.3, while otherwise D(T') > 0 by induction. Since D(T) > D(T') + 20 by Lemma 4.4, we have D(T) > 0.
• dv = 2: Denote by a' the vertex of T adjacent to v, a' = a. Remove from T the vertex v and the edges va and va', insert the edge aa', and denote the resulting graph by T'. Then T' is a 2+-tree having at least two vertices of degree at least 3. Hence D(T') = —4 if T' = H by Lemma 4.3, while otherwise D(T') > 0 by induction. Since D(T) > D(T') + 8 by Lemma 4.5, we have D(T) > 0.
U
a
CD U
00 +->
CO
M <
00
Hence, in both cases we have D(T) > 0. Since D(T) = 4[2W(L2(T))-W(L(T))-W(T)], by Corollary 1.4, we have W(L3(T)) > W(T) for every 2+-tree different from K 1,3 and H.
By Lemma 4.3 we have also W(L3(H)) > W(H), so that W(L3(T)) > W(T) for every 2+-tree different from	□
Acknowledgements. The first author acknowledges partial support by Slovak research grants VEGA 1/0489/08, APVV-0040-06 and APVV-0104-07, and the second the support of Slovenian research agency ARRS, project number J1-0540.
References
0
o
1
00 ^
CO CO
[1] [2]
[3]
[4]
[5]
[6]
[7
F. Buckley, Mean distance in line graphs, Congr. Numer. 32 (1981), 153-162.
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(3) (2001), 211-249.
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. Natur-forsch. 57 A (2002), 824-828.
L. Niepel, M. Knor, L. Soltes, Distances in iterated line graphs, Ars Combin. 43 (1996), 193-202.
J. Plesnik, 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.
CO CD
$H
CD CO
u
a
CD U