IMFM
Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA
Preprint series Vol. 48 (2010), 1113
ISSN 2232-2094
ON WIENER INDEX OF GRAPHS AND THEIR LINE GRAPHS
Nathann Cohen Darko Dimitrov
Roi Krakovski Riste Skrekovski Vida VukaSinovic
Ljubljana, February 12, 2010
CO CD
■ i-H
u
CD
On Wiener index of graphs and their line graphs
Nathann Cohen 1, Darko Dimitrov 2, Roi Krakovski 3, Riste Skrekovski 4, Vida Vukasinovic 5
February 10, 2010
1 INRIA - Projet MASCOTTE, 2004 route des Lucioles, BP 93 F-06902, Sophia Antipolis Cedex, France nathann.cohen@sophia.inria.fr 2 Institut fur Informatik, Freie Universitat Berlin, Takustrafie 9, D-14195 Berlin, Germany darko@mi.fu-berlin.de 3 Department of Computer Science, Ben Gurion University of the Negev, Beer-Sheva 84105, Israel roikr@cs.bgu.ac.il 4 Department of Mathematics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia skrekovski@gmail.com 5 Computer Systems Department, Jozef Stefan Institute, Jamova 39, 1000 Ljubljana, Slovenia vida.vukasinovic@ijs.si
Abstract
The Wiener index of a graph G, denoted by W(G), is the sum of distances between all pairs of vertices in G. In this paper, we consider the relation between the Wiener index of a graph, G, and its line graph, L(G). We show that if G is of minimum degree at least two, then W(G) < W(L(G)). We prove that for every non-negative integer go, there exists g > g0, such that there are infinitely many graphs G of girth g, satisfying W(G) = W(L(G)). This partially answers a question raised by Dobrynin and Mel'nikov [8] and encourages us to conjecture that the answer to a stronger form of their question is affirmative.
Keywords: Wiener index, line graphs
1 Introduction
In this paper all graphs are finite, simple and undirected. For a graph G, we denote by V(G) and E(G) its vertex and edge sets, respectively. All paths and cycles are simple, i.e., they contain no repeated vertices. A path Pn = x\x2 ■ ■ ■ xn is given by the sequence of its consecutive vertices. A path whose endvertices are u and v is called an uv-path. The length of a path P, denoted |Pis the number of its edges. A cycle of length k is denoted by Ck. Given a graph G, its line graph L(G) is a graph such that
• The vertices of L(G) are the edges of G; and
J-i
a	• Two vertices of L(G) are adjacent if and only if their corresponding edges in G share a
common endvertex.
CD U
CSI
For a vertex v € V(G), we denote by dG (v) the degree of v in G. For the sake of simplicity we write d(v) if the graph G is clear from the context. For v,u € V(G), we denote by dG(u, v) (or simply d(u, v)), the length of a shortest path in G between u and v. For ei,e2 € E(G), we define dc(ei,e2) = dL(c)(ei,e2).
The Wiener index of a graph G, denoted by W(G), is the sum of distances between all (unordered) pairs of vertices of G, i.e.,
W (G)= £ d(u,v).
(G)
CD
00
The Wiener index is a graph invariant that belongs to the molecules structure-descriptors called topological indices, which are used for the design of molecules with desired properties [18]. For details and results on the Wiener index see in [6, 7, 16, 17] and the references cited therein.
The concept of line graph has various applications in physical chemistry [12, 15]. Recently there has been an interest in understanding the connection between W(G) and W(L(G)) for a graph G. In particular, it is important to understand when a graph G satisfies W(G) = W(L(G)). In sequel, we state some results related to those presented in this paper. For more results on the topic see [4, 5, 9, 10, 12, 14].
Theorem 1 (Buckley [3]). For every tree T, W(L(T)) = W(T) - (n).
Theorem 2 (Gutman [11]). If G is a connected graph with n vertices and q edges, then
C^
W(L(G)) > W(G) - n(n - 1) + -q(q + 1).
00
Theorem 3 (Gutman, Pavlovic [14]). If G is a connected unicyclic graph with n vertices, then W(L(G)) < W(G), with equality if and only if G is a cycle of length n.
£
CO CO
In Section 2 it will be shown that, if G is of minimum degree at least two, then, W(G) < W(L(G)), with a strict inequality as soon as G is not a cycle.
For a graph G, it seems difficult to characterize when W(G) = W(L(G)). Moreover, it is not clear on which graph parameters or structural properties the difference W(G) — W(L(G)) depends.
A connected graph G is isomorphic to L(G) if and only if G is a cycle. Thus, cycles provide a trivial infinite family of graphs for which W(G) = W(L(G)). That is, for every positive number g there exists a graph G with girth g for which W(G) = W(L(G)). In connected bicyclic graphs all the three cases W(L(G)) < W(G), W(L(G)) = W(G), and W(L(G)) > W(G) occur [14]. It is known that, the smallest bicyclic graph with the property W(L(G)) = W(G) has 9 vertices and is unique. There are already 26 ten-vertex bicyclic graphs with the same property [13]. In [8], Dobrynin and Mel'nikov have constructed infinite family of graphs of girth three and four with the property W(G) = W(L(G)), and asked the following:
CD W
U
a
CD U
Problem 1 (Dobrynin and Mel'nikov [8]). Is it true that for every integer g > 5, there exists a graph G = Cg of girth g, for which W(g) = W(L(G)) ?
The following is the main result of this paper, and provides a partial answer to Problem 1.
Theorem 4. For every positive integer g0, there exists g > g0 such that there are infinitely many graphs G of girth g satisfying W(G) = W(L(G)).
Our result encourages us to state the following conjecture. The answer to it for graphs of girth three and four is affirmative [8].
Conjecture 1. For every integer g > 3, there exist infinitely many graphs G of girth g satisfying W(G) = W(L(G)).
?
2 Graphs with minimum degree at least two
The following folk lemma is needed for the proof of Theorem 6, and states that the distance between two edges can be bounded by the mean of the distances between their endvertices. For the sake of completness we include its proof.
Lemma 5. Let G be a graph and e = uv, e' = u'v' be two edges of G. Then the following inequality holds:
' 1 T '	'	'	' 1
d(e, e ) > 4 d(u, u ) + d(u, v ) + d(v, u ) + d(v, v ) .
Proof. Without loss of generality, we can assume that d(v, v') = min{d(u, u'), d(u, v' ),d(v, u' ),d(v, v')}. We observe that the following holds:
d(v,u') < d(v,v') + 1, d(u,u') < d(v,v') + 2, and d(u,v') < d(v,v') + 1.
o
Therefore,
1( ' ' ' ' ^ 1 '	'	'
- ( d(u, u ) + d(u, v ) + d(v, u ) + d(v, v ) 1 < - (4 d(v, v ) + 4) = d(v, v ) + 1 = d(e, e ).
CO 4	4
The last equality in the above expression holds by minimality of d(v,v').	□
o
CSI
u
a
CD U
The following is the main result of this section. Theorem 6. Let G be a connected graph with 5(G) > 2. Then,
CO
W(G) < W(L(G)). Moreover, equality holds only for cycles.
Proof. If G is a cycle, then L(G) is isomorphic to G, and so, equality holds. Hence, we may assume that G has at least one vertex of degree at least three. By Lemma 5, we obtain a lower bound on W(L(G)):
W (L(G))= £ d(e,e')
e.e'6 E (G) e=e'
1 ( \
> 4 ^ yd(u,u') + d(u,v') + d(v,u') + d(v,v')J
CD
e ' =u'v' eE(G)
e=e
y^ d(u)d(v)d(u, v) + ^ (d(u)d(v) — 1) d(u, v)
»,v£ V(G)	u,ve V(G)
uv^E(G)	uveE(G)
o
1—1
b
u
CD
CO
0 o
1
CO ^
CO CO
Thus, for the difference W(L(G)) — W(G), we obtain the following lower bound:
W(L(G)) — W(G) > 4
y^ d(u)d(v)d(u, v) + ^ (d(u)d(v) — 1
u,vGV (G) uv^E(G)
E
u,vE V (G) uv^E(G)
u,veV (G) uveE(G)

d(u, v)
u,veV (G)
d(u)d(v) — 4) d(u, v) +
E
u,vE V (G) uveE(G)
d(u)d(v) — 5
(1)
Let G2 be the graph induced by the vertices of degree two in G. Then,
E
u,vev (g2)
uv£E(G2)
^dG(u)dG(v) — dG(u, v) = 0, and y^ ^dG(u)dG(v) — 5^
u,vGV (G2)
uve e(g2)
— |E (G2)|. (2)
From (1) and (2), we obtain
W(L(G)) — W(G) > 4
^ (dG(u)dG(v) — 4) dG(u,v)+ ^ (dG(u)riG(v) — 5) — |E(G2)|
u,vGV (G) {u,v}gV (G2) uv^E(G)
>1
u,v6V (G) {u,v}gV (G2) uveE(G)
>1
As G has at least one vertex x of degree at least 3, the above sums are not empty. Besides, we can ensure that |V(G2)| — 1 > |E(G2)|: indeed, we know that |V(H)| > |E(H)| for any graph H of maximum degree 2 with the equality holds only if H is 2-regular. But, in the present situation there is at least one vertex of degree two adjacent to a vertex of strictly larger degree in G, as the graph G is connected and G2 is a proper subgraph of it. So, G2 is not 2-regular, and so, |V(G2)| > |E(G2)|. Consequently,
W(L(G)) — W(G) > 4
dG(x,v) — |V (G2)| + 1
vev (G2)
1
> -. - 4
m
CD
$H
CD
m
u
a
CD U
This establishes the theorem.
□
3 Graphs whose Wiener index equals to the Wiener index of their line graphs
As the equality W(L(T)) = W(T) — (£) holds for trees [3], and the equality W(L(C)) = W(C) holds for cycles, one can expect that there are some graphs G, comprised of cycles and trees, with property W(L(G)) = W(G). In what follows, we present one such class of graphs.
1—1
b
u
CD
CO
0 o
1
CO ^
CO CO
CO CD
■ i-H $H
CD CO
$H
a
CD Jh
For positive integers k,p,q, we define the graph $(k,p, q) as follows (see Figure 1 for an illustration). The graph $(k,p, q) is simple and comprised of two cycles, Ci = ui ■ ■ ■ u2k+1 and C2 = v1 ■ ■ ■ v2k+1, and two paths Pp = x1 ■ ■ ■ xp and Pq = y1 ■ ■ ■ yq such that all introduced vertices are distinct except for vertices v1 = u1 = x1 and y1 = v2k+1 = u2k+1.
$(k, p, q)
!
xp-1
L($(k,p, q)
U2k
u2k+1
Uk Uk+1
V2k+1 V2
Vq
Vk
Vk+1
U2k-1
V2k-1
' Vq-1
Figure 1: Graphs $(k,p, q) and L($(k,p, q))
We are now interested in computing the difference W(L($(k,p, q))) — W($(k,p, q)), which is determined by the following technical result, and it will be used in the proof of Theorem 8. As the proof is straightforward and rather technical, we present it in the next section.
Theorem 7. For integers, k,p, q > 1, let G = $(k,p, q) with girth g = 2k + 1. Then, W (L(G)) — W (G) = 1(g2 + (p — q)2 + 5(p + q — 3) — 2g(p + q — 3)). We now turn to prove the main theorem of this paper.
Theorem 8. For every non-negative integer h, there exist infinitely many graphs G of girth g = h2 + h + 9 with W(L(G)) = W(G).
Proof. Our candidates are $ graphs defined above. First we prove the following claim: Claim 1. Let a0,a1,k, such that W(L($(k, ao, a1)) = W($(k,ao,a1)) and a0 < a1. Then, from a0 and a1, we can build an infinite strictly increasing sequence a0, a1, a2,... of integers such that for every n > 0, W(L($(k, an, an+1))) = W($(k, an, an+1)).
o
c^
c^ 1—1
CD U
By Theorem 7, such a sequence can only exist if the following equation is verified for all n:
Dn = W(L($(fc,an,an+i))) - W($(fc,ara,ara+i))
1 2	, 1 2	, 1 2 ^o , 5	15
= 2g - gan - gan+i + 2an - anan+i + 2an+i + 3g + 2(an + an+i) - y
where g = 2k + 1. Then,
1 22	5
Dn - Dn+i = g(an+2 - an) - 2(an+2 - an) + an+i(an+2 - an) - 2(an+2 - an)
1	5
= (fln+2 - An)(g - 2(®n+2 + ^n) + ^n+i - 2) 22
= 0.
00
As we want the sequence to be strictly increasing, it is enough to solve the following recursive equation:
g - 1 (an+2 + On) + ^n+i - 5 = 0.	(3)
2 2
It is well known that a solution to (3) is of the form an = cn + pn, where cn = nx + y, for x,y € R, is the homogeneous solution, and pn = cn2, for c € R, is the particular solution. An easy calculation gives y = a0, x = (2 + ai - g - ao) and c = g - 5. Hence,
«n = (g - 5)n2 + (5 + ai - g - ao)n + ao.	(4)
2 2
Observe that for every n > 0, an is an integer and an < an+i. As by assumption a0 and ai satisfy the equation D0 = 0, the claim follows.	♦
CSI
Let k,p, q be positive integers (with g = 2k + 1). By Theorem 7, W(L($(k,p, q)) = W($(k,p,q)) if
CO
g = -3+ p + q + y/24 - 11p - 11q + 4pq.	(5)
Setting p = 3 and q = h2 + 9 for some integer h, one obtains the equation g = h2 + h + 9. Then, g is an odd positive integer. Consequently, for every h € N the parameters g = h2+h+9, k = i(g - 1), p = 3, and q = h2 + 9 satisfy W(L(G)) = W(G). By Claim 1, for every such girth, we can compute an infinite family of graphs G satisfying the same equation by setting a0 = 3 and ai = h2 + 9. Thus, the theorem is proved.
□
Clearly, the set of integer solutions of (5) is not complete (see Fig.2 for other infinite fam-
co
ilies). However, the equation (5) does not have integer solutions for every g, thus preventing us from producing an infinite family of graphs G satisfying W(L(G)) = W(G) for all girths with the $ family.
Theorem 4 is an immediate corollary of Theorem 8. For every positive integer g0, we can
a
choose a non-negative integer h such that g = h2 + h + 9 > g0. By Theorem 8, it follows that there are infinitely many graphs G of girth g with W(L(G)) = W(G).
«N 1—1
b
u
CD
«N
CO
0
«N
o
1
CO ^
CO CO
CO CD
$H
CD CO
u
a
CD U
p	q	g	24 — 11p — 11q + 4pq
3	h2 + 9	h2 + h + 9	h2
4	20h2 + 4	20h2 + 10h + 5	(10h)2
6	13h2 + 12h + 6	13h2 + 25h + 15	(13h + 6)2
6	13h2 + 14h + 7	13h2 + 27h + 17	(13h + 7)2
7	17h2 + 14h + 6	17h2 + 31h + 17	(17h + 7)2
7	17h2 + 20h + 9	17h2 + 37h + 23	(17h + 10)2
9	h2 + 3	h2 + 5h + 9	(5h)2
10	29h2 + 2h + 3	29h2 + 31h + 11	(29h + 1)2
10	29h2 + 56h + 30	29h2 + 85h + 65	(29h + 28)2
12	37h2 + 30h + 9	37h2 + 67h + 31	(37h + 15)2
12	37h2 + 44h + 16	37h2 + 81h + 45	(37h + 22)2
13	41h2 + 4h + 3	41h2 + 45h + 12	(41h + 2)2
13	41h2 + 78h + 40	41h2 + 119h + 86	(41h + 39)2
16	53h2 + 44h + 12	53h2 + 97h + 41	(53h + 22)2
16	53h2 + 62h + 21	53h2 + 115h + 59	(53h + 31)2
18	61h2 + 116h + 58	61h2 + 177h + 123	(61h + 58)2
18	61h2 + 128h + 70	61h2 + 189h + 141	(61h + 64)2
Figure 2: Families of integer solutions
4 Proof of Theorem 7
The proof of Theorem 7 follows from the following two lemmas. Their purpose is to compute the exact value of W(G) and W(L(G)) for the $ graphs.
Lemma 9. Let G be a graph $(k,p,q) where k,p,q > 1. Then,
W (G) = W (Pp+q) + 4W (Pq+k) + 4W (Pp+k) + 2W (C2fc+i) + 2W (P2k+l) + 2W (P2k) — 16W (Pk-i) — 4W (Pq) — 4W (Pp) — p(p + 1) — q(q + 1) — 2(8k2 + k — 2).
Proof. We consider several paths and cycles in G such that each pair of vertices of G belongs to at least one of these subgraphs. See Figure 1 for the notation. In order to make our proof more readable, we denote a shortest path between vertices a and b with P(a,b). The subgraphs we consider are the following:
•	The path P (xp, yq) = XpXp-i • • • xiyiy2 ••• yq of length p + q — 1.
•	The paths P(xp, Vk+1) = XpXp-i • • • X2viv2 • • • vk+1, P(xp, uk+1) = XpXp-i • • • X2uiu2
•	• • uk+i, P(Xp, vk+2) = XpXp-i • • • Xiv2k+iv2k • • • Wk+2 and P(Xp, uk+2) = XpXp-i • • • Xiu2k+i u2k ••• uk+2 of length p + k — 1.
•	The paths P (yq ,vk+i) = yq yq-1 • • • y2v2k+iv2k • • • vk+i, P (yq, uk+i) = yq yq-i • • • y2u2k+i u2k ••• uk+i, P (yq, vk) = yq yq-i • • • yi viv2 • • • vk and P (yq, uk) = yq yq-1 • • • yiuiu2 ••• uk of length q + k — 1.
•	The paths Pi (uk+i,vk+i) = uk+iuk ••• u2viv2 ••• vk+i and P2(uk+i, vk+i) = uk+i uk+2
•	• • u2kv2k+1 v2k • • • vk+1 of length 2k have the same endvertices. Similarly, the paths
P (uk, vk+2) = uk uk-1 • • • uiv2k+iv2k • • • vk+2 and P (uk+2,vk) = uk+2 uk+3 • • • u2k+iviv2 ••• vk are of length 2k — 1.
•	The cycles Cu = ■ ■ ■ u2k+1u1 and Cv = v\v2 ■ ■ ■ v2k+^ on 2k + 1 vertices.
The following pairs of vertices were considered more than once:
C^
•	Pairs of vertices on the paths P(x1,xp), P(y1 , yq), P(v2,vk), P(u2,uk), P(vk+2,v2k) and P(uk+2,u2k) are considered five times.
•	Pair (x1,y1) is on distance 1 and is considered nine times. Similarly pair (uk+1,vk+1) is on distance 2k and is considered twice.
•	Pairs (u1,Uk+1), (v1,vk+1), (uk+1, ^+1) and (vk+1,v2k+1) are on distance k. Similarly pairs of vertices {(uk+1,a)|a € P(u2,uk) U P(uk+2,u2k)} and |(vk+1,a)|a € P(v2,vk) U P(vk+2,v2k)} are on distances 1,2,..., k — 1. All of them are considered three times.
00
o
o
CSI
CO CO
CO CD
u
CD
CD U
Pairs of vertices {(x1,a)|a € P(v2,vk) U P(u2,uk)} and {(y1,a)|a € P(v2k, vk+2) U P(u2k, uk+2)} are on distances 1,2,..., k — 1 and are considered five times.
Pairs of vertices {(x1,a)|a € P(uk+2,U2k) U P(vk+2,v2k)} and {(y1,a)|a € P(u2,uk) U P(v2,vk)} are on distances 2,3,..., k and are considered three times.
Pairs of vertices {(x1, a)|a € P(y2, yq)} are on distances 2,3,..., q and {(y1, a)| a € P(x2, xp)} are on distances 2,3,...,p. They are considered three times.
As the Wiener index of a graph G is the sum of the distances between all pairs of the vertices, we compute it as a sum of Wiener indices of all observed subgraphs and subtract the distances between pairs of vertices which were observed more than once. The distances are multiplied the appropriate number of times. The Wiener index of the graph $(k,p, q) is
00
W ($(k,p,q)) = W (Pp+q) + 2W (Pq+k) + 2W (Pq+k) +2W (Pp+k) + 2W (Pp+k)
+ 2W (C2k+1) + 2W (P2k+1) + 2W (P2k) — 16W (Pk-1) — 4W (Pq)
—	4W (Pp) — 8 ■ 1 — 2k — 4 ■ 2 ■ k — 4 ■ 2(1 + 2 + ■■■ + k — 1)
—	4 ■ 4(1 + 2 + ■ ■ ■ + k — 1) — 4 ■ 2(2 + 3 + ■ ■ ■ + k) — 2(2 + 3 + ■ ■ ■ + q)
—	2(2 + 3 + ■■■ + p) = W (Pp+q ) + 4W (Pq+k) + 4W (Pp+k) + 2W (C2k+1) + 2W (P2k+1)
+ 2W (P2k) — 16W (Pk-1) — 4W (Pq) — 4W (Pp) — p2 — p — q2 — q
— 16k2 — 2k + 4.
□
Lemma 10. Let G = $(k,p, q) where k,p, q > 1. Then,
W (L(G)) = W (Pp+q-1) + 2W (Pq+k-1) + 2W (Pq+k) + 2W (Pp+k-1) + 2W (Pp+k) + 2W (C2k+1) + 2W (P2k) + 2W (P2k+1) — 16W (Pk) — 4W (Pq-1) — 4W (Pp-1) — p(p — 1) — q(q — 1) — 4k(k + 1).
Proof. Similar as in the previous lemma, we consider paths and cycles in L($(k,p, q)) such a that each pair of vertices L(0(k,p, q)) belongs to at least one of these subgraphs. The subgraphs we consider are the following:
o
c^
c^ 1—1
b
u
CD
00
o
CSI
CSI
£
CO CO
u
u
cu
The path P(xp-i, Vq-i) = xp-ixp-2 ■ ■ ■ xiv2fc+iViV2 ■ ■ ■ Vq-i of length p + q - 2.
The paths P (xp-1,vk) = xp-1xp-2 ••• xiviv2 ••• vk, P (xp-1,uk) = xp-i xp-2 ••• xiui u2 ■ ■ ■ uk of length p+k-2 and the paths P(xp-i, vk+i) = xp-ixp-2 ■ ■ ■ xiv2k+iv2k ■ ■ ■ vk+i, P(xp-i, Ufc+i) = xp-i xp-2 ■ ■ ■ xiU2fc+iU2fc ■ ■ ■ ufc+i of length p + k - 1.
The paths P (Vq-i,vfc+i) = Vq-iVq-2 ••• Viv2fc v2fc-i ••• vfc+i, P (Vq-i, Ufc+i) = Vq-iVq-2 ■ ■ ■ ViU2fcU2fc-i ■ ■ ■ Ufc+i of length q+k-2 and the paths P(Vq-i, vfc) = Vq-iVq-2 ■ ■ ■ Viv2fc+i viv2 ■ ■ ■ vfc, P(Vq-i, Ufc) = Vq-iVq-2 ■ ■ ■ Vi U2fc+iUiU2 ■ ■ ■ Ufc of length q + k - 1.
• The paths P (Ufc ,vfc) = Ufc Ufc-i ■■■ Uiviv2 ■■■ vfc, P (Ufc+i, vfc+i) = Ufc+iUfc+2 ■■■ U2fc v2fc v2fc-i ■ ■ ■ vfc+i of length 2k-1 and the paths P(Ufc, vfc+i) = UfcUfc-i ■ ■ ■ Uiv2fc+iv2fc ■ ■ ■ vfc+i, P(Ufc+i, vfc) = Ufc+iUfc+2 ■ ■ ■ U2fc+iviv2 ■ ■ ■ vfc of length 2k.
• The cycles Cu = u1u2 ■ ■ ■ U2k+iUi and Cv = viv2 ■ ■ ■ v2k+ivi on 2k + 1 vertices. The pairs of vertices which were observed more than once are the following:
•	Pairs of vertices on the paths P(xi,xp-i), P(Vi,Vq-i), P(vi,vfc), P(ui,ufc), P(vfc+i,v2fc) and P(ufc+1,u2k) are considered five times.
•	Pairs of vertices |(v2fc+i,a)|a € P(ui,ufc) U P(vi,vfc) U P(ufc+i,u2fc) U P(vfc+i,v2fc)} are on distances 1,2,..., k and are considered three times.
• Pairs of vertices |(v2fc+1,a)|a € P(V1,Vq-1)} are on distances 1,2,...,q - 1 and are considered three times. Similarly pairs of vertices |(v2fc+1 ,a)|a € P(x1,xp-1)} are on distances 1,2,... ,p - 1 and are considered three times.
00
The Wiener index is calculated as a difference between a sum of Wiener indices of all observed subgraphs and corresponding multiplication of distances between different pairs of vertices which were observed more than once:
W (L(G)) = W (Pp+q-i) + 2W (Pq+fc-i) + 2W (Pq+fc) + 2W (Pp+fc-i) + 2W (Pp+fc) + 2W(C2fc+i) + 2W(P2fc) + 2W(P2fc+i) - 16W(Pfc) - 4W(Pq-i)
-	4W (Pp-i) - 4 ■ 2(1 + 2 + ■■■ + k)
-	2(1 + 2 + ■■■ + q - 1) - 2(1 + 2 + ■■■ + p - 1))
= W (Pp+q-i) + 2W (Pq+fc-i) + 2W (Pq+fc) + 2W (Pp+fc-i) + 2W (Pp+fc) + 2W(CWi) + 2W(P2fc) + 2W(P2fc+i) - 16W(Pfc) - 4W(Pq-i)
-	4W(Pp-1) - p2 + p - q2 + q - 4k2 - 4k.
CD
Proof of Theorem 7. By Lemmas 9 and 10, it follows that
□
W(L(G)) - W(G) = W(Pp+q-i) - W(Pp+q) + 2(W(Pq+fc-i) - W(Pq+fc)) + 2(W(Pp+fc-i)
- W(Pp+fc)) + 4(W(Pq) - W(Pq-1)) + 4(W(Pp) - W(Pp-1))
+ 16(W(Pfc-i) - W(Pfc)) + p + q - 4k2 - 4k + p + q + 16k2 + 2k - 4. CD
o
1—1
b
u
CD
CO
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
The Wiener index of a path with n vertices being W(Pn) = (n+^ [2], we have
W(L(G)) - W(G) =
p + q 3

p + 3 + A +2/ (q + k
+2
+4
p + k 3
^p + 1

p+k+1 3

+ 16
p
3	3	3
+ 2(p + q) + 12k2 - 2k - 4
p +2 q - 2 q +2 k - 2 p +2 k
+ 2(p + q) + 12k2 - 2k - 4 1
+4 k

+4 q2 +4 p2
- 16
= 2(-8 + 4k2 + 3p + (p - q)2 + 3q - 4k(-4 + p + q)).
If we set k = (g - 1)/2, we obtain the claimed formula
1
W(L(G)) - W(G) = 2(g2 + (p - q)2 + 5(p + q - 3) - 2g(p + q - 3)).
□
4.1 Wiener index and Combinatorial Nullstellensatz
We bring to reader's attention the fact that the polynomials given in Theorem 8 can be easily obtained through polynomial interpolation with the help of a computer. Indeed, the above proofs can be massively shortened and simplified if one only needs to show that both W(G) and W(L(G)) are low-degree polynomials on the variables k,p and q.
Once bounds on the degree of each variable in the polynomials W(L($(k,p, q))) and W($(k,p, q)) have been derived, it is easy to define a (small) set of representatives of the $ family which are sufficient to define exactly the corresponding polynomials using the Combinatorial Nullstellensatz [1] (less than 30 different graphs in the present case).
This way, a computer can be made to answer very quickly the following question: "given a graph family G depending on several parameters pi,... ,pi, what is the general formula of W(G(pi,... ,pz)) - W(L(G(pi,... ,pz)))?". This is of great help when looking for graphs G satisfying the equation W(G) = W(L(G)), as it reduces the problem to finding the integral zeros of a multivariate polynomial (which is not by itself an easy question).
This approach has to be considered when trying to find more classes of graphs satisfying the above constraint, especially when the $ family used here can be modified in so many ways: one could like to attach paths to the cycles at different points, set two different sizes for the cycles, or to attach trees instead of paths, etc.
U
a
CD U
References
[1] N. Alon. Combinatorial Nullstellensatz. Combin. Probab. Comput., 8(1&2):7-29, 1999.
k
2
«N 1—1
b
u
CD
«N
CO
0
«N
o
1
CO ^
CO CO
CO CD
$H
CD CO
u
a
CD U
[2]	D. Babic, D. J. Klein, I. Lukovits, S. Nikolic, and N. Trinajstic. Resistance-distance matrix: A computational algorithm and its applications. Int. J. Quant. Chem., 90:166176, 2002.
[3]	F. Buckley. Mean distance of line graphs. Congr. Numer., 32:153-162, 1981.
[4]	P. Dankelmann, I. Gutman, S. Mukwembi, and H. C. Swart. The edge-Wiener index of a graph. Discrete Math., 309:3452-3457, 2009.
[5]	A. A. Dobrynin. Distance of iterated line graphs. Graph Theory Notes N. Y., 37:8-9, 1999.
[6]	A. A. Dobrynin, R. Entringer, and I. Gutman. Wiener index of trees: theory and applications. Acta Appl. Math., 66:211-249, 2001.
[7]	A. A. Dobrynin, I. Gutman, S. Klavzar, and P. Zigert. Wiener index of hexagonal systems. Acta Appl. Math., 72:247-294, 2002.
[8]	A. A. Dobrynin and L. S. Melnikov. Some results on the Wiener index of iterated line graphs. Electron. Notes Discrete Math., 22:469-475, 2005.
[9]	A. A. Dobrynin and L. S. Melnikov. Wiener index for graphs and their line graphs with arbitrary large cyclomatic numbers. Appl. Math. Lett., 18(3):307-312, 2005.
[10]	A. A. Dobrynin and L. S. Melnikov. Wiener index, line graph and the cyclomatic number. MATCH Commun. Math. Comput. Chem., 53:209-214, 2005.
[11]	I. Gutman. Distance of line graphs. Graph Theory Notes N. Y., 31:49-52, 1996.
[12]	I. Gutman and E. Estrada. Topological indices based on the line graph of the molecular graph. J. Chem. Inf. and Comput. Sci., 36(3):541-543, 1996.
[13]	I. Gutman, V. Jovasevic, and A. Dobrynin. Smallest graphs for which the distance of the graph is equal to the distance of its line graph. Graph Theory Notes N. Y., 33:19, 1997.
[14]	I. Gutman and L. Pavlovic. More on distance of line graphs. Graph Theory Notes N. Y., 33:14-18, 1997.
[15]	I. Gutman, L. Popovic, B. K. Mishra, M. Kuanar, E. Estrada, and N. Guevara. Application of line graphs in physical chemistry. Predicting the surface tensions of alkanes. J. Serb. Chem. Soc., 62(3):1025-1029, 1997.
[16]	I. Gutman, Y. Yeh, S. Lee, and Y. Luo. Some recent results in the theory of the Wiener number. Indian J. Chem., 32A:651-661, 1993.
[17]	S. Nikolic, N. Trinajstic, and Z. Mihalic. The Wiener index: developments and applications. Croat. Chem. Acta, 68:105-129, 1995.
[18]	M. Randic. In search for graph invariants of chemical interest. J. Mol. Struct., 300:551571, 1993.