/^creative ^commor
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 19-37
https://doi.org/10.26493/1855-3974.1376.7c2
(Also available at http://amc-journal.eu)
ARS MATHEMATICA CONTEMPORANEA
On Wiener inverse interval problem of trees
Jelena Sedlar *
University of Split, Faculty of civil engineering, architecture and geodesy, Matice hrvatske 15, 21000 Split, Croatia
Received 6 April 2017, accepted 30 September 2017, published online 2 November 2017 Abstract
The Wiener index W(G) of a simple connected graph G is defined as the sum of distances over all pairs of vertices in a graph. We denote by W [Tn] the set of all values of the Wiener index for a graph from the class Tn of trees on n vertices. The largest interval of consecutive integers (consecutive even integers in case of odd n) contained in W [Tn] is denoted by Wint [Tn]. In this paper we prove that both sets are of cardinality 1 n3 + O(n5/2) in the case of even n, while in the case of odd n we prove that the cardinality of both sets equals 12n3 + O(n5/2), which essentially solves two conjectures posed in the literature.
Keywords: Wiener index, Wiener inverse interval problem, Tree. Math. Subj. Class.: 05C05, 05C90
1 Introduction
The Wiener index of a connected graph G is defined as the sum of distances over all pairs of vertices, i.e.
W (G) = ^ d(u,v).
u,veV (G)
It was first introduced in [13] and it was used for predicting the boiling points of paraffins. Since the index was very successful many other topological indices were introduced later which use the distance matrix of a graph. There is a recent survey by Gutman et al. [14] in which finding extremal values and extremal graphs for the Wiener index and several of its variations is nicely presented. Given the class of all simple connected graphs on n vertices it is easy to establish extremal graphs for the Wiener index, those are complete graph Kn and path Pn. The same holds for the class of tree graphs on n vertices in which the minimal
* This work has been supported in part by Croatian Science Foundation under the project 8481 (BioAmpMode) and Croatian-Chinese bilateral project "Graph-theoretical methods for nanostructures and nanomaterials". Also, many thanks to the anonymous reviewers for careful reading of the paper and very valuable suggestions. E-mail address: jsedlar@gradst.hr (Jelena Sedlar)
©® This work is licensed under https://creativecommons.Org/licenses/by/3.0/
20
Ars Math. Contemp. 15 (2018) 39-51
tree is the star Sf and the maximal tree is the path Pf. Many other bounds on the Wiener index are also established in the literature.
In [4] Gutman and Yeh proposed the inverse Wiener index problem, i.e. for a given value w the problem of finding a graph (or a tree) G for which W(G) = w. The first attempt at solving the problem was made in [7] where integers up to 1206 were checked and 49 integers were found that are not Wiener indices of trees. In [1] it was computationally proved that for all integers w between 103 and 108 there exists a tree with Wiener index w. The problem was finally fully solved in 2006 when two papers were published solving the problem independently. It was proved in [12] that for every integer w > 108 there is a caterpillar tree G such that W(G) = w. The other proof is from the paper [9] where it was proved that all integers except those 49 are Wiener indices of trees with diameter at most 4. Since the most interesting graphs to be considered are chemical trees (especially those in which maximum vertex degree is at most 3) and hexagon type graphs, in [11] this problem was further considered on classes of such graphs.
A related question is to ask what value of the Wiener index can a graph (or a tree) G on n vertices have? In order to clarify further this problem one may also ask how many such values are there, how are they distributed along the related interval or how many of them are consecutive. In [6] this problem is named the Wiener inverse interval problem (see also a nice recent survey [5] which covers the topic). In that paper the set W[Gf] is defined as the set of all values of the Wiener index for graphs G G Gf, where Gn is the class of simple connected graphs on n vertices. Similarly, W[7f] is defined as the set of values W(T) for all trees on n vertices (7f denotes the class of trees on n vertices). Also, Wmi[G„] (or analogously Wint [7f ]) is defined to be the largest interval of consecutive integers such that Wint[Gn] C W[Gn] (or analogously Wint[7f] C W[7f]).
In [6] the Wiener inverse interval problem on the class Gn was considered. First, the authors noted that obviously Wifi[£„] C W[£„] C [W(K„), W(P„)]. Since W(K„) and W(P„) are easily computed, the upper bound | Wifi[£„] | < |W[£„] | < f- - fr + f + 1 easily follows. Introducing dandelion and comet graphs and establishing how the values between the values of the Wiener index for dandelion a| nd comet |graph can be obtained, the authors obtain the following lower bound |W[£„]| > |Wifi[£„]| > f- - §n2 - ±n3/2 + 19n + 3n1/2. These bounds sandwich the value of | Wmi[£„] | and |W[Gf]| in terms of n3 tightly, therefore the result |Wift[Gf]| = |Wift[Gf]| = f- + O(n2) easily follows. The authors further conjecture that |W[Gf]| = f— fir + ©(n). Regarding the same problem on the class 7f the following two conjectures were made.
Conjecture 1.1. The cardinality of W[7f ] equals 1 n3 + ©(n2).
Conjecture 1.2. The cardinality of Wmi[7f ] equals ©(n3).
In this paper we will consider these two conjectures. First, we will note that for a tree T on odd number of vertices n the value W (T) can be only an even number. That means that the Wiener inverse interval problem in that case has to be reformulated as the problem of finding the largest interval Wmi[7f] of consecutive even integers such that
1^,3 m2 , 11„
Wini[T„] c W[Tn]. Since |W[T„]| < W(P„) - W(S„) + 1 = 6n3 - n2 + n, we now conclude that the cardinality of W[7n] in the case of odd n can be at most 12n3 + O(n2). Given that reformulation, we will prove both conjectures to be true in terms of n3. Even
more, we will prove the strongest possible version of Conjecture 1.2 in terms of n3 by
6n3 + O(n5/2) (i.e. ^?
proving that |Wmi[7f]| also equals 6n3 + O(n5/2) (i.e. 12n3 + O(n5/2) in case of odd
J. Sedlar: On Wiener inverse interval problem of trees
21
n) which is the best possible result given the upper bound on |W[7^]| derived from the difference between W(Pn) and W(Sn). These results will yield quite a strong result for the class Trf of chemical trees as a direct corollary.
The present paper is organized as follows. In the next section basic definitions and preliminary results are given. In the third section the problem is solved for trees on even number of vertices, while in the fourth section the problem is solved for trees on odd number of vertices. In the fifth section we conclude the paper with several remarks and possible directions for further research.
2 Preliminaries
Let G = (V(G),E(G)) be a simple connected graph having n = |V(G)| vertices and m = |E(G)| edges. For a pair of vertices u, v e V(G) we define the distance dG(u, v) as the length of the shortest path connecting u and v in G. For a vertex u e V (G) the degree dG(u) is defined as the number of neighbors of vertex u in graph G. When it doesn't lead to confusion we will use the abbreviated notation d(u, v) and d(u). Also, for a vertex u e V(G) and a set of vertices A C V(G) we will denote d(u, A) = J2veA d(u, v). Similarly, for two sets of vertices A, B C V(G) we will denote d(A, B) = ueA v£B d(u, v). We say that a vertex u e V(G) is a leaf if dG(u) = 1, otherwise we will say that u is an interior vertex of a graph G. A graph G which does not contain cycles is called a tree. A tree graph will usually be denoted by T throughout the rest of the paper. We say that a tree T is a caterpillar tree if all its interior vertices induce a path. Such a path will be called the interior path of a caterpillar. Let a and b be positive integers such that a < b. We say that the interval [a, b] is Wiener p-complete if there is a tree T in Tn such that W(T) = a + pi for every i = 0,...,	. We say that the interval [a, b] is Wiener complete if it is Wiener
1 - complete.
Let us now note that the value of the Wiener index for a tree T on odd number of vertices n is an even number. There are various ways to prove this fact, maybe the simplest one is to recall that for a tree T on n vertices it holds that
W (T) = ^ n„ • nv
uveE(T)
where nu and nv are the number of vertices in the connected component of T\{uv} containing u and v respectively. Obviously, nu + nv = n and therefore in the case of odd n the product nu • nv must be an even number. I would like here to thank prof. Tomislav Doslic for suggesting this short proof to me and to the anonymous reviewers for referring me to the interesting survey [2] in which this fact is already explained and to several interesting papers ([3], [8] and [10]) in which one can read more on the subject. Before proceeding further, let us state this fact as a formal theorem which we can reference in further text.
Theorem 2.1. Let T be a tree on odd number of vertices n > 3. Then W(T) is an even number.
The main tool for obtaining our results throughout the paper will be a transformation of a tree which increases the value of the Wiener index by exactly four. We will call it Transformation A, but let us introduce its formal definition.
Definition 2.2. Let T be a tree and u e V(T) a vertex of degree 4 such that neighbors vi and v2 of u are leaves, while neighbors w1 and w2 of u are not leaves. We say that a tree
22
Ars Math. Contemp. 15 (2018) 39-51
T' is obtained from T by Transformation A if T' is obtained from T by deleting edges uv1 and uv2, while adding edges w1v1 and w2v2.
Theorem 2.3. Let T be a tree and let T' be a tree obtained from T by Transformation A. Then W(T') = W(T) + 4.
Proof. For simplicity's sake we will use the notation d'(u,v) for dT> (u,v). Let TWi = (VWi ,EWi) be the connected component of T\{u} which contains vertex wi for i = 1, 2. Note that the only distances that change in Transformation A are distances from vertices v1 and v2. For every v G VW1 U VW2 we have
d'(vi, v) — d(vi, v) + d/(v2, v) — d(v2, v) = 0.
For the vertex u we have
d'(vi, u) — d(vi, u) + d'(v2, u) — d(v2, u) = 2.
Finally, we also have d'(v1,v2) — d(v1,v2) = 2. Therefore, W(T') — W(T) = 4 which proves the theorem.	□
Although Transformation A can be applied on any tree graph, we will mainly apply it on caterpillar trees. Moreover, it is critical to find a kind of caterpillar tree on which Transformation A can be applied repeatedly as many times as possible. For that purpose, let us prove the following theorem.
Theorem 2.4. Let T be a caterpillar tree and P = u1.. .ud its interior path. If there is a vertex ui G P of degree 4 such that ui±j is of degree 3 for every 1 < j < k — 1, then the interval [W(T), W(T) + 4k2] is Wiener 4—complete.
Proof. Let us denote a caterpillar tree T from the statement of the lemma by Tk (since 1 < j < k — 1). Also, let us denote D = {ui±j : j = 0,... ,k — 1}. To obtain the desired result we will systematically apply Transformation A to vertices from D until there is no more vertices in D to which Transformation A can be applied. Let us now explain into greater detail by what system that is done. First, note that in Tk Transformation A can initially be applied only to ui. By applying transformation A to ui in Tk we will obtain a caterpillar tree in which Transformation A can be applied to vertices ui-1 and ui+1. By applying Transformation A to ui-1 and ui+1 consecutively we will obtain a caterpillar tree in which Transformation A can be applied to ui-2 and ui+2 (and ui but we will not further apply Transformation A to that vertex for the time being). By further applying transformation A to ui-2 and ui+2 consecutively and repeating this procedure we will reach a caterpillar tree in which Transformation A can be applied to vertices ui-(k-1) and ui+(k-1) and finally apply Transformation A to those two vertices. The caterpillar tree obtained after that last step we can denote by Tk-1 because of the following: in that tree vertex ui g P is of degree 4 and vertices ui±j are of degree 3 for every j = 1,... ,k — 2. Note that in the process of transforming Tk to Tk-1 we will have applied the Transformation A 2k — 1 times. Now, the same process can be repeated on Tk-1 to obtain Tk-2. The procedure stops when we reach T1 in which ui is the only vertex in D having degree greater than 2 (to be more precise, the degree of ui in T1 equals 4, so Transformation A can be applied to it one more time). Applying Transformation A on ui in T1 we finally obtain T0 in which Transformation A cannot be further applied to vertices from D. Therefore, in transforming Tk to T0 Transformation A was used J2j=1(2j — 1) = k2 times and each time the value of the Wiener index increased by 4.	□
J. Sedlar: On Wiener inverse interval problem of trees
23
Note that the Transformation A in Theorem 2.4 is applied k2 times on a caterpillar in which interior path is of length d - 1. If we prove that there are ©(n) different values of d for which k = ©(n), we obtain roughly ©(n3) graphs with different values of the Wiener index which is exactly the result we aim at (of course, here one has to be careful to avoid significant overlapping of the values of the Wiener index for caterpillars with different values of d). So, that is what we are going to do in following sections, but in order to do that with sufficient mathematical precision we will have to construct four different special types of caterpillar trees. To easily construct those four types of caterpillar trees we first introduce two basic types of caterpillars from which those four types will be constructed by adding one or two vertices.
Definition 2.5. Let n, d and x be positive integers such that n > 18 is even, r^i < d < and x < 4+42d-n. Caterpillar Bi(n, d, x) is a caterpillar on even number of vertices n obtained from path P = u_d ... m_1m0u1 ... ud by appending a leaf to vertices u_d_1+x and ud+1-x and by appending a leaf to 2k - 1 consecutive vertices u_(k-1),..., uk-1
where k = —2 '—.
Caterpillar graph B1 (n, d, x) is illustrated by Figure 1 (vertex u of the interior path is in the images denoted just by i in order to make labels easier to see).
Figure 1: Caterpillar graphs: a) B1(20,6, 2), b) B1(20,5,1).
Lemma 2.6. Let n, d and x be integers such that B1 (n, d, x) is defined. Then
n3	oj 5	13
W(B1(n,d,x)) = — + (-y - 5)n2 + (4d2 + 10d + y - 2x)n+
2 8 ,o ,2 46d
+ 2x2 — d3 - 12d2---7.
3	3
Proof. Let k = "_(2d+1)_1 and x' = -d - 1 + x. Even though the structure of B1 is a bit complicated it is still regular enough so that the Wiener index can be computed exactly (as a function in variables n, d and x). Let us divide vertices of B1 into three sets A, B and C so that set A contains vertices u for i = - d,..., d, set B contains leaves attached to 2k - 1 consecutive vertices u_(k_1),..., uk_1 and set C contains two leaves attached to
24
Ars Math. Contemp. 15 (2018) 39-51
vertices u_d_1+x and ud+1_x. Note that we have
d d k_1 k_1 d(A,A) = ££ (j - i),d(B,B)= £ £ (j - i + 2)
i=_dj=i+1 i=_(k_1) j=i+1
d fc_1
d(C,C) = (2d +2 - 2(x - 1)),d(A,B) = £ £ (|i - j| + 1)
i=_dj=_(k_1) d fc_1 d(A,C) = 2 £ (|i - x'| + 1),d(B,C) = 2 £ (|i - x'| +2)
i=_d i=_(k_1)
Noting that
W(B1 (n, d,x)) = d(A, A) + d(B, B) + d(C, C) + d(A, B) + d(A, C) + d(B, C) and simplifying the obtained sum yields the formula from the statement of the lemma. □
Note that the caterpillar B1(n, d, x) is a caterpillar with relatively long interior path. Namely, the value d is roughly half of the length of the interior path and in the definition of B1 (n, d, x) the value of d is relatively large with respect to number of vertices n. We now introduce the formal definition of the second basic caterpillar which will have relatively short interior path.
Definition 2.7. Let n, d and x be positive integers such that n > 18 is even, 4 < d < [^J and x < "_42d+2. Caterpillar B2 (n, d, x) is a caterpillar on even number of vertices n obtained from path P = u_d ... u_1u0u1.. .ud by appending a leaf to 2k - 1 consecutive vertices u_(k_1),..., uk_1 where k = d -1, by appending x leaves to each of the u_(d_1) and u(d_1), and by appending r leaves to each of the u_d and ud where r = "_4d_2x+2.
Caterpillar graph B2 (n, d, x) is illustrated by Figure 2 (vertex ui of the interior path is in the images denoted just by i in order to make labels easier to see).
^ muiiiv b) mu iij.
Figure 2: Caterpillar graphs: a) B2(20,4,1), b) B2(20,4, 3).
Lemma 2.8. Let n, d and x be integers such that B2 (n, d, x) is defined. Then
d	8d3 32d
W(B2(n, d,x)) = (^ + 1)n2 + (-2d - 2)n - — + — - 5 + 8x - 8dx - 2x2.
Proof. Let k = d -1 and r = "_4d^2x+2. To obtain the exact formula for W(B2(n,d,x)) we divide vertices from B2(n,d,x) into four sets: set A contains vertices ui for i =
J. Sedlar: On Wiener inverse interval problem of trees
25
—d,..., d, set B contains leaves appended to 2k-1 consecutive vertices u_(fc_i),..., set C contains x leaves appended to each of the M_(d-1) and u(d_1), while finally set D contains r leaves appended to each of the u_d and ud. Note that
d d k_1 k_1 d(A,A) = g g (j — i), d(B,B)= g g (j — i + 2)+
i=_dj=i+1 i= — ( k — 1) j=i+1
d(C,C) =4(2) + x2(2d), d(D,D) =4(2) + r2(2d +2) Also, we have
d k_1 2d+1 d(A,B) = g g (|i — j| + 1), d(A,C)=2x(3 + g (i — 1))
i=_dj = _(k_1)	i=3
2d+1 k_1 d(A,D) = 2r g i, d(B,C) = 2x g (i + d + 1)
i=1 i=_(k_1) k_1
d(B,D) = 2r g (i + d +2), d(C,D) = 2(3xr + xr(2d + 1)).
i=_(k_1)
Noting that
W(B1(n, d, x)) = d(A, A) + d(B, B) + d(C, C) + d(D, D)+ + d(A, B) + d(A, C) + d(A, D)+ + d(B, C) + d(B, D) + d(C, D)
and simplifying the obtained sum yields the formula from the statement of the lemma. □
Finally, let us denote df" = [ 2 ] and xf^ = 4+4d:2'"_", while difax = [ f J . Note that
B1(n,dmin,xmax) = B2(n,dfax, 1).	(2.1)
This equality will provide us with a nice transition from caterpillars based on B1(n, d, x) to caterpillars based on B2(n, d, x) in the following sections.
3 Even number of vertices
In this section we will first introduce a special kind of caterpillar based on B1(n, d, x) which will have a longer interior path, then we will introduce a second special kind of caterpillar based on B2 (n, d, x) which will have a shorter interior path. For each of those two special kinds of caterpillars we will establish a bound on the value of d for which the interval between values of the Wiener index for two consecutive values of x and d is Wiener 4—complete. The equality (2.1) will then enable us to "glue" all those intervals into one big Wiener 4—complete interval.
Definition 3.1. Let n, d and x be integers for which B1(n — 2, d, x) is defined. For s = — 1,0,1, 2 caterpillar T1 (n, d, x, s) is a caterpillar on even number of vertices n, obtained from B1 (n — 2, d, x) by appending a leaf to the vertex us and a leaf to the vertex ud of the
path P = u_d ... u_1u0U1 ... Ud in B1(n — 2, d, x).
26
Ars Math. Contemp. 15 (2018) 39-51
a)
b)
Figure 3: Caterpillar graphs: a) ^(22,6,2,0), b) Ti(22,6, 2, 2).
Caterpillar graph T1(n, d, x, s) is illustrated by Figure 3 (vertex ui of the path P is in the images denoted just by i in order to make labels easier to see).
Lemma 3.2. Let n, d, x and s be integers for which T1 (n, d, x, s) is defined. Then
n2
W(T1(n,d,x,s)) = W(B1(n - 2,d,x)) + — + — + 2d2 + 3d + 2s2 - s - 2x.
Proof. Let k = ("-2)-(22d+1)-1, x' = -d - 1 + x. We define a function
d k-1 f(v)= E (|v - i| + 1)+ E (|v - i| +2)+
i=-d i= — (k — 1)
(|x' - v | + 2+ | —x' - v | +2) Now, the definition of T1(n,d,x, s) implies
W(T1(n, d, x,s)) = W(B1(n - 2, d, x)) + f (s) + f (d) + d - s + 2.
Plugging s and d into the formula for f and simplifying the obtained expression yields the result.	□
As a direct consequence of Lemma 3.2 we obtain the following corollary.
Corollary 3.3. It holds that
W(T1(n, d, x, 1)) = W(T1(n, d,x, 0)) + 1, W(T1(n, d, x, 2)) = W(T1(n, d, x, 0)) + 6, W(T1(n, d, x, -1)) = W(T1(n, d, x, 0)) + 3.
The main tool in proving the results will be Transformation A of the graph, which, for a given graph, finds another graph whose value of the Wiener index is greater by 4. Therefore, it is critical to find a graph on which Transformation A can be applied consecutively as many times as possible. That was the basic idea behind constructing graph T1(n, d, x, s) as we did, so that we can use Theorem 2.4 in filling the interval between values W(T1(n, d, x, s)) for consecutive values of x and d. So, let us first apply Theorem 2.4 (i.e. find the corresponding value of k) to the graph T1(n, d, x, s).
Lemma 3.4. Let n, d, x and s be integers for which T1(n, d, x, s) is defined. For k = 1 n -d-4 the interval [W(T1(n, d, x, s)), W(T1(n, d, x, s)) + 4k2] is Wiener 4-complete.
J. Sedlar: On Wiener inverse interval problem of trees
27
Proof. Let us denote ki = (n-2)-(22d+1)-1. Note that ki is half of the number of leaves appended to the vertices u±j of the interior path of T1(n, d, x, s) for j = 0,..., k - 1. Since s < 2, note that the definition of T1(n, d, x, s) and Theorem 2.4 imply the result for
k = k1 - 2. □
So, let us now establish for which values of d the gap between W(T1(n, d, x, s)) and W(T1(n, d, x — 1, s)) is smaller than 4k2 which is the width of an interval which can be filled by repeatedly applying Transformation A on T1 (n, d, x, s) (i.e. by using Lemma 3.4).
Lemma 3.5. Let n, d, x > 2 and s be integers for which T1(n, d, x, s) is defined. For d < 2 (n — a/2n — 8 — 8) the interval
[W(T1(n, d, x, s)), W(T1(n, d, x — 1, s))]
is Wiener 4—complete. Proof. First note that
W(T1(n,d,x — 1,s)) — W(T1(n,d,x,s)) < W(T1(n,d, 2,s)) — W(T1(n,d, 1,s)) =
= 2(n — 5)+ 2.
Therefore, Lemma 3.4 implies it is sufficient to find integers n and d for which it holds that 4k2 > 2(n — 5) + 2 where k = 1 n — d — 4. By a simple calculation it is easy to establish that the inequality holds for d < 1 (n — a/2n — 8 — 8) so the lemma is proved.	□
It is easy to show, using Lemma 3.2, that W(T1 (n, d, x — 1, s)) — W(T1 (n, d, x, s)) = 2n — 4x which is divisible by 4 since n is even. Therefore, Lemma 3.5 enables us to "glue" together Wiener 4—complete intervals
[W(T1(n, d, x, s)), W(T1(n, d, x — 1, s))]
into one bigger Wiener 4—complete interval
[W(T1 (n, d, xmax, s)), W(T\(n, d, 1, s))]
where x5"ax = 4+4d-("-2). Corollary 3.3 then implies that roughly the same interval will be Wiener complete when we take values for every s = —1,0,1,2. We say "roughly" because the difference W(T1(n, d, x, 2)) = W(T1(n, d, x, 0)) + 6 makes one point gap at W(T1 (n, d, xmax, 0)) + 2. We now want to "glue" together such bigger intervals into one interval on the border between d and d — 1 . The problem is that
T1(n, d, x5"ax,s) = T1(n,d — 1,1,s),
so we have to cover the gap in between. Moreover, it holds that
W(T1(n, d, x5"ax,s)) — W(T1(n,d — 1,1,s)) = n — 3
which is not divisible by 4. Therefore, we have to find enough graphs whose values of the Wiener index will cover the gap of n — 3 plus the gap of 6 which arises from the "rough" edge of the interval for a given d.
28
Ars Math. Contemp. 15 (2018) 39-51
Lemma 3.6. Let n, d, xjiax = 4+4d 2(" 2) and s be integers for which T1(n, d, x™3*, s) and T1 (n, d — 1,1, s) are defined. For d < 2 (n — %/n + 3 — 6) the interval
[W(T1(n, d — 1,1, s)), W(T1(n, d, x1^, s)) + 6]
is Wiener 4—complete.
Proof. Since
W(T1(n, d, x5"ax, s)) + 6 — W(T1(n, d — 1,1, s)) = n — 3 + 6 = n + 3,
Lemma 3.4 implies that it is sufficient to find for which d it holds that 4k2 > n + 3 where k = 1 n — (d — 1) — 4. By a simple calculation one obtains that inequality holds for
d < 1 (n — a/n + 3 — 6) which proves the theorem.	□
Note that the restriction on the maximum value of d is stricter in Lemma 3.5 then in Lemma 3.6 for every n > 4.
Now we have taken out all we could from graph T\, but that covers only caterpillars with relatively large d. We can further expand the Wiener complete interval to the left side, i.e. to caterpillars with smaller d, using graph T2 which we will construct from the basic graph B.
Definition 3.7. Let n, d and x be integers for which B2(n — 2, d, x) is defined. For s = — 1,0,1, 2 caterpillar T2 (n, d, x, s) is a caterpillar on even number of vertices n, obtained from B2 (n — 2, d, x) by appending a leaf to the vertex us and a leaf to the vertex ud of the path P = u_d ... u_1UoU1 ... ud in B2(n — 2, d, x).
Caterpillar graph T2 (n, d, x, s) is illustrated by Figure 4 (vertex u of the path P is in the images denoted just by i in order to make labels easier to see).
a)	MI I If!
b)	.Yuiym
Figure 4: Caterpillar graphs: a) T2(22,4,3, —1), b) T2(22,4, 3,1).
Lemma 3.8. Let n, d, x and s be integers for which T2 (n, d, x, s) is defined. Then W(T2(n, d,x, s)) = W(B2(n — 2,d,x)) + (2d + 4)n — 2d2 — 7d — 6 — 2x + 2s2 — s Proof. Let k = d — 1 and r = "-4d-2x. We define a function
d k-1 f(v)= E (|v — i| + 1)+ E (|v — i| + 2) +
i=-d i=-(k-1)
+ x(|v + (d — 1)| + 2) + x(|v — (d — 1)| + 2)+ + r(|v + d| + 2) + r(|v — d| +2).
J. Sedlar: On Wiener inverse interval problem of trees
29
Now, the definition of T2 (n, d, x, s) implies
W(T2(n, d, x, s)) = W(B2(n - 2, d, x)) + f (s) + f (d) + d - s + 2.
Plugging s and d into the formula for f and simplifying the obtained expression yields the result.	□
Again, as a direct consequence of Lemma 3.8 we obtain the following corollary. Corollary 3.9. It holds that
W(T2(n, d, x, 1)) = W(T2(n, d, x, 0)) + 1, W(T2(n, d, x, 2)) = W(T2(n, d, x, 0)) + 6, W(T2(n, d, x, -1)) = W(T2(n, d, x, 0)) + 3.
As in the case of large d, the main tool in obtaining the results will be the following lemma.
Lemma 3.10. Let n, d, x and s be integers for which T2(n, d, x, s) is defined. For k = d—3 the interval [W(T2(n, d, x, s)), W(T2(n, d, x, s)) + 4k2] is Wiener 4—complete.
Proof. Let us denote ki = d - 1. Note that ki is half of the number of leaves appended to the vertices of the interior path of T2 (n, d, x, s) for j = 0,..., k -1. Since s < 2, note that the definition of T2 (n, d, x, s) and Theorem 2.4 imply the result for k = k1 - 2. □
We will first use Lemma 3.10 to cover the interval between W(T2(n, d, x, s)) and
W(T2(n, d, x - 1, s)), after that we will use it to cover the gap between W(T2(n, d -1,1,s)) and W(T2(n, d,x;fax, s)).
Lemma 3.11. Let n, d, x > 2 and s be integers for which T2(n, d, x, s) is defined. For d > 1 (V2 n - 8 + 6) the interval
[W(T2(n, d, x, s)), W(T2(n, d, x - 1, s))]
is Wiener 4-complete.
Proof. First note that for xmax = ("-2)-4d+2 it holds that
W(T2(n,d,x - 1,s)) - W(T2(n,d,x,s)) < < W(T2 (n, d, xipax - 1,s)) - W(T2(n,d,xmax,s)) = = 2(n - 5) + 2.
Therefore, Lemma 3.10 implies it is sufficient to find for which n and d it holds that 4k2 > 2(n - 5) + 2 where k = d - 3. By a simple calculation it is easy to establish that the inequality holds for d > 2 (%/2n - 8 + 6) so the theorem is proved.	□
Again, it is easy to show that W(T2(n, d, x - 1, s)) - W(T2(n, d, x, s)) = 4d + 4x - 8 which is divisible by 4. Therefore, using Lemma 3.11 we can again "glue" the interval for different values of x into one bigger interval which will be "roughly" Wiener complete when taking values of W(T2(n, d, x, s)) for every s = -1,0,1,2. The next thing is to cover the gap between W(T2(n, d - 1,1, s)) and W(T2(n, d, xmax, s)) which equals n - 3 plus the gap of 6 which arises from the "rough" ends of the Wiener complete interval for given n and d.
30
Ars Math. Contemp. 15 (2018) 39-51
Lemma 3.12. Let n, d, x™3* = (n 2)2 4d+2 and s be integers for which T2(n, d, x™3*, s) and T2 (n, d — 1,1, s) is defined. For d > 2 (%/n + 3 + 8) the interval
[W(T2(n, d — 1,1, s)), W(T2(n, d, x?ax, s)) + 6]
is Wiener 4—complete.
Proof. Since
W(T2(n, d, x^, s)) + 6 — W(T2(n, d — 1,1, s)) = n + 3,
Lemma 3.10 implies it is sufficient to find n and d for which it holds that 4k2 > n + 3 where k = (d — 1) — 3. By a simple calculation one obtains that the inequality holds for
d > 1 (%/n + 3 + 8) which proves the theorem.	□
Therefore, using graphs l\(n, d, x, s) and T2(n, d, x, s) we obtained two big Wiener complete intervals, which it would be nice if we could "glue" together into one big Wiener complete interval. In order to do that, note that the equality (2.1) implies
T2(n, d?ax, 1, s) = Ti (n, df", x5"ax, s)
for d?ax = [n42J, dfin = I"nf4] and xf8* = 4+4d°'"2-(n-2). Now we can state the theorem which gives us the largest Wiener complete interval we have managed to obtain.
Theorem 3.13. Let n > 30, d?in = 11 (V2n — 8 + 6)] , x?ax = (n-2)-24d°'"+2 and di"ax = L1 (n — V2n — 8 — 8)J . The interval
[W(T2(n, df", x?8*, 2)), W(Ti(n, d?^, 1,0))]
is Wiener complete.
Now that we have obtained very large Wiener complete interval, we can finally prove the following theorem which is our main result and which proves Conjectures 1.1 and 1.2 in terms of n3.
Theorem 3.14. For even n > 30 it holds that \ Wint[7n] | = |W[7^] | = 1 n3 + O(n5/2). Proof. Theorem 3.13 implies
|W[Tn]| > \Wini[rn]\ > W(T1(n,d5nax, 1, 0)) — W(T2(n,dlnin,xmnax, 2))
wherediT" = 2(V2n — 8 + 6)+ p, x?^ = (n-2)-24d°'"+2 anddfax = 1 (n — V2n — 8 — 8) — 1 + q for p G [0,1} and q G (0,1]. From Lemmas 3.2 and 3.8 we further obtain that
\Wint[Tn]\ > 1 n3 — 1 \/2n5 — 8n4 — 4n2 + 10v/2n3 — 8n2 + ^n + 21^2n — 8 — 51. 6 2	3	6
On the other hand, recall that \Wint[7n]\ < |W[7n]| < W(Pn) — W(Sn) + 1 = 1 n3 — n2 + 11 n, which proves the theorem.	□
J. Sedlar: On Wiener inverse interval problem of trees
31
Note that caterpillar trees Ti(n, d, x, s) are chemical trees (i.e. trees in which the degree of every vertex is at most 4) for all possible values of its parameters and they remain chemical after repeated application of Transformation A. Therefore, half of these results hold for chemical trees and we obtain the following corollary.
Corollary 3.15. Let Tn be a class of chemical trees on n vertices where n > 30 is even. Then |Wini[T„4]| = |W[T4]| = ©(n3).
Proof. Note that Lemmas 3.5 and 3.6 imply that
|W[T4]1 > |Wint[T44]1 > W(Ti(n, d5"ax, 1, 0)) - W(Ti(n,dmin,xmax, 2))
where dfax = 2(n - V2n - 8 - 8) - 1 + p, dfin = "f2 + q and xfax = 6+4dj°for p € (0,1] and q € [0,1}. From Lemma 3.2 we obtain
|Wint[T4]| > 1 n3-1 V2n5 - 8n4-15n2 + 5^2n3 - 8n2+^-n+9^2^-8-134.
12 4	8 3	12 2	3
Note that this result for chemical trees is obtained using only chemical trees with relatively large diameter and the result is still the best possible with regard to the highest power n3 (just the power, not the coefficient). This means that this result is something that probably can be significantly improved by considering chemical trees with shorter diameter, but we leave that as an open problem for future research.
4 Odd number of vertices
The strategy to prove the result in the case of odd number of vertices is the same as in the case of even number of vertices. The only difference is that in this case the value of the Wiener index can be only even number so we are aiming at the largest possible interval of consecutive even numbers which are values of the Wiener index for a tree.
Definition 4.1. Let n, d and x be integers for which Bi(n - 1, d, x) is defined. For s = 0,1 caterpillar T3(n, d, x, s) is a caterpillar on odd number of vertices n, obtained from
Bi (n-1, d, x) by appending a leaf to the vertex us of the path P = u-d ... w_iM0ui... ud in Bi(n - 1, d, x).
Caterpillar tree T3 (n, d, x, s) is illustrated by Figure 5 (vertex u of the path P is in the images denoted just by i in order to make labels easier to see).
Figure 5: Caterpillar graphs: a) T3(21,6,2,0), b) T3(21,6,2,1).
32
Ars Math. Contemp. 15 (2018) 39-51
Lemma 4.2. Let n, d, x and s be integers for which T3(n, d, x, s) is defined. Then
n2	H
W(T3(n, d,x, s)) = W(B1(n - 1,d,x)) + — - dn + 2d2 + 5d + — - 2x + 2s2.
Proof. Let k = ("-1)-(22d+1)-1, x' = —d - 1 + x. The definition of T3(n, d, x, s) implies
d
W(Ts(n, d, x, s)) = W(Bi(n - 1, d, x)) + ^ (|s - i| + 1)+
i=-d
k-1
+ ^ (|s - i\ + 2) + (s - x' + 2) + i=-(k-1) + (-x' - s + 2).
Simplifying this expression yields the result.	□
As a direct consequence of Lemma 4.2 we obtain the following corollary.
Corollary 4.3. It holds that W(T3(n, d, x, 1)) = W(T3(n, d, x, 0)) + 2.
We now want to apply Theorem 2.4 to T3(n, d, x, s), i.e. we want to establish the value of k in the case of this special graph.
Lemma 4.4. Let n, d, x and s be integers for which T3(n, d, x, s) is defined. For k = 2n-d- 5 the interval [W(T3(n, d,x,s)), W(T3(n, d, x, s))+4k2] is Wiener 4-complete.
Proof. Let us denote k1 = ("-1)-(22d+1)-1. Note that k1 is half of the number of leaves appended to the vertices u±j of the interior path of T3(n, d,x,s) for j = 0,... ,k - 1. Since s < 1, note that the definition of T3(n, d, x, s) and Theorem 2.4 imply the result for
k = k1 - 1. □
So, let us now establish for which values of d the gap between W(T3(n, d, x, s)) and
W(T3(n, d,x - 1, s)) is smaller than 4k2 where k = 2n - d - |.
Lemma 4.5. Let n,d, x > 2 and s be integers for which T3(n, d, x, s) is defined. For d < 2 (n -%/2n - 6 - 5) the interval
[W(T3(n, d, x, s)), W(T3(n, d,x - 1, s))]
is Wiener 4-complete. Proof. First note that
T3(n, d,x - 1, s) - T3(n, d, x, s) < T3(n, d, 2, s) - T3(n, d, 1, s) =
= 2(n - 4)+ 2.
Therefore, Lemma 4.4 implies it is sufficient to find integers n and d for which it holds that 4k2 > 2(n - 4) + 2 where k = 1 n - d - |. By a simple calculation it is easy to establish that the inequality holds for d < 1 (n - sj2n - 6 - 5) so the lemma is proved.	□
J. Sedlar: On Wiener inverse interval problem of trees
33
Using Lemma 4.2 it is easy to establish that
W(T3(n, d,x - 1,s)) - W(T3(n,d,x,s)) = 2(n - 2x + 1)
which is divisible by 4 since n is odd. Moreover, note that for xmax = 4+4d-("-1) it holds that
T3(n, d, x^ax, s) = T3(n, d - 1,1, s).
Therefore we can use Lemma 4.5 and "glue" together intervals both on the border between x and x - 1 and on the border of d and d - 1, so we will obtain one large interval which is Wiener 2-complete (because of Corollary 4.3).
Again, here we have used T3(n, d, x, s) to the maximum, but we have covered thus only caterpillars with large d. Let us now use graph B2 (n, d, x) to create the fourth special kind of caterpillars which we will use to widen our interval to caterpillars with small d.
Definition 4.6. Let n, d and x be integers for which B2(n - 1, d, x) is defined. For s = 0,1 caterpillar T4(n, d, x, s) is a caterpillar on odd number of vertices n, obtained from
B2 (n-1, d, x) by appending a leaf to the vertex us of the path P = u-d ... m_1m0u1 ... ud in B2(n - 1, d, x).
Caterpillar graph T3(n, d, x, s) is illustrated by Figure 6 (vertex u of the path P is in the images denoted just by i in order to make labels easier to see).
^ :vny i ij. b) muzm
Figure 6: Caterpillar graphs: a) T4(21,4,3,0), b) T4(21,4,3,1).
Lemma 4.7. Let n, d, x and s be integers for which T4(n, d, x, s) is defined. Then W(T4(n,d,x,s)) = W(B2(n - 1,d,x)) + (2 + d)n - 2d2 - 3d - 1 + 2s2 - 2x.
Proof. Let k = d - 1 and r = (n-1)-4d-2x+2. The definition of T4(n, d, x, s) implies
d
W(T4(n, d, x, s)) = W(B2(n - 1,d,x)) + ^ (|s - i| + 1) +
i=-d
k-1
+ ^ (|s - i| + 2) + (s - x' + 2)+ ¿=-(fc-1) + 2x(d +1) + 2r(d +2).
Simplifying this expression yields the result.	□
Corollary 4.8. It holds that W(T4(n, d, x, 1)) = W(T4(n, d, x, 0)) + 2.
34
Ars Math. Contemp. 15 (2018) 39-51
Let us now apply Theorem 2.4 to T4(n, d, x, s).
Lemma 4.9. Let n, d, x and s be integers for which T4 (n, d, x, s) is defined. For k = d — 2 the interval [W(T4(n, d, x, s)), W(T4(n, d, x, s)) + 4k2] is Wiener 4—complete.
Proof. Let us denote k1 = d — 1. Note that k1 is half of the number of leaves appended to the vertices u± j of the interior path of T3 (n, d, x, s) for j = 0,..., k — 1. Since s < 1, note that the definition of T4(n, d, x, s) and Theorem 2.4 imply the result for k = k1 — 1. □
Now we can establish the minimum value of d for which the difference between Wiener index of T4(n, d, x, s) and T4(n, d, x — 1, s) can be "covered" by Transformation A.
Lemma 4.10. Let n, d, x > 2 and s be integers for which T4(n, d, x, s) is defined. For d > 2(V2 n — 6 + 4) the interval
[W(T4(n, d, x, s)), W(T4(n, d, x — 1, s))]
is Wiener 4—complete.
Proof. First note that for xfax = ("_1)2_4d+2 it holds that
W(T4(n, d, x — 1,s)) — W(T4(n, d,x, s)) < W(T4(n, d,xfax — 1,s)) — W(T4(n, d,xfax, s)) = = 2(n — 4)+ 2.
Therefore, Lemma 4.9 implies it is sufficient to find integers n and d for which it holds that 4k2 > 2(n — 4) + 2 where k = d — 2. By a simple calculation it is easy to establish that the inequality holds for d > 2 (%/2n — 6 + 4) so the lemma is proved.	□
Using Lemma 4.7 it is easy to establish that
W(T4(n, d,x — 1,s)) — W(T4(n,d,x,s)) = 4(x + 2d — 2) which is divisible by 4. Moreover, note that for xmax = ("_1)—4d+2 it holds that
T4(n, d, xfax, s) = T4(n, d — 1,1, s).
Therefore we can use Lemma 4.10 and "glue" together intervals both on the border between x and x — 1 and on the border of d and d — 1, so we will obtain one large interval which is Wiener 2—complete (because of Corollary 4.8).
Finally, noting that for dfin = [], xfax = 4+4d°'"2_("_1) and dfax = 1J it holds that
T3(n, dfin, xfax, s) = T4(n, dfax, 1, s),
we conclude that we can "glue" together two large Wiener 2—complete intervals we obtained (one for large values of d and the other for small values of d), and thus we obtain the following theorem which gives us the largest Wiener 2—complete interval we manage to obtain.
J. Sedlar: On Wiener inverse interval problem of trees
35
Theorem 4.11. Let n > 21, d= [1 (n - V2n - 6 - 5)J, d^" = [2 (V2n - 6 + 4)] and x4max =	—+2. The interval
[W (T4(n,d4in,x4ax, 1)),W (T3(n,d4ax, 1,0))] is Wiener 2—complete.
Having the largest Wiener 2-complete interval from the previous theorem, we can now finally prove the following theorem which is our main result and which proves Conjectures 1.1 and 1.2 in terms of n3.
Theorem 4.12. For odd n > 21 it holds that |Wini[7"]| = |W[7"]| = 12n3 + O(n5/2). Proof. Using Theorem 3.13 we obtain
|W[7"]| > |Wint[7"]| > (W(T3(n,d4ax, 1,0)) - W(T4(n,d4in,x4ax, 1)))/2 where d4ax = 2 (n - V2n - 6 - 5) - 1 + p, d^" = 1 (V2n - 6 + 4) + q and ~max
("-1)-4d4i"+2 2
obtain
2 (n - v2n - 6 - 5) - 1 + p, «4 = 2(V2n - 6 + 4) + q and x4 for p € (0,1] and q G [0,1}. Now, using Lemmas 4.2 and 4.7 we further
-I	-I _ Q	C __
|W[7;]| > |Wini[7;]| > — n3 - -v^n5 - 6n4 - 3n2 + ^2n3 - 6n2 +
83 13 ^-- 253
--n--v2n — 6--.
12 12 12
On the other hand, Theorem 2.1 implies |Wint[7"]| < |W[7"]| < (W(P") - W(S") +
12n - 2n + 12?
1)/2 = n3 - 2n2 + n.	'	'	□
Again, since caterpillars T3(n, d, x, s) are chemical trees for all possible values of parameters, and remain chemical after applying repeatedly Transformation A, half of these results hold for chemical trees, i.e. we obtain the following corollary.
Corollary 4.13. Let 7"4 be a class of chemical trees on n vertices where n > 21 is odd. Then |Wini[r„4]| = |W[7"4]| = ©(n3).
Proof. Using Lemma 4.5 we obtain
|W[7"^ > |Wini[7;4]1 > (W(T3(n, dmax, 1, 0)) - W(T3(n, dmin, xmax, 1)))/2
where d^in = + p, x^ax = 4+4d°'"2_("_1) and d^ax = 2 (n - V2n - 6 - 5) - 1 + q for p G [0,1} and q G (0,1]. Using Lemma 4.2 we further obtain
|	1 q 1 /—;-7 11 9 5 /—--- 19 61 ,- 685
|Wint[7"4]| > — n3--v^n5 - 6n4- — n2 + ^2n3 - 6n2+—n-—.
24 8	16 6	12 24	48
□
Again, this result for chemical trees is obtained by considering only chemical trees with large diameter so it probably can be significantly improved, but we leave that as an open problem for future research.
36
Ars Math. Contemp. 15 (2018) 39-51
5 Conclusion
In this paper we have proved that in the case of even n the cardinality of the largest interval Wint[Tn] of consecutive integers which are values of the Wiener index for a tree graph on n vertices equals 1 n3 + O(n5/2). In the case of odd n the value of the Wiener index for a tree on n vertices can be only even number, therefore the cardinality of the largest interval Wmt[Tn ] of consecutive even integers which are values of the Wiener index for a tree graph on n vertices equals n3+O(n5/2). Since the set Wmt[Tn] is a subset of the set W [Tn] of all values of the Wiener index for trees on n vertices, this immediately yields the same result on the cardinality of W [Tn ]. The upper bound |W [Tn]l < 1 n3 - n2 +11 n (i.e. | W [Tn] | < 12 n3 - 2n2 +11 n for odd n) is easily established by calculating the difference of the value of the Wiener index for maximal and minimal tree graphs (the path Pn and the star Sn respectively). Comparing this bound with our results it is readily seen that our results are best possible with respect to n3. Yet, with respect to n2 the results are not so good, because we obtained |W [Tn ]| = |Wint[Tn]| = 1 n3 + O(n5/2) (i.e. 12 n3 + O(n5/2) in the case of odd n). This may be due to the fact that in the paper we aimed at the bound for | Wint [Tn] | and we stopped with our search when the interval was interrupted (when the diameter of a tree became too small or too large). There is the possibility that the same approach extended to the caterpillars of all diameters would yield sufficient improvement on |W[Tn] | to reduce O(n5/2) to O(n2). But we leave that for future research.
Furthermore, in our research we focused only on caterpillar trees, so the obvious corollary is that the same results hold in the narrower class of caterpillar trees. Half of the caterpillars we used are chemical trees, which yields relatively strong result for the class of chemical trees as a direct corollary. Also, we researched the caterpillars grouped by the length of the interior path (which is nearly the diameter), so the results for trees with given diameter would also follow easily though it is questionable how strong those results would be. Researching the same question in the classes of trees with other given parameters might also be interesting direction of future research.
References
[1]	Y.-E. A. Ban, S. Bereg and N. H. Mustafa, A conjecture on Wiener indices in combinatorial chemistry, Algorithmica 40 (2004), 99-117, doi:10.1007/s00453-004-1097-y.
[2]	A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, ActaAppl. Math. 66 (2001), 211-249, doi:10.1023/a:1010767517079.
[3]	I. Gutman, Frequency of even and odd numbers in distance matrixes of bipartite graphs, J. Chem. Inf. Comput. Sci. 34 (1994), 912-914, doi:10.1021/ci00020a027.
[4]	I. Gutman and Y.-N. Yeh, The sum of all distances in bipartite graphs, Math. Slovaca 45 (1995), 327-334, http://maslo.mat.savba.sk/paper.php?id_paper=14 3.
[5]	M. Knor, R. Skrekovski and A. Tepeh, Mathematical aspects of Wiener index, Ars Math. Con-temp. 11 (2016), 327-352, doi:10.26493/1855-3974.795.ebf.
[6]	M. Krnc and R. Skrekovski, On Wiener inverse interval problem, MATCH Commun. Math. Comput. Chem. 75 (2016), 71-80, http://match.pmf.kg.ac.rs/electronic_ versions/Match75/n1/match75n1_71-80.pdf.
[7]	M. Lepovic and I. Gutman, A collective property of trees and chemical trees, J. Chem. Inf. Comput. Sci. 38 (1998), 823-826, doi:10.1021/ci980004b.
[8]	I. Lukovits, Frequency of even and odd numbers in distance matrices of trees, J. Chem. Inf. Comput. Sci. 33 (1993), 626-629, doi:10.1021/ci00014a016.
J. Sedlar: On Wiener inverse interval problem of trees
37
[9] S. G. Wagner, A class of trees and its Wiener index, Acta Appl. Math. 91 (2006), 119-132, doi:10.1007/s10440-006-9026-5.
[10]	S. G. Wagner and H. Wang, On the parity of the Wiener index, European J. Combin. 30 (2009), 996-1004, doi:10.1016/j.ejc.2008.06.004.
[11]	S. G. Wagner, H. Wang and G. Yu, Molecular graphs and the inverse Wiener index problem, Discrete Appl. Math 157 (2009), 1544-1554, doi:10.1016/j.dam.2008.06.008.
[12]	H. Wang and G. Yu, All but 49 numbers are Wiener indices of trees, Acta Appl. Math. 92 (2006), 15-20, doi:10.1007/s10440-006-9037-2.
[13]	H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947), 17-20, doi:10.1021/ja01193a005.
[14]	K. Xu, M. Liu, K. Ch. Das, I. Gutman and B. Furtula, A survey on graphs extremal with respect to distance-based topological indices, MATCH Commun. Math. Com-put. Chem. 71 (2014), 461-508, http://match.pmf.kg.ac.rs/electronic_ versions/Match71/n3/match71n3_4 61-50 8.pdf.