IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1159 ISSN 2232-2094 SOME REMARKS ON INVERSE WIENER INDEX PROBLEM Jirl Fink Borut Luzar Riste Skrekovski Ljubljana, September 7, 2011 IN U CD rO CD 10 CM £ CO CO CO CD u a Some Remarks on Inverse Wiener Index Problem Jiri Fink1* Borut Luzar2} Riste Skrekovski2* a CD Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University Malostranske namestl 25, 118 00 Prague 1, Czech Republic E-mail: fink@kam.mff.cuni.cz 2 Institute of Mathematics, Physics, and Mechanics, Jadranska 19, 1111 Ljubljana, Slovenia E-mail: {borut.luzar, skrekovski}@gmail.com Abstract o In 1995 Gutman and Yeh [3] conjectured that for every large enough integer w there exists a tree with Wiener index equal to w. The conjecture has been solved by Wang and Yu [8] and independently by Wagner [6]. We present a constant time algorithm to construct a tree with a given Wiener index. Moreover, we show that there exist non-isomorphic trees with Wiener index w. CM Keywords: Wiener index, Inverse Wiener index problem CM 00 1 Introduction The sum of distances between all pairs of vertices W(G) in a connected graph G as a graph invariant was first introduced by Wiener [9] in 1947. He observed a correlation between boiling points of paraffins and this invariant, which has later become known as Wiener index of a graph. Today, the Wiener index is one of the most widely used descriptors in chemical graph theory. Due to its strong connection to chemistry, where molecules have a tree-like structures, a lot of research was done on acyclic graphs (see [2] for survey). In 1995 Gutman and Ye [3] considered an inverse Wiener index problem. They asked for which integers n there exist trees with Wiener index n, and posed the following conjecture: Conjecture 1. For all but finitely many integers n there exist trees with Wiener index n. Inspired by the conjecture above, Lepovic and Gutman [4] checked integers up to 1206 and found 49 integers that are not Wiener indices of trees. In 2004, Ban, Bereg, and Mustafa [1] computationally proved that for all integers n on the interval from 103 to 108 there exist a tree with Wiener index n. Finally, in 2006, two proofs of the conjecture were published. First, Wang and Yu [8] proved that for every n > 108 there exists a caterpillar tree with Wiener * Supported by project 1M0545 of the Czech Ministry of Education and Czech-Slovene bilateral project BI-CZ/10-11-004. ^Operation part financed by the European Union, European Social Fund. ^Supported in part by ARRS Research Program P1-0297. o CM IN $H CD rO a CD a CD CO & 10 0 Ö o CM 1 CM CO CM CM £ CO CO index n. The second result is due to Wagner [6], who proved that all integers but 49 are Wiener indices of trees with diameter at most 4. In Section 2, we present a proof, similar to Wagner's, that we use to develop a constant time algorithm, which for a given, sufficiently large integer w returns a tree with diameter 4 and with Wiener index w in a constant number of arithmetic operations. In Section 4, we prove that there exist at least non-isomorphic trees with Wiener index w, i.e. there exist wo and C > 0 such that for every w > u>o there are at least 2° ^ trees with Wiener index w. On the other hand, note that the number of non-isomorphic trees with Wiener index w is at most . 2 Inverse Wiener index problem for large values Here, we present a proof of Conjecture 1, similar to Wagner's, for large values. Let k, m and s1,...,sk be non-negative numbers such that m = ^k=1 Sj. Let Tsi,...,sk be a tree that has one center vertex with k neighbours, called branches, and a branch i has other Si neighbours, called terminals. Fig. 1 depictes the tree To,2,3,4. Note that Tsi,...,si, has m terminals and n = m + k + 1 vertices. First, we compute the Wiener index of Tsi, .,Sk • Lemma 1. Figure 1: A tree T0,2,3,4 with four branches and nine terminals. W(Tsu...,sk) = 2m2 + (3k - 1)m + k2 - ^ s i=1 CO CD CD CO u a CD U Proof. We have three types of vertices (center, branch and terminal) and we compute the number of pairs of vertices of given type. Type of vertices distance number of pairs of vertices center - branch 1 k center - terminal 2 m branch - branch 2 G) branch - terminal 1 m branch - terminal 3 Hi (m-8i) terminal - terminal 2 >:■, m terminal - terminal 4 h TH=i Si{m - Si) 2 o CM IN $H CD rO a CD a CD CO & 10 0 Ö o CM 1 CM CO CM CM £ CO CO CO CD $H CD CO $H a CD U We sum up all products of the second and the third columns to obtain Wiener index of T, si, ,Sk . First, we sum up the last two rows separately. 2Eu = k k k s2 — m + 2m2 — 2 > s2 = 2m2 — > s2 — m . i=1 i=1 i=1 Now, we sum up all rows to obtain W(T2 Si,...,Sk ) = 2m2 + (3k — 1)m + k2 — £k=1 s?- □ Since £k=1 si and £k=1 s2 have the same parity, the parity of W(TSl,...,Sfc) depends only on the number of branches and terminals, thus moving terminals between branches does not change the parity. However, we obtain different Wiener indices by moving terminals between branches in TSl,...,Sk with fixed number of vertices and branches. Our aim is to cover a long ,,k interval of numbers of the same parity by Wiener indices of Ts ,, k with fixed k and m. Therefore, we need to know which values of £k=1 s2 are obtained when the sum £k=1 si equals m. The further computation is made simpler by restricting our attention on situation 0 < si < s for all i € [k], where s is a fixed number and [k] denotes the set {1,2,..., k}. Lemma 2. Let s, k and m be natural numbers such that k < m < 2k. Let Mmin = 3m — 2k and Mmax = s (m — (2)). For every z with the same parity as Mmin and Mmin < z < Mmax there exist s1,..., sk € {0,..., s} such that 52k=1 si = m and^k=1 s2 = z. Proof. We prove the statement by induction on z. The smallest value of z = Mm by choosing s1,..., s2k-m = 1 and s2k-m+1,..., sfc = 2. is obtained Let us assume that £i=1 si = m and £i=1 s2 = z where Mmin < z < Mmax — 2. We show how to obtain a sequence s1,..., sk such that £k=1 si = m and £k=1 s2 = z + 2. We will show that there exist two indices a and b such that 0 < sa = sb < s. Then, just let sa = sa — 1 and sb = sb + 1 and si = si for all other i and observe that the sequence s1,..., sk satisfies our requirements. So, if there are no such a and b, then every number of [s — 1] occurs at most once in the sequence s1,..., sk. Since £k=1 si = m, there exist at least r v^s — 1 • 1 m~T,i=i* s s indices i with si = s. But, this is impossible since -(5)" z = £ s2 > s2 i=1 sm = Mmax > z + 2 . □ Now, we present a short proof of the inverse Wiener index problem for large values. Theorem 3. For every sufficiently large number w there exists a tree T with Wiener index w. Proof. We put m = k+1 in order to make the computation simpler. Hence, using the notation of Lemma 2, we have Mmin = k + 3 and Mmax = s (k + 1 — (2) )• By Lemma 1, it follows that W(TSl,...,Sfc) = 6k2 + 6k + 1 — k=1 s2. As the smallest value of 52k=1 s| is k + 3, we obtain that W(Tsi,...,sk) < 6k2 + 5k — 2. Now, let k be the smallest number of the same parity as w that satisfies w < 6k2 + 5k — 2. Let z = 6k2 + 6k + 1 — w. Notice that z has the same parity as Mmin and z > Mmin. If z < Mmax then by Lemma 2 there exists a sequence si,..., sk such that k=1 si = m and ^k=1 s2 = z, and then by Lemma 1, the Wiener index of Tsi,...,sk is w. So, it only remains to prove the inequality z < Mmax. By the definition of z, we know w = 6k2 + 6k + 1 — z, and by minimality of k we infer that w > 6(k — 2)2 + 5(k — 2) — 2, which implies 25k — 11 > z. We have to prove that s (k — (s) + 1) > z, and it suffices to prove s (k — (2) + l) > '25k — 11, which we can simplify to k(s — 25) > |s3 — |s2 — s — 11. Since w is sufficiently large, we can assume that k > s ~2(s-25) 22 ^ where s is a fixed constant of size at least 26, and this establishes the theorem. □ a CD CO 10 o Ö I CSF 00 CSF £ CO CO 3 Algorithm Theorem 3 and Lemma 2 immediately give us the following algorithm which finds a tree with Wiener index w. Algorithm 1 Require: Wiener index w that is large enough. k The smallest number of the same parity as w that satisfies w < 6k2 + 5k — 2. m ^ k + 1 z ^ 6k2 + 6k + 1 — w {Now, we find si,..., sk such that 0 < si,..., sk < s and ^k=1 s = m and ^k=1 s2 = z.} si,... ,sfc-i ^ 1 Sk ^ 2 {We start with s1,..., sk satisfying ^k=1 si = m and the minimum value of ^k=1 s2 which we increase by 2 in every step.} while Ekk=1 s2 2 in a constant time. Note that numbers to,... ,ts uniquely describe Tsi,...,sk, so output of our algorithm is only s + 1 numbers. Now, we describe how we speed up the while loop. For a given w we compute k, m, and z as described in Algorithm 1, and from them we create the required sequence s1,... ,sk in two steps. a In the first step, we compute a, ft, and 7 to be the number of branches with 0, 1, and s terminals, respectively. There remains k' = k — a — ft — 7 undefined numbers of the sequence. o CM IN $H CD rO CD a CD CO m 0 Ö o CM 1 CM CO CM CM £ CO CO CO CD $H CD CO Jh a CD U The sum of undefined numbers must be m' = m — ft — sy; and the sum of squares of undefined numbers must be z' = z — ft — s2y. In the second, we use Lemma 2 to find a sequence for the triple (k', m', z'). If we prove that all numbers of the new triple (k', m', z') are bounded by a constant, then the number of iterations in the while loop is bounded by a constant. Let us recall our conditions: k' = k — a — ft — y, m' = m — ft — sy , z' = z — ft — s2y , 3m' — 2k' < z' < si m' — (1) 2 Lemma 2 requires that the last inequality is satisfied. Note that the given triple (k, m, z) satisfies 3m — 2k < z < s (m — (2) ) which is assured by the proof of Theorem 3. Recall that m = k + 1. We keep the same relation also for m' and k', i.e. m' = k' + 1. This implies a = 7 (s — 1) and simplifies our conditions in the following way: k' = k — ft — sy , z' = z — ft — s2y , k' + 3 < z' < s ^k' — ^1+1 Replacing the values of k' and z' in (1) gives us: k — ft — sy + 3 < z — ft — s2y < s ^k — ft — sy — (^J + 1 ) , which can be simplifed in the following way: k — sy + 3 < z — s2y and z — ft < s ^k — ft — ^ + 1 Hence, we can easily solve the two inequalities independently. We choose the solutions: ft = s(k+l)-Z _ «2 s-1 2 and y = z—k—3 s(s-l) It remains to show that we can bound all parameters k', m', and z' by a constant. From the definitions of k', ft, and y it follows that k' = k — ft — sy , ft+i > Y + 1 > z—k—3 s(s-l) It implies that k' is bounded by + s + which is a constant. Hence, m' is also bounded since m' = k' + 1. Similarly, from z' < s (k' — (2) + 1) it follows that z' is also bounded by a constant s ^ + 1 + ttt)- This analysis implies the following theorem: Theorem 4. The Algorithm finds a tree with a given sufficiently large Wiener index in a constant time. IN $H CD rO CD a CD co m 0 Ö o CM 1 CM 00 CM CM £ CO CO CO CD $H CD CO Algorithm 2 Constant time algorithm for constructing tree of given Wiener index Require: Wiener index w that is large enough. {Specify a constant s that is used in calculations.} s ^ 26 {Compute k to be the smallest number of the same parity as w that satisfies w < 6k2 + 5k - 2.} k 2. {A trivial loop over all indices.} {Move one terminal from a branch with i terminals into another branch with i terminals.} ti-1 ti-1 + 1 ti ^ ti 2 ti+1 ^ ti+1 + 1 end for {We add branches that were created in the beginning.} to to + a t1 ^ t1 + ft ts ^ ts + Y 4 Semi-exponential number of trees with given Wiener index U a CD U In this section we prove that there exist at least trees with Wiener index w. Here, let us mention that, a tree with Wiener index w has at most Lv^J + 1 vertices, since the Wiener index of the star Sn is (n — 1)2 and it is the smallest among all trees on n vertices. It is known IN $H CD CD CD CO in a CD U that there are at most 3n non-isomorphic trees on n vertices (see [5]), hence there are at most |ywj+i g 3* = 3(3LV^J+I _ i) i=1 non-isomorphic trees with at most y/w + 1 vertices. This proves the following proposition. Proposition 5. There is at most 2^v^) non-isomorphic trees ■with Wiener index w. a In order to obtain many non-isomorphic trees with the same Wiener index w, we increase the maximum number of terminals on a branch to p, where p = p(k) is a function of number of branches k. As described in the previous section, we denote a tree Tsi,...,sk also by T*,...,tp, where U is the number of branches with precisely i terminals, for i € {0,1,... ,p}. Let s be a fixed integer, and let p > s be of the same parity as s. We show that for every combination of numbers tj, where j € P = {s + 1, s + 3,... ,p — 1} and tj € {0,1}, there exist numbers tk, for k € {0,1,...,p}\P, such that W(Tt*,...,tp) = w. It is easy to see that all possible combinations of tj, j € P, give exactly 2(p-s)/2 distinct sequences, i.e. non-isomorphic trees. Note that the numbers in P are of the same parity. Next, let us introduce the notation used in this section. Let k1, m1, z1, k2, m2, and z2 be defined as s s s k1 = ^ ti, m1 = ^2 i ti, Z1 = ^2 i2 ti, i=0 i=0 i=0 p p p k2 = ti , m2 = ^2 i ti , Z2 = ^2 i2 ti. i=s+1 i=s+1 i=s+1 By the above definitions, the number of branches k, terminals m, and the sum of squares of numbers of terminals z, respectively, is k = k1 + k2 , m = m1 + m-2 , z = Z1 + Z2 . (2) Now, we describe how to compute the undefined values of the sequence {ti}P=0, after the values tj, j € P, are fixed. We want the number of branches with big number of terminals (at least s + 1) to be always the same, so that the possible values of m2 and z2 are on a small interval. Therefore, we define ti+1 = 1 — ti, where i € P. Hence, the value of k2 is always equal to l-H h2 = %(p-s). (3) CD Note that the minimum (resp. maximum) values of m2 and z2 are obtained when for every j € P holds that tj = 1 (resp. tj =0). It is easy to see that the following inequalities hold: CO \(p2-s2)< m2 < \(p(p + 2) -s(s + 2)) (4) | (pD — CD* z2 ,(p+2) — (s+2). (5) Now, we present a variation of Lemma 2 in terms of ij's. Lemma 6. Let s, and mi be natural numbers such that s is fixed and ki < mi < 2ki. (6) Let Mmin = 3mi — 2ki and Mmax = s (mi — (2)). For every integer zi with the same parity CD as Mmin and rO CD IO CO Mmin < Zi < Mmax (7) there exist t0, • • •, ts € {1,..., ki} such that^s=0 U = ki, ^2=o i ^ = mi, and^s=0 i2 U = zi. The equivalence between Lemmas 2 and 6 is obvious. Now, we are ready to state the main theorem of this section. Theorem 7. There exists a function f(w) € such that for every sufficiently large integer w there exist at least 2f(w) trees with Wiener index w. Proof. In the proof we use the notation given above. We will prove that there exist at least 2(p-s)/2 non-isomorphic trees with sufficiently large Wiener index w, where s = 124 and p is a function of k\ of order Q( tfw), defined as follows: p = p(ki) = LaAiJ " (Lv^iJ mod 4) . (8) Recall that k is of order 0(y/w). Hence k\ is also of order 0(y/w), since k = k\ + ^(p — s). Let tj € {0,1}, where i € P, be arbitrarily chosen, and set ti+i = 1 — tj. Observe that by this procedure all tj, for i € {s + 1, s + 2,... ,p} are fixed and so are k2, m2, and z2. We will show that for every selection of tj's, i € P, there exist numbers tj, j € {0,1,..., s}, such that ki = ^2=0 tj, mi = ^2=0 i tj, and zi = ^2=0 i2 tj. Hence, the Wiener index of Tt* ,...,tp will be w. In order to do this, we need to satisfy the conditions of Lemma 6. CM Let m = 2k — 2. From (2) it follows mi + m2 = 2(ki + k2) — 2. Hence, CM £ By Lemma 1, we have mi = 2(ki + k2) — 2 — m2 . (9) w = W(T*, ) = 15k2 — 24k + 10 — z . (10) Note that (10) implies z = 15k2 — 24k + 10 — w. We proceed by showing that all the assumptions of Lemma 6 are satisfied. First, we show that the assumption (6) holds. By substituting m2 in (9) with its minimum and maximum value derived in (4) and k2 with its value derived in (3) we obtain the lower and upper bound ^ for mi: CO mi > 2kx-\p2+ \p + \s2-\s-2, (11) mi < 2k\ - \p2 + p + \s2 - s - 2 . (12) Note that by the definition of p, the inequalities (11) and (12) imply that the assumption (6) of Lemma 6 is satisfied, since w is large enough. Now, we show that we satisfy the assumption (7). First, note that by (5), we have the following lower bound for z = zi + z2: Z > Z*, (13) CO u CD CO Some Remarks on Inverse Wiener Index Problem where z*2 = i{p(k1js-p(k1)-s3 + s). IN Now, we compute the upper bound M(fci) that the Wiener index of TO t can achieve. We do this by substituting z in the equality (10) with its minimum value derived in (13). We also substitute k2 by its value defined in (3). M(ki) = 15(ki + fc2)2 - 24(ki + k2) + 10 - z2 = 15 {h + - s))2 - 24 (fci + - s)) + 10 CD Let k1 be the smallest integer of the same parity as w such that M(k1) > w. By the choice ~ of k1, we also obtain the inequality ^ 2 w > 15 ((fci - 2) + - 2) - s))' -24((fci-2) + i(p(A;i-2)-s))+10 - 4 - 2)3 - - 2) - s3 + s) . (14) 6 Now, we apply the equality (1°) to the inequa]ity (I4) usi„g that k = k1 + k2 and otata that 15 (ki + 4(p(ki) - s))2 - 24 (ki + 4(p(ki) - s)) + 10-z2-z1> 15 ((ki - 2) + i(p(ki - 2) - s))2 - 24 ((ki - 2) + ¡(p(ki - 2) - s)) + 10 - i (p(k! - 2)3 - p(k! - 2) - s3 + s) . (15) o In order to simplify the calculations, we use the inequality i p(ki) - p(ki - 2) < 4 . (16) CM It is easy to verify that (16) holds for every ki > 4. By plugging the inequality (16) in (15) we infer mP(h - 2)3 - p(h -2)-s3 + s). (17) l-H Now we show that the assumption (7) of Lemma 6 is satisfied. The maximum value that zi attains, is obtained when z2 is as small as possible. By replacing z2 with its lower bound z|, we infer zi < 120ki + 60 V ki - 60s - 216 - z2 zi < 120ki + 60y ki - 60s - 216 < Mmax . Since s = 124, the right side of assumption (7) of Lemma 6 is satisfied. On the other hand, the minimum value of zi is at least Mmin = 3mi — 2ki, since s s s zi — Mmin = J] i2ti — ^(3i — 2)ti = — 1)(i — 2)ti > 0 . i=0 i=0 i=0 Finally, we argue the parity condition of Lemma 6. First, note that k2 (defined in (3)) is always even, since p and s are both divisible by 4. It follows that k = k1 + k2 has the same parity as w, since we chose k1 to have the same parity as w. Using this fact and the equality (10) we have that z is even. Since z = z1 + z2, we infer that z1 and z2 have the same IN $H CD rO parity. Obviously, z2 = ^¿=s+1 i2 ti and m2 = ^¿=s+1 iti also have the same parity. On the other hand, since m = 2k — 2, it follows that m = m1 + m2 is always even, implying that m1 has the same parity as m2. Now, m1, m2, z1, and z2 have the same parity, which implies that Mmin = 3m1 — 2k1 and z1 are also of the same parity as required in Lemma 6. Hence, we have satisfied all asuumptions of Lemma 6, therefore there exist j, j € {0,1,..., s}, such that W{T£0 ^ ^ ) = w what completes the proof. □ CD a CD CO lO 0 Ö o CM 1 CM CO CM CM £ CO CO References [1] Y. A. Ban, S. Bereg, N. H. Mustafa, On a conjecture on Wiener indices in combinatorial chemistry, Algorithmica 40 (2004), 99-117. [2] A. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001), 211-249. [3] I. Gutman, Y. Yeh, The sum of all distances in bipartite graphs, Math. Slovaca 45 (1995), 327-334. [4] M. Lepovic, I. Gutman, A collective property of trees and chemical trees, J. Chem. Inf. Comput. Sci. 38 (1998), 823-826. [5] R. Otter, The Number of Trees, Ann. Math. 49 (1948), 583-599. [6] S. Wagner, A class of trees and its Wiener index, Acta Appl. Math. 91(2) (2006). 119-132. [7] S. Wagner, H. Wang, G. Yu, Molecular graphs and the inverse Wiener index problem, Discrete Appl. Math. 157 (2009), 1544-1554. [8] H. Wang, G. Yu, All but 49 numbers are Wiener indices of trees, Acta Appl. Math. 92(1) (2006), 15-20. [9] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), 17-20. CO CD Jh CD CO u a CD U