ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 11 (2016) 327-352 Mathematical aspects of Wiener index Martin Knor Slovak University of Technology in Bratislava, Faculty of Civil Engineering, Department of Mathematics, Bratislava, Slovakia Riste Skrekovski FMF, University ofLjubljana & Faculty ofInformation Studies, Novo mesto & University of Primorska, FAMNIT, Koper, Slovenia Aleksandra Tepeh Faculty of Information Studies, Novo mesto & Faculty of Electrical Engineering and Computer Science, University ofMaribor, Slovenia Received 25 January 2015, accepted 8 May 2015, published online 12 January 2016 The Wiener index (i.e., the total distance or the transmission number), defined as the sum of distances between all unordered pairs of vertices in a graph, is one of the most popular molecular descriptors. In this article we summarize some results, conjectures and problems on this molecular descriptor, with emphasis on works we were involved in. Keywords: Graph distance, Wiener index, average distance, topological index, molecular descriptor, chemical graph theory. Math. Subj. Class.: 05C12, 05C05, 05C20, 92E10 1 Introduction Having a molecule, if we represent atoms by vertices and bonds by edges, we obtain a molecular graph, [87, 88]. Graph theoretic invariants of molecular graphs, which predict properties of the corresponding molecule, are known as topological indices. The oldest topological index is the Wiener index [107], which was introduced in 1947 as the path number. At first, the Wiener index was used for predicting the boiling points of paraffins [107], but later a strong correlation between the Wiener index and the chemical properties of a E-mail addresses: knor@math.sk (Martin Knor), skrekovski@gmail.com (Riste Skrekovski), aleksandra.tepeh@gmail.com (Aleksandra Tepeh) Abstract ©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/ 328 Ars Math. Contemp. 11 (2016) 247-254 compound was found. Nowadays this index is a tool used for preliminary screening of drug molecules [1]. The Wiener index also predicts binding energy of protein-ligand complex at a preliminary stage. Hence, the Wiener index was used by chemists decades before it attracted attention of mathematicians. In fact, it was studied long time before the branch of discrete mathematics, which is now known as Graph Theory, was developed. Many years after its introduction, the same quantity has been studied and referred to by mathematicians as the gross status [48], the distance of graphs [29] and the transmission [93]. A great deal of knowledge on the Wiener index is accumulated in several survey papers [13, 16, 24, 67, 109]. This paper is also of similar kind and it appears in a volume dedicated to A. Graovac, whose wide research opus of mathematical chemistry includes also works of the Wiener index, e.g., see [34, 84, 90, 99, 100]. Let d(u, v) denote the distance between vertices u and v in G. The Wiener index of a graph G, denoted by W (G), is the sum of distances between all (unordered) pairs of vertices of G W (G) = ^ d(u,v). (1.1) {u,v}CV (G) Though, the Wiener index is the most common topological index, nowadays we know over 200 topological indices used in chemistry. Here we mention three of them, those, which can be considered as weighted versions of the Wiener index. For an edge e = ij, let ne(i) be the number of vertices of G being closer to i than to j and let ne(j) be the number of vertices of G lying closer to j than to i. The Szeged index of a graph G is defined by Sz (G)= ^ ne(i)ne(j). e=ijEE(G) This invariant was introduced by Gutman [37] during his stay at the Attila Jozsef University in Szeged, and he named it after this place. In 1989, lead by the idea of characterizing the alkanes, Schultz [89] defined a new index MTI(G) that is degree and distance based. Gutman decomposed this index into two parts and called one of them Schultz index (of the first kind), which is defined by S(G)= ^ (d(u)+ d(v)) d(u,v), {u,v}CV(G) where d(v) denotes the degree of v. The same invariant was independently and simultaneously introduced by Dobrynin and Kochetova [17]. Gutman [36] also introduced a new index, Gut(G) = ^^ d(u)d(v)d(u, v), {u,v}CV(G) and named it the Schultz index of the second kind. Nowadays this index is also known as the Gutman index. In this paper we consider mathematical aspects of the Wiener index. This is not a typical survey. We summarize our mathematical work on this molecular descriptor over the past years and, what is more important, we integrate some conjectures, problems, thoughts, and ideas for possible future work that we find interesting. We include also a couple of related open problems that have been considered by other authors. M. Knor et al.: Mathematical aspects of Wiener index 329 2 Some fundamental properties of Wiener index Already in 1947, Wiener has shown that the Wiener index of a tree can be decomposed into easily calculable edge-contributions. In what follows, by n(G) we denote the number of vertices of G. Let F be a graph with p components, T\, T2,..., Tp. Then we set N2(F)= £ n(Ti) n(Tj). 1 108 there exists a caterpillar tree with Wiener index w. The second result is due to Wagner [101], who proved that all integers but 49 are Wiener indices of trees with diameter at most 4. Surprisingly, it turns out that in most cases the inverse problem has many solutions. Fink, LuZar and Skrekovski [30] showed that the following theorem holds. Theorem 3.1. There exists a function f (w) G tfw) such that for every sufficiently large integer w there exist at least 2f (w) trees with Wiener index w. In [30] there is also proposed a constant time algorithm, which for a given integer w returns a tree with diameter four and with Wiener index w. It would be interesting to find a better lower bound on f (w) in Theorem 3.1. However, beside caterpillars and trees with small diameter, it could be interesting to find some other types of trees (or graphs) that solve the inverse Wiener index problem. Li and Wang [75] considered this problem for peptoids, Wagner et. al [103] for molecular M. Knor et al.: Mathematical aspects of Wiener index 331 and so-called hexagon type graphs, and Wagner [102] for graphs with small cyclomatic number. Bereg and Wang [3] experimentally came to the observation that this may hold for binary trees, as stated bellow. Moreover, they observed that the conjecture may hold even when restricting to 2-trees, and even more, they where not able to disprove it for 1-trees (a binary tree of height h is a k-tree if every vertex of depth less than h — k has precisely two children). Conjecture 3.2. Except for some finite set, every positive integer is the Wiener index of a binary tree. In [73] was considered the following problem, so called the Wiener inverse interval problem. Problem 3.3. For given n, find all values w which are Wiener indices of graphs (trees) on n vertices. Regarding the above problem, let WG(n) and WT(n) be the corresponding sets of values w for graphs and trees on n vertices, respectively. Both sets have ("+1) for the maximum element. The smallest value in WG(n) is and in WT(n) it is (n — 1)2. In [73], the size of the set WG(n) was considered, and it was shown that it is of order 6 n3 + O ( n2 . In the same paper the following problems were stated. Conjecture 3.4. The cardinality of WG(n) is of order 6 n3 — 2 n2 + ©(n). Conjecture 3.5. The cardinality of WT(n) equals 1 n3 + © (n2). In fact in [73] it was shown that the length of the largest interval of integers which is fully contained in WG(n) is of size 1 n3 + O (n2). Regarding the length of the largest interval when only trees are considered, the following is conjectured. Conjecture 3.6. In the set WT(n), the cardinality of the largest interval of integers equals © (n3h. 4 Graphs with prescribed minimum/maximum degree Here we consider extremal values of the Wiener index in some subclasses of the class of all graphs on n vertices. Recall that the maximum degree of a graph G, denoted by A(G), and the minimum degree of a graph, denoted by ¿(G), are the maximum and minimum degree of its vertices. As mentioned above, among n-vertex graphs with the minimum degree > 1, the maximum Wiener index is attained by Pn. But when restricting to minimum degree > 2, the extremal graph is Cn. Observe that with the reasonable assumptions A > 2 and 5 < n — 1, the following holds max{W(G); G has maximum degree at most A and n vertices} = W(Pn), and min{W(G); G has minimum degree at least S and n vertices} = W(Kn). Analogous reasons motivate the following two problems. Problem 4.1. What is the maximum Wiener index among n-vertex graphs with the minimum degree at least S? 332 Ars Math. Contemp. 11 (2016) 247-254 Problem 4.2. What is the minimum Wiener index among n-vertex graphs with the maximum degree at most A? A related problem was considered by Fischermann et al. [31], and independently by Jelen and Trisch in [52, 53], who characterized the trees which minimize the Wiener index among all n-vertex trees with the maximum degree at most A. They also determined the trees which maximize the Wiener index, but in a much more restricted family of trees which have two distinct vertex degrees only. Later Stevanovic [94] determined the trees which maximize the Wiener index among all graphs with the maximum degree A, and originally Problem 4.2 was proposed by him in an equivalent form which requires that the maximum degree is precisely A. Restricting to A = S = r, i.e., restricting to regular graphs, could be especially interesting. In general, introducing (resp. removing) edges in a graph decreases (resp. increases) the Wiener index, but in the class of r-regular graphs on n vertices we have fixed number of r • n/2 edges. Thus, more important role is played by the diameter. Recall that in the case of trees, where the number of edges is fixed as well, the maximum Wiener index is attained by Pn which has the largest diameter, and the minimum Wiener index is attained by Sn, which has the smallest diameter. Let us start with the first nontrivial case r = 3, i.e. with cubic graphs. Figure 1: The graph L18. Let n be even and n > 10. If 4 { n, then Ln is obtained from (n — 10)/4 copies of K4 — e joined to a path by edges connecting the vertices of degree 2, to which at the ends we attach two pendant blocks, each on 5 vertices, see Figure 1 for L18. Figure 2: The graph L20. On the other hand if 4 | n, then Ln is obtained from (n — 12)/4 copies of K4 — e, joined into a path by edges connecting the vertices of degree 2, to which ends we attach two pendant blocks, one on 5 vertices and the other on 7 vertices, see Figure 2 for L2o [68]. We have the following conjecture. Conjecture 4.3. Among n-vertex cubic graphs, Ln has the largest Wiener index. We believe that similar statements hold also for higher r > 4, with intermediate repetitive gadget K4 — e replaced by Kr+1 — e, where on both ends we attach suitable gadgets so that the resulting graph will have n vertices. Actually, these graphs are those with the M. Knor et al.: Mathematical aspects of Wiener index 333 maximum diameter, see [58], where the problem of finding a regular graph of given order and degree with maximum diameter is studied from a different point of view. The cubic graphs with the minimum Wiener index are hard to describe for us but it seems that they have the smallest diameter. For suitable n, good candidates are the cage graphs, e.g. Petersen graph and Heawood graph. Guided by our intuition, we believe that the following may hold. Conjecture 4.4. Among all r-regular graphs on n vertices, the maximum Wiener index is attained by a graph with the maximum possible diameter. Conjecture 4.5. Among all r-regular graphs on n vertices, the minimum Wiener index is attained by a graph with the minimum possible diameter. 5 Graphs with prescribed diameter/radius The eccentricity ecc(v) of a vertex v in G is the largest distance from v to another vertex of G; that is, max{d(v,w) | w G V(G)}. The diameter of G, denoted by diam(G), is the maximum eccentricity in G. Similarly, the radius of G, denoted by rad(G), is the minimum eccentricity in G. Plesnik [86] obtained the graphs with minimum Wiener index in the class of graphs of order n and diameter d (d < n — 1). When d < n — 1, they are cycle-containing graphs. In 1975 he [85] addressed the following problem. Problem 5.1. What is the maximum Wiener index among graphs of order n and diameter d? This problem remains unsolved even under additional restrictions. DeLaVina and Waller [9] conjectured the following. Conjecture 5.2. Let G be a graph with diameter d > 2 and order 2d + 1. Then W(G) < W (C2d+1), where C2d+1 denotes the cycle of length 2d + 1. Wang and Guo [105] determined the trees with maximum Wiener index among trees of order n and diameter d for some special values of d, 2 < d < 4 or n — 3 < d < n — 1. Independently, Mukwembi [83] considered the diameter up to 6 and showed that bounds he obtained are best possible. It could be also interesting to find a sharp upper bound on the Wiener index for trees of given order and larger diameter. For any connected graph G, rad(G) < diam(G) < 2rad(G). By considering the close relationship between the diameter and the radius of a graph, it is natural to consider the above problem with radius instead of diameter [5]. Problem 5.3. What is the maximum Wiener index among graphs of order n and radius r? Chen et al. [5] characterized graphs with the maximum Wiener index among all graphs of order n with radius two. Analogous problem for the minimum Wiener index was posed by You and Liu [110]. Problem 5.4. What is the minimum Wiener index among all graphs of order n and radius r? 334 Ars Math. Contemp. 11 (2016) 247-254 Regarding this problem, Chen et al. [5] stated the following conjecture. For integers n, r, and s with n > 2r, r > 3, and n — 2r +1 > s > 1, construct a graph Gn,r,s from a 2r-cycle v1v2 ■ ■ ■ v2r so that v1 is replaced by Ks and v2 is replaced by Kn-2r+2-s, connect v2r to each vertex of Ks, connect each vertex of Ks to each vertex of Kn-2r+2-s, and connect each vertex of Kn-2r+2-s to v3 (in other words vi is replicated s — 1 times, and v2 is replicated n — 2r + 1 — s times). Notice that the resulting graph has n vertices and radius r. Conjecture 5.5. Let n and r be two positive integers with n > 2r and r > 3. Then graphs Gn,r,s for s € {1,..., r — 1} attain the minimum Wiener index in the class of graphs on n vertices and with radius r. 6 Congruence relations for Wiener index It was of interest to several authors to obtain congruence relations for the Wiener index. The first result of this kind was proved by Gutman and Rouvray [43]. They established the congruence relation for the Wiener index of trees with perfect matchings. Theorem 6.1 (Gutman and Rouvray). Let T and T' be two trees on the same number of vertices. If both T and T' have perfect matchings, then W (T) = W (T') (mod 4). A segment of a tree is a path contained in the tree whose terminal vertices are branching or pendant vertices of the tree. Dobrynin, Entringer and Gutman [13] obtained a congruence relation for the Wiener index in the class of k-proportional trees. Trees of this class have the same order, the same number of segments, and the lengths of all segments are multiples of k. Theorem 6.2 (Dobrynin, Entringer and Gutman). Let T and T' be two k-proportional trees. Then W(T) = W(T') (mod k3). Theorem 6.1 was recently generalized by Lin in [76] by establishing the congruence relation for the Wiener index of trees containing T-factors. A graph G has a T-factor if there exist vertex disjoint trees T1,T2,... ,Tp such that V(G) = V(T1) U V(T2) U ■ ■ ■ U V(Tp) and each T is isomorphic to a tree T on r vertices. If T is a path on r vertices, we say that the graph G has a Pr -factor. In this sense the well-known perfect matching is a P2-factor. Theorem 6.3 (Lin). If T and T' are two trees on the same number of vertices, both with Pr-factors, then W(T) = W(T') (mod r) for odd r, and W(T) = W(T') (mod 2r) for even r. Recently Gutman, Xu and Liu [46] showed that the first congruence in the above result is a special case of a much more general result on the Szeged index. As its consequence, for the Wiener index they obtained the following result. M. Knor et al.: Mathematical aspects of Wiener index 335 Theorem 6.4 (Gutman, Xu and Liu). Let To be the union of connected graphs Gi, G2,..., Gp, p > 2, each of order r > 2, all blocks of which are complete graphs. Denote by r a graph obtained by adding p — 1 edges to r0 so that the resulting graph is connected. Then W(r) = ^ W(Gj) (mod r). In [49] we generalized both the above results. Let r and t be integers, r > 2 and 0 < t < r. Further, let H = {Hi, H2,..., H^} be a set of connected graphs, such that for all i, 1 < i < i, we have |V(H,)| = -t (mod r). Finally, let F = {F1, F2,..., be a set of connected graphs, such that for all j, 1 < j < i - 1, we have | V (Fj) | = t + 2 (mod r). For every Fj, choose vertices v1, v? G V(Fj). We remark that the vertices v1 and v? are not necessarily distinct. Denote by G = G (H, F) the set of all graphs obtained when all the vertices vj and v?, 1 < j < i - 1, are identified with some vertices of H1 U H2 U • • • U Hi so that the resulting graph is connected. Every graph in G contains i graphs from H, i - 1 graphs from F, and each graph of F connects two graphs of H. Since the graphs in G are connected, if we contract every Hj to a single vertex and we consider Fj's as edges joining pairs of these contracted vertices, then the resulting graph is a tree. In this way, H1, H2,..., H can be regarded as supervertices, F1, F2,..., Fi_1 as superedges, and the resulting graph has a tree structure. In Figure 3 we have one graph G of G for given parameters r, t and i, and for given sets H, F and {vj v?}^. The vertices of Hj's are depicted by full circles in Figure 3 and the edges of Hj's are thick. Figure 3: A graph of G for r = 7, t = 3, £ = 4 and given Hj's, Fj's and 's. Theorem 6.5. Let G1, G2 G G. Then W(G1) = W(G2) (mod r). Now we generalize the second part of Theorem 6.3. Let r be an even number, r > 2. Further, let H = {H1, H2,..., H^} be a set of trees, such that for all i, 1 < i < i, we have |V(Hj)| = 0 (mod r). Finally, let F = {F1, F2,..., F£-1} be a set of trees, such that for all j, 1 < j < i — 1, we have |V(Fj)| = 2 (mod r). For every Fj, choose vertices v1, v? G V(Fj). Denote by GT the set of all graphs obtained when all the vertices v1 and v?, 1 < j < i - 1, are identified with some vertices of H1 U H2 U • • • U He so that the 336 Ars Math. Contemp. 11 (2016) 247-254 resulting graph is connected. Hence, GT is a restriction of G when all the graphs in H and F are trees and t = 0. Theorem 6.6. Let r be even and Gi, G- € GT. Then W (Gi) = W (G2) (mod 2r). Theorems 6.5 and 6.6 show limits of Theorem 6.3. Note that a segment can be defined on graphs as well, and similarly one can define k-proportional graphs. So, it would be interesting to find analogous limits for Theorem 6.2. Problem 6.7. Let G and G be two k-proportional graphs. Under which conditions we have W(G) = W(G') (mod k3) ? 7 Wiener index and line graph operation Let G be a graph. Its line graph, L(G), has vertex set identical with the set of edges of G and two vertices of L(G) are adjacent if and only if the corresponding edges are adjacent in G. Iterated line graphs are defined inductively as follows: Li(G) = / G ifi = 0 L (G) = \ L(Li-i(G)) if i> 0. The main problem here is to determine the relation between W(L(G)) and W(G). Particularly, we focuss on graphs G satisfying W (L(G)) = W (G), (7.1) see [8, 22, 21, 40, 42], and in particular see the expository papers [24, 67]. Let us remark that in the literature one easily encounters the term edge-Wiener index of G, which is actually the Wiener index of the line graph, sometimes shifted by (!-), see [55]. The following remark of Buckley [4] is a pioneering work in this area. Theorem 7.1 (Buckley, 1981). For every tree T, W(L(T)) = W(T) - (-). By the above result, the Wiener index of a line graph of a tree is strictly smaller than the Wiener index of the original tree. An interesting generalization of this was given by Gutman [38]: Theorem 7.2. If G is a connected graph with n vertices and m edges, then W(L(G)) > W(G) - n(n - 1) + 1 m(m + 1). In addition, regarding Theorem 7.1, Gutman and Pavlovic [42] showed that the Wiener index of a line graph is not greater than the Wiener index of the original graph even if we allow a single cycle in the graph. Theorem 7.3. 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. 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 [42]. There are 26 bicyclic graphs of order 9 with the property W(L(G)) = W(G) [14, 41], and already 166 ten-vertex vertices with this property, see [24]. The following result tells us that in most cases (7.1) does not hold for graphs of minimum degree at least 2, see [6, 108]. M. Knor et al.: Mathematical aspects of Wiener index 337 Theorem 7.4. Let G be a connected graph with S(G) > 2. Then W(L(G)) > W(G). Moreover, the equality holds only for cycles. 7.1 Sandwiching by Gutman index The following result was proved independently and simultaneously in [6] and [108]. Theorem 7.5. Let G be a connected graph of size m. Then 1 1 ( m^fl 4 (Gut(G) - m) < W(L(G)) < ^Gut(G) - m) + ^ Moreover, the lower bound is attained if and only ifG is a tree. Let Kj(G) denote the number of ¿-cliques in a graph G. In [65], the lower bound of the above theorem is improved in the following way. Theorem 7.6. Let G be a connected graph. Then, 1 1 3 W(L(G)) > ^Gut(G) - ^|E(G)| + 4ks(G) + 3k4(G) (7.2) with the equality in (7.2) if and only if G is a tree or a complete graph. It follows from the above theorem that for a connected graph G of minimal degree S > 2 we have ¿2 1 1 W(L(G)) > -W(G) - 1 |E(G)| > S2 - -W(G). Moreover, this lower bound was improved in [72]. Theorem 7.7. Let G be a connected graph ofminimum degree S. Then W(L(G)) > ¿J2W(G) with equality holding if and only if G is isomorphic to a path on three vertices or a cycle. 7.2 Extremal line graphs The problem of finding graphs, whose line graph has the maximal Wiener index was given by Gutman [38] (see also [24]). Problem 7.8. Find an n-vertex graph G whose line graph L(G) has the maximal Wiener index. We say that a graph is dumbell if it is comprised of two disjoint cliques connected by a path, and similarly a graph is barbell if it is comprised of two disjoint complete bipartite graphs connected by a path. Conjecture 7.9. In the class of graphs G on n vertices, W(L(G)) attains maximum for some dumbell graph. The above conjecture is supported by a result in [8]. We state a similar one for bipartite graphs. Conjecture 7.10. Let n be a large integer. Then in the class of all bipartite graphs G on n vertices W (L(G)) attains maximum for some barbell graph. 338 Ars Math. Contemp. 11 (2016) 247-254 7.3 Extremal ratios Dobrynin and Mel'nikov [24] proposed to estimate the extremal values for the ratio W (Lk (G)) W (G) ' (7.3) and explicitly stated the case k = 1 as a problem. In [72] this problem was solved for the minimum. Theorem 7.11. Among all connected graphs on n vertices, the fraction WW(g)) is minimum for the star Sn. The problem for the maximum remains open. imol Tmliiac nf W_ W (G) Problem 7.12. Find n-vertex graphs G with maximal values of W(L(G)) Notice that W(L(Sn)) _ n - 2 W(L(P„)) _ n - 2 ^ W(L(Kn)) _ (n - 1 W (S„) 2(n + 1)' W (P„) n +1' W (KJ V 2 The line graph of Kn has the greatest number of vertices, and henceforth, it may attain the maximum value. Restricting to bipartite graphs, the almost balanced complete bipartite graphs have most vertices, so in this class of graphs the extreme could be K^n/2j ,[n/2]. Regarding the minimum of (7.3), we expect that for higher iterations k > 2, it should be Pn, as it is the only graph whose line graph decreases in size. We believe the following holds, as it is proposed and considered in [50]. Conjecture 7.13. Let k > 2 and let n be a large integer. Then in the class of graphs G on n vertices W (Lk (G))/W (G) attains the maximum for Kn, and it attains the minimum for Pn. 7.4 Graphs with given girth The girth of a graph is the length of a shortest cycle contained in the graph. 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)). In [23], Dobrynin and Mel'nikov stated the following problem. 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))? (7.4) The above problem (7.4) was solved by Dobrynin [11] for all girths g = {5, 7}; these last two cases were solved separately. Already in [23], Dobrynin and Mel'nikov [23] constructed infinite families of graphs of girths three and four with the property W(G) = W(L(G)). Inspired by their result the following statement was proved in [6]. Theorem 7.14. For every non-negative integer h, there exist infinitely many graphs G of girth g = h2 + h + 9 with W(L(G)) = W(G). The above result encouraged the authors of [6] to state the following conjecture. Conjecture 7.15. For every integer g > 3, there exist infinitely many graphs G of girth g satisfying W (G) = W (L(G)). M. Knor et al.: Mathematical aspects of Wiener index 339 7.5 Graphs and cyclomatic number The cyclomatic number A(G) of a graph G is defined as A(G) = |E(G)| - |V(G)| + 1. Some attention was devoted to graphs G with prescribed cyclomatic number satysfying the equality W(L(G)) = W(G). As already mentioned, the smallest 26 bicyclic graphs with 9 vertices are reported in [14,41]. Bicyclic graphs up to 13 vertices are counted in [24] and diagrams of such graphs with 9 and 10 vertices are also given. The smallest 71 tricyclic graphs with 12 vertices are counted in [14]. There are 733 tricyclic graphs of order 13 with this properties [24]. Denote by n(A) the minimal order of graphs with cyclomatic number A > 2 and W(L(G)) = W(G). Then n(2) = 9 and n(3) = 12. Graphs with increasing cyclomatic number were constructed in [15, 21, 22]. To construct graphs from [22], properties of the Pell equation from the number theory were applied. The cyclomatic number A of graphs from [22] rapidly grows and the order of graphs is asymptotically equal to (2 + %/5)A « 4.236A when A ^ to. The following conjecture was put forward in [22]: Conjecture 7.16. The graphs constructed in [22] have the minimal order among all graphs with given cyclomatic number satisfying the property W(L(G)) = W(G). Graphs for all possible A > 2 were constructed in [21]. It is known that n(A) < 5A for A > 4, n(5) < 21 and n(7) < 29. The following problem was posed in [14]. Problem 7.17. Find an exact value of n(A) for small A > 4. 7.6 Quadratic line graphs The graph L2(G) is also called the quadratic line graph of G. As mentioned above, for non-trivial tree T we cannot have W(L(T)) = W(T). But there are trees T satisfying W (L2 (T ))= W (T), (7.5) see [10, 18, 19, 67]. Obviously, the simplest trees are such which have a unique vertex of degree greater than 2. Such trees are called generalized stars. More precisely, generalized t-star is a tree obtained from the star , t > 3, by replacing all its edges by paths of positive lengths, called branches. In [23] we have the following theorem. Theorem 7.18. Let S be a generalized t-star with q edges and branches of length k1, k2,..., kt. Then W(l2(s)) = W(S) + 2(t( Ek2 + q) -q2 + 6 Q). (7.6) Based on this theorem, it is proved in [23] that W(L2(S)) < W(S) if S is a generalized 3-star, and W(L2(S)) > W(S) if S is a generalized t-star where t > 7. Thus, property (7.5) can hold for generalized t-stars only when t G {4, 5,6}. In [23] and [66], for every t G {4, 5, 6} infinite families of generalized t-stars with property (7.5) were found, see also [67]. These results suggest the following conjecture [20]: Conjecture 7.19. Let T be a non-trivial tree such that W(L2(T)) = W(T). Then there is an infinite family of trees T' homeomorphic to T, such that W (L2(T')) = W (T'). 340 Ars Math. Contemp. 11 (2016) 247-254 Of course, more interesting is the question which types of trees satisfy (7.5). Perhaps such trees do not have many vertices of degree at least 3. Let T be a class of trees which have no vertex of degree two, and such that T e T if and only if there exists a tree T' homeomorphic to T, and such that W(L2(T')) = W(T'). Trees that satisfy (7.5) are in abundance, so perhaps, it is impossible to characterize them, but the characterization of trees from T could be achievable. Problem 7.20. Characterize the trees in T. By the above results, among the stars only K1j4, K1j5, and K1j6 are in T. Recently, the following progress was done by Ghebleh, Kanso, Stevanovic [35] regarding the above problem. Note that in [66] it was conjectured that this set is finite. Theorem 7.21. T is infinite. Up to our knowledge the trees constructed in [35] may have arbitrary many 3-vertices, but no vertex of higher degree. Possibly, the later can be achieved with combination of all these known constructions. However, we expect that no tree in T has a vertex of degree exceeding 6 and the number of vertices of degree at least 4 is bounded, and perhaps it is very small, 1 or 2 or so. In order to motivate further research in this direction, we state these expectations as problems. Conjecture 7.22. Trees from T satisfy the following: (a) no tree has a vertex of degree exceeding 6; (b) there is a constant c such that no tree has more than c vertices of degree at least 4. 7.7 Iterated line graphs As we have seen, there is no non-trivial tree T for which W(L(T)) = W(T) and there are many trees T, satisfying W(L2 (T)) = W(T). However, it is not easy to find a tree T and i > 3 such that W(Li(T)) = W(T). In [13], Dobrynin, Entringer and Gutman posed the following problem: Is there any tree T satisfying equality W(L®(T)) = W(T) for some i > 3? (7.7) Observe that if T is a trivial tree, then W(Li(T)) = W(T) for every i > 1, although here the graph L® (T) is empty. The real question is, if there is a non-trivial tree T and i > 3 such that W(L®(T)) = W(T). The same question appeared four years later in [23] as a conjecture. Based on the computational experiments, Dobrynin and Mel'nikov expressed their belief that the problem has no non-trivial solution and stated the following conjecture: There is no tree T satisfying equality W(T) = W(L®(T)) for any i > 3. (7.8) In a series of papers [59], [60], [61], [62], [63] and [64], conjecture (7.8) was disproved and all solutions of problem (7.7) were found, see also [67]. Let Ha,b,c be a tree on a + b + c + 4 vertices, out of which two have degree 3, four have degree 1 and the remaining a + b + c - 2 vertices have degree 2. The two vertices of degree 3 are connected by a path of length 2. Finally, there are two pendant paths of lengths a and b attached to one vertex of degree 3 and two pendant paths of lengths c and 1 attached to the other vertex of degree 3, see Figure 4 for H3 2 4. We have the following statement. M. Knor et al.: Mathematical aspects of Wiener index 341 b Figure 4: The graph Ha,b, Theorem 7.23. For every j, k G z define a a = 128 + 3j2 + 3k2 - 3jk + j, b = 128 + 3j2 + 3k2 - 3jk + k, c = 128 + 3j2 + 3k2 - 3jk + j + k. c 2 2 2 Then W(L3(H0,6,C)) = W(Ha,6,c). Let I G {j, k, j + k}. Since for every integers j and k the inequality 3j2 + 3k2 - 3jk + I > 0 holds, we see that a, b, c > 128 in Theorem 7.23. Therefore, the smallest graph satisfying the assumptions is Hi28,i28,i28 on 388 vertices, obtained when j = k = 0. If we take in mind that there are approximately 7.5 • 10175 non-isomorphic trees on 388 vertices while the number of atoms in the entire Universe is estimated to be only within the range of 1078 to 1082, then to find "a needle in a haystack" is trivially easy job compared to finding a counterexample when using only the brute force of (arbitrarily many) real computers. The following theorem gives a complete answer to problem (7.7). Theorem 7.24. Let T be a tree and i > 3. Then the equation W(L®(T)) = W(T) has a solution if and only if i = 3 and G is of type Ha,b,c as stated in Theorem 7.23. We conclude this section with the following problem. Problem 7.25. Find all graphs (with cycles) G and powers i for which For i = 1 the above problem is very rich with many different solutions, so probably it will not be possible to find all of them. But still, stating it as a problem could serve as a motivation for searching of various graph classes that satisfy the equation. However, we want to emphasize the case i > 2. In this case the problem is still rich with many solutions, particularly among the trees, but abandoning the class of trees can reduce the solutions significantly. At the moment, cycles are the only known cyclic graphs G for which W(L®(G)) = W(G) holds for some i > 3 and we believe that there are no other cyclic graphs satisfying (7.9). This was conjectured independently in [24] and [67]. Conjecture 7.26. Let i > 3. There is no graph G, distinct from a cycle and a tree, such that W (L (G)) = W (G). (7.9) W (L (G)) = W (G). 342 Ars Math. Contemp. 11 (2016) 247-254 8 Excursion into digraphs In [69, 70, 71], we have considered the Wiener index of not necessarily strongly connected digraphs. In order to do so, if in a digraph there is no directed path from a vertex u to a vertex v, we follow the convention that which was independently introduced in several studies of directed networks. A counterpart of the Wiener theorem for directed trees, i.e. digraphs whose underlying graphs are trees can be stated in this way. Theorem 8.1. Let T be a directed tree with the arc set A(T). Then where t(a) denotes the number of vertices that can reach a, and s(b) denotes the number of vertices that can be reached by b. Here we give a counterpart of a relation between the Wiener index and betweenness centrality B(x) for oriented graphs. Theorem 8.2. For any digraph D of order n where p(D) denotes the number of ordered pairs (u, v) such that there exists a directed path from u to v in D. The above result implies that for strongly connected digraph D on n vertices, we have the relation xtv (D) Let Wmax(G) and Wmin(G) be the maximum possible and the minimum possible, respectively, the Wiener index among all digraphs obtained by orienting the edges of a graph G. Problem 8.3. For a given graph G find Wmax(G) and Wmin(G). The above problem has been considered for strongly connected orientations. Plesnik [86] proved that finding a strongly connected orientation of a given graph G that minimizes the Wiener index is NP-hard. Regarding the problem of finding Wmax(G), Plesnik and Moon [82, 86] resolved it for complete graphs, under the assumption that the orientation is strongly connected. We showed [69] that the above mentioned results of Plesnik and Moon hold also for non-strongly connected orientations assuming the condition (8.1). One may expect that for a 2-connected graph G, Wmax(G) is attained for some strongly connected orientation. However, this is not the case as we proved by ©-graphs ©a,&,i for a and b fulfilling certain d(u, v) = 0, (8.1) W (T )= ^ t(a)s(b), abeA(T) W (D) =^3 B(x)+ p(D), xev (D) M. Knor et al.: Mathematical aspects of Wiener index 343 conditions. By ©a,b,c we denote a graph obtained when two distinct vertices are connected by three internally-vertex-disjoint paths of lengths a +1, b +1 and c +1, respectively. We assume a > b > c and b > 1. The orientation of ©a,b,c which achieves the maximum Wiener index is not strongly connected if c > 1. However, we believe that the following holds. Conjecture 8.4. Let a > b > c. Then Wmax(©a,b,c) is attained by an orientation of ©a,b,c in which the union of the paths of lengths a +1 and b + 1 forms a directed cycle. Analogous results as for ©-graphs, stating that the orientation of a graph which achieves the maximum Wiener index is not strongly connected, can probably be proved also for other graphs which are not very dense and which admit an orientation with one huge directed cycle without "shortcuts", that is without directed paths shortening the cycle. On the other hand, we were not able to find examples without long induced cycles that makes us wonder if the following holds. Conjecture 8.5. Let G be a 2-connected chordal graph. Then Wmax(G) is attained by an orientation which is strongly connected. Finally, we wonder how hard it is to find Wmax and Wmin. Problem 8.6. For a given graph G, what is the complexity of finding Wmax(G) (resp. Wmin(G))? Are these problems NP-hard? Consider also the following problem for the minimum value. Conjecture 8.7. For every graph G, the value Wmin(G) is achieved for some acyclic orientation G. This is certainly true for bipartite graphs. Namely, by orienting all edges of such a graph G so that the corresponding arcs go from one bipartition to the other, we obtain a digraph D with W(D) = |E(G)|. As obviously Wmin(G) > |E(G)|, this case is established. Now we turn our attention to graphs with higher chromatic number. Our next conjecture is motivated by the Gallai-Hasse-Roy-Vitaver theorem, which states that a number k is the smallest number of colors among all colorings of a graph G if and only if k is the largest number for which every orientation of G contains a simple directed path with k vertices. In other words, the chromatic number x(G) is one plus the length of a longest path in a special orientation of the graph which minimizes the length of a longest path. The orientations for which the longest path has the minimum length always include at least one acyclic orientation. A graph orientation is called k-coloring-induced, if it is obtained from some proper k-coloring such that each edge is oriented from the end-vertex with the bigger color to the end-vertex with the smaller color. Conjecture 8.8. Wmin(G) is achieved for a x(G)-coloring-induced orientation. As mentioned above, Conjecture 8.8 holds for bipartite graphs and trivially it holds for complete graphs. It was shown that holds for graphs with at most one cycle and prisms. By computer it was tested also for the Petersen graph. Observe that Conjecture 8.8 implies Conjecture 8.7. 344 Ars Math. Contemp. 11 (2016) 247-254 9 Wiener index for disconnected graphs Since the formula (1.1) cannot be applied to non-connected graphs, for these graphs we set W (G) = £ d(x,y). (9.1) {x,y}CV (G) x — y path exists in G In other words, we ignore pairs of vertices x and y for which the distance d(u, v) can be considered as "infinite" analogously as we ignored such pairs of vertices in the case of digraphs. For example, in [12], the Wiener index has been used in quantitative studies of disconnected hexagonal networks. Let G be a disconnected graph with components G1, G2,..., Gp. By (9.1) we get W(G) = W(G1) + W(G2) + • • • + W(Gp). It is interesting to study the problems from the previous sections using the modified definition of Wiener index (9.1). Particularly, we find interesting the analogues of Problems 3.3 and (7.7). Problem 9.1. For given n, find all values w which are Wiener indices of not necessarily connected graphs (forests) on n vertices. Let i > 3. From the proof of Theorem 7.24 one can see that most trees T satisfy W(L4(T)) > W(T), while paths on n > 2 vertices satisfy W(L®(Pn)) < W(Pn). Hence, the following problem is interesting. Problem 9.2. For i > 3, find all forests F for which W(L4(F)) = W(F). 10 Trees with given degree conditions Lin [77] characterized the trees which maximize and minimize the Wiener index among all trees of given order that have only vertices of odd degrees. An ordering of trees by their smallest Wiener indices for trees of given order that have only vertices of odd degrees was obtained by Furtula, Gutman and Lin [33]. In [32] Furtula further determined the trees with the second up to seventeenth greatest Wiener indices. Lin [77] suggested analogous problems for general graphs. Problem 10.1. Characterize the graphs with maximal Wiener index in the set of graphs on 2n vertices whose vertices are all of odd degree, and in the set of graphs on n vertices whose vertices are all of even degree, respectively. In [78] Lin characterized the trees which minimize (maximize, respectively) the Wiener index among all trees with given number of vertices of even degree. He proposed the following problems for the class of graphs En,r of order n with exactly r vertices of even degree, where r > 1 and n = r (mod 2). Problem 10.2. Order the trees in En,r with the smallest or greatest Wiener index. Problem 10.3. Characterize graphs with maximal and minimal Wiener index in En r, respectively. M. Knor et al.: Mathematical aspects of Wiener index 345 The same author in [79] characterized trees which maximize the Wiener index among all trees of order n with exactly k vertices of maximum degree. For better understanding how the maximum degree vertices influence the Wiener index he proposes to consider analogous problem for the minimum. Problem 10.4. Characterize the tree(s) with the minimal Wiener index among all trees of order n with exactly k vertices of maximum degree. Wang [104] and Zhang et al. [96] independently determined the tree that minimizes the Wiener index among trees of given degree sequence. But the following problem from [54, 91, 97] is still open, although it is known for longer time that extremal graphs are caterpillars [92]. Problem 10.5. Which trees maximize the Wiener index among trees of given degree sequence? 11 Few more problems Here we collect some more problems on Wiener index. Eulerian graphs. Denote by En the set of all Eulerian graphs of order n. Gutman et al. [39] characterized elements of En having the first few smallest Wiener indices. They proved that for graphs in En, Cn attains the maximal value. In addition, they posed a conjecture on the second-maximal Wiener index in En. Conjecture 11.1. The second-maximal Wiener index between all Eulerian graphs of large enough order n is attained by Cn,3 (i.e. the graph obtained from disjoint cycles Cn-2 and C3 by identifying one vertex in each of them). They have also analogous conjecture for small values of n, see [39] for more details. Fullerene graphs. In [51] the Wiener indices of the (6,0)-nanotubes (tubical fullerenes) is computed. Note that such a graph has 12k vertices, for some k > 2, and the corresponding value of the Wiener index is 48k3 + 828k — 1632. These fullerenes have long diameter and consequently big Wiener index. Nevertheless the authors believe that the following may hold. Conjecture 11.2. The Wiener index of fullerene graphs on n vertices is of asymptotic order 6(n3). Wiener index versus Szeged index. Klavzar, Rajapakse and Gutman [56] showed that Sz (G) > W(G), and even more, by a result of Dobrynin and Gutman [25], equality Sz (G) = W(G) holds if and only if each block of G is complete. In [80] a classification of graphs with n(G) = Sz (G) — W(G) < 3 is presented. In [81] the authors classify connected graphs which satisfy n(G) =4 or 5. Moreover, they state the following conjecture. Conjecture 11.3. Let G be a graph of order n with blocks Bi,..., Bk such that none is complete. Let Bi be of order ni. Then k Sz (G) — W(G) > ^(2nj — 6). i=i 346 Ars Math. Contemp. 11 (2016) 247-254 The difference n was also studied by Klavzar and Nadjafi-Arani [57]. Wiener index of graphs with given matching number. Zhou and Trinajstic [98] determined the minimum Wiener index of connected graphs with n > 5 vertices and matching number i > 2, and characterized the extremal graphs. Du and Zhou [28] determined the minimum Wiener indices of trees and unicyclic graphs, respectively, with given number of vertices and matching number. Also, they characterized extremal graphs. For this class of trees Tan [95] et al. determined ordering of trees with the smallest Wiener indices. Regarding the maximum Wiener index, Dankelmann [7] determined it for connected graphs with n > 5 vertices and matching number i > 2, and he characterized the unique extremal graph, which turned out to be a tree. Thus, the maximum Wiener index among trees with given number of vertices and matching number is known, as well as the corresponding unique extremal graph. Finding the maximum Wiener index among unicyclic graphs remains an open problem [28]. Problem 11.4. Find the maximum Wiener index among unicyclic graphs with n vertices and matching number i for 3 < i < LfJ — 1. Graph connectivity. Graphs with higher connectivity have more edges, and henceforth smaller Wiener index. Gutman and Zhang [47] showed that in the class of k-connected graphs on n vertices, the minimum value of Wiener index is attained by Kk + (K1 U Kn-k-1), i.e. the graph obtained when we connect all vertices of Kk with all vertices of disjoint union of K1 and Kn-k-1. This graph is extremal also in the class of k-edge-connected graphs on n vertices. They pose the following problem. Problem 11.5. Find the maximum Wiener index among k-connected graphs on n vertices. Note that Pn is the extremal graph in the class of 1-connected graphs, and Cn is extremal in the class of 2-connected graphs. Of course, similar problem can be posed for k-edge-connected graphs. The authors of [47] ask the following question, which has affirmative answer in the case of the minimum Wiener index. Problem 11.6. Do the extremal graphs for the maximum Wiener index in the classes of k-connected and k-edge-connected graphs coincide? Trees and unicyclic graphs with given bipartition. Du [27] considered Wiener index of trees and unicyclic graphs on n vertices with prescribed sizes of bipartitions p and q, where n = p + q and p > q. He showed that in the case of trees, the extremal graph for the minimum Wiener index is obtained by connecting the centers of disjoint stars K1p-1 and K1q-1, and the extremal graph for the maximum Wiener index is obtained by connecting the end-vertices of a path P2q-1 with [(p — q + 1)/2] and |_(p — q + 1)/2j new vertices, respectively. Regarding the unicyclic graphs, Du showed that the minimum Wiener index is attained by the graph, which is obtained by connecting p — 2 vertices to one vertex of a 4-cycle, and connecting q — 2 vertices to its neighbour on the 4-cycle. Moreover, if p = q = 3, then C6 is also an extremal graph. What remains open, is the maximum value. Problem 11.7. Find the maximum Wiener index among unicyclic graphs on n vertices with bipartition sizes p and q, where n = p + q. M. Knor et al.: Mathematical aspects of Wiener index 347 Acknowledgment. We are thankful to A. A. Dobrynin for his valuable comments and suggestions that improved the paper. The first author acknowledges partial support by Slovak research grants VEGA 1/0781/11, VEGA 1/0065/13 and APVV 0136-12. All authors are partially supported by Slovenian research agency ARRS, program no. P1-00383, project no. L1-4292, and Creative Core-FISNM-3330-13-500033. References [1] V. K. Agrawal, S. Bano, K. C. Mathur and P. V. Khadikar, Novel application of Wiener vis-à-vis Szeged indices: Antitubercular activities of quinolones, Proc. Indian Acad. Sci. (Chem. Sci.) 112 (2000), 137-146. [2] Y. A. Ban, S. Bereg and N. H. Mustafa, On a conjecture on Wiener indices in combinatorial chemistry, Algorithmica 40 (2004), 99-117. [3] S. Bereg and H. Wang, Wiener indices of balanced binary trees, Discrete Applied Math. 155 (2007), 457-467. [4] F. Buckley, Mean distance in line graphs, Congr. Numer. 32 (1981), 153-162. [5] Y. Chen, B. Wu and X. An, Wiener Index of Graphs with Radius Two, ISRN Combinatorics, Article ID 906756 (2013), 5 pages. [6] N. Cohen, D. Dimitrov, R. Krakovski, R. Skrekovski and V. Vukasinovic, On Wiener index of graphs and their line graphs, MATCH Commun. Math. Comput. Chem. 64 (2010), 683-698. [7] P. Dankelmann, Average distance and independence number, Discrete Appl. Math. 51 (1994), 75-83. [8] P. Dankelmann, I. Gutman, S. Mukwembi and H.C. Swart, The edge-Wiener index of a graph, Discrete Math. 309 (2009), 3452-3457. [9] E. DeLaVina and B. Waller, Spanning trees with many leaves and average distance, Electronic. J. Combin. 15 (2014), R33 p.16. [10] A. A. Dobrynin, Distance of iterated line graphs, Graph Theory Notes of New York 37 (1999), 8-9. [11] A. A. Dobrynin, The Wiener index of graphs of arbitrary girth and their line graphs, J. Appl. Industrial Math. 4(4) (2010), 505-511. [12] A. A. Dobrynin, Wiener index of hexagonal chains of equal length, In: Quantitative Graph Theory: Mathematical Foundations and Applications, Matthias Dehmer, Frank Emmert-Streib editors, Discrete Mathematics and Its Applications, Chapman and Hall/CRC, 2014, P. 81-109. [13] A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: Theory and applications, Acta Appl. Math 66(3) (2001), 211-249. [14] A. A. Dobrynin, I. Gutman and V. Jovasevic, Bicyclic graphs and their line graphs with coinciding Wiener index (in Russian), Diskretn. Anal. Issled. Oper. Ser. 2 4(2) (1997), 3-9. [15] A. A. Dobrynin and L. S. Mel'nikov, The Wiener index for graphs and their line graphs (in Russian), Diskretn. Anal. Issled. Oper. Ser. 2 11(2) (2004), 25-44. [16] A. A. Dobrynin, I. Gutman, S. KlavZar and P. Zigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002), 247-294. [17] A. A. Dobrynin and A. A. Kochetova, Degree distance of a graph: a degree analogue of the Wiener index, J. Chem. Inf. Comput. Sci. 34 (1994), 1082-1086. 348 Ars Math. Contemp. 11 (2016) 247-254 [18] A. A. Dobrynin and L. S. Mel'nikov, Trees and their quadratic line graphs having the same Wiener index, MATCH Commun. Math. Comput. Chem. 50 (2004), 145-161. [19] A. A. Dobrynin and L. S. Mel'nikov, Trees, quadratic line graphs and the Wiener index, Croat. Chem. Acta 77 (2004), 477-480. [20] A. A. Dobrynin and L. S. Mel'nikov, Some results on the Wiener index of iterated line graphs, Electronic Notes in Discrete Mathematics 22 (2005), 469-475. [21] A. A. Dobrynin and L. S. Mel'nikov, Wiener index, line graph and the cyclomatic number, MATCH Commun. Math. Comput. Chem. 53 (2005), 209-214. [22] A. A. Dobrynin and L. S. Mel'nikov, Wiener index for graphs and their line graphs with arbitrary large cyclomatic numbers, Appl. Math. Lett. 18 (2005), 307-312. [23] A. A. Dobrynin and L. S. Mel'nikov, Wiener index of generalized stars and their quadatic line graphs, Discussiones Mathematicae, Graph Theory 26 (2006), 161-175. [24] A. A. Dobrynin and L. S. Mel'nikov, Wiener index of line graphs, in I. Gutman, B. Furtula (Eds.) Distance in Molecular Graphs - Theory, Univ. Kragujevac, Kragujevac (2012), 85-121. [25] A. A. Dobrynin and I. Gutman, Solving a problem connected with distances in graphs, Graph Theory Notes N.Y. 28 (1995), 21-23. [26] J. K. Doyle and J. E. Graver, Mean distance in a graph, Discrete Math. 17 (1977), 147-154. [27] Z. Du, Wiener indices of trees and monocyclic graphs with given bipartition, Int. J. Quantum Chem. 112 (2012), 1598-1605. [28] Z. Du and B. Zhou, Minimum Wiener indices of trees and unicyclic graphs of given matching number, MATCH Commun. Math. Comput. Chem. 63 (2010), 101-112. [29] R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976), 283-296. [30] J. Fink, B. Luzar and R. Skrekovski, Some remarks on inverse Wiener index problem, Discrete Appl. Math. 160 (2012), 1851-1858. [31] M. Fischermann, A. Hoffmann, D. Rautenbach, L. Szekely and L. Volkmann, Wiener index versus maximum degree in trees, Discrete Appl. Math. 122 (2003) 127-137. [32] B. Furtula, Odd-vertex-degree trees maximizing Wiener index, Kragujevac J. Math. 37 (2013), 129-134. [33] B. Furtula, I. Gutman and H. Lin, More Trees with All Degrees Odd Having Extremal Wiener Index, MATCH Commun. Math. Comput. Chem. 70 (2013), 293-296. [34] A. Graovac and T. Pisanski, On the Wiener index of a graph, J. Math. Chem. 8 (1991), 53-62. [35] M. Ghebleh, A. Kanso and D. Stevanovic, Open quipus with the same Wiener index as their quadratic line graph, to appear in Appl. Math. Comp. [36] I. Gutman, Selected properties of the Schultz molecular topological index, J. Chem. Inf. Comput. Sci. 34 (1994), 1087-1089. [37] I. Gutman, A formula for the Wiener number of trees and its extension to graphs containing cycles, Graph Theory Notes N.Y. 27 (1994), 9-15. [38] I. Gutman, Distance of line graphs, Graph Theory Notes N.Y. 31 (1996), 49-52. [39] I. Gutman, R. Cruz and J. Rada, Wiener index of Eulerian graphs, Discrete Appl. Math. 162 (2014), 247-250. [40] I. Gutman and E. Estrada, Topological indices based on the line graph of the molecular graph, J. Chem. Inf. and Comput. Sci. 36 (1996), 541-543. M. Knor et al.: Mathematical aspects of Wiener index 349 [41] 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 (1997), 19. [42] I. Gutman and L. Pavlovié, More on distance of line graphs, Graph Theory Notes N.Y. 33 (1997), 14-18. [43] I. Gutman and D. H. Rouvray, A new theorem for the Wiener molecular branching index of trees with perfect matchings, Comput. Chem. 14 (1990), 29-32. [44] I. Gutman and R. Skrekovski, Vertex version of the Wiener theorem, MATCH Commun. Math. Comput. Chem. 72 (2014), 295-300. [45] I. Gutman and Y. Yeh, The sum of all distances in bipartite graphs, Math. Slovaca 45 (1995), 327-334. [46] I. Gutman, K. Xu, M. Liu, A Congruence Relation for Wiener and Szeged Indices, Filomat, in press. [47] I. Gutman and S. Zhang, Graph connectivity and Wiener index, Bulletin, Classe des Sciences Mathematiques et Naturelles, Sciences mathematiques 31 (2006), 1-5. [48] F. Harary, Status and contrastatus, Sociometry (1959), 23-43. [49] K. Hrinakova, M. Knor, R. Skrekovski and A. Tepeh, A congruence relation for the Wiener index of graphs with a tree-like structure, MATCH Commun. Math. Comput. Chem. 72 (2014), 791-806. [50] K. Hrinakova, M. Knor and R. Skrekovski, A result about ratio of Wiener index of line graphs, in preparation, 2015. [51] H. Hua, M. Faghani and A. R. Ashrafi, The Wiener and Wiener Polarity Indices of a Class of Fullerenes with Exactly 12n Carbon Atoms, MATCH Commun. Math. Comput. Chem. 71 (2014), 361-372. [52] F. Jelen, Superdominance order and distance of trees, Doctoral thesis, RWTH Aachen, Germany, 2002. [53] F. Jelen and E. Trisch, Superdominance order and distance of trees with bounded maximum degree, Discrete Appl. Math. 125 (2003), 225-233. [54] Y. L. Jin and X. D. Zhang, On the two conjectures of the Wiener index, MATCH Commun. Math. Comput. Chem. 70 (2013), 583-589. [55] M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi and S. G. Wagner, Some new results on distance-based graph invariant, European J. Combin. 30 (2009), 1149-1163. [56] S. KlavZar, A. Rajapakse and I. Gutman, The Szeged and the Wiener index of graphs, Appl. Math Lett. 9 (1996), 45-49. [57] S. KlavZar and M. J. Nadjafi-Arani, Improved bounds on the difference between the Szeged index and the Wiener index of graphs, European J. Combin. 39 (2014), 148-156. [58] M. Knor, Smallest regular graphs of given degree and diameter, Discuss. Math., Graph Theory 34 (2014), 187-191. [59] M. Knor, M. Macaj, P. Potocnik and R. Skrekovski, Trees T satisfying W(L3(T)) = W(T), Filomat 28 (2014), 551-556. [60] M. Knor, M. Macsaj, P. Potocsnik and R. Sskrekovski, Complete solution of equation W(L3(T)) = W(T) for Wiener index of iterated line graphs of trees, Discrete Appl. Math. 171 (2014), 90-103. [61] M. Knor, P. Potocnik and R. Skrekovski, Wiener index in iterated line graphs, Discrete Appl. Math. 160 (2012), 2234-2245. 350 Ars Math. Contemp. 11 (2016) 247-254 [62] M. Knor, P. Potočnik and R. Skrekovski, On a conjecture about Wiener index in iterated line graphs of trees, Discrete Math. 312 (2012), 1094-1105. [63] M. Knor, P. Potočnik and R. Skrekovski, Wiener index of iterated line graphs of trees home-omorphic to the claw Ki,3, Ars Math. Contemp. 6 (2013), 211-219. [64] M. Knor, P. Potocnik and R. Skrekovski, Wiener index of iterated line graphs of trees home-omorphic to H, Discrete Math. 313 (2013), 1104-1111. [65] M. Knor, P. Potocnik and R. Skrekovski, Relationship between edge-Wiener index and Gut-man index of a graph, Discrete Appl. Math. 167 (2014), 197-201. [66] M. Knor and R. Skrekovski, Wiener index of generalized 4-stars and of their quadratic line graph, Australasian J. Combin. 58 (2014), 119-126. [67] M. Knor and R. Skrekovski, Wiener index of line graphs, in M. Dehmer and F. Emmert-Streib (Eds.), Quantitative Graph Theory: Mathematical Foundations and Applications), CRC Press (2014), 279-301. [68] M. Knor, R. Skrekovski and A. Tepeh, Balaban index of cubic graphs, MATCH Commun. Math. Comput. Chem. 73 (2015), 519-528. [69] M. Knor, R. Skrekovski and A. Tepeh, Orientations of graphs with maximum Wiener index, manuscript, 2014. [70] M. Knor, R. Skrekovski and A. Tepeh, Some remarks on the Wiener index of digraphs, Appl. Math. Comput. 273 (2016), 631-636. [71] M. Knor, R. Skrekovski and A. Tepeh, Digraphs with large maximum Wiener index, manuscript, 2016. [72] M. Knor, R. Skrekovski and A. Tepeh, An inequality between the edge-Wiener index and the Wiener index of a graph, Appl. Math. Comput. 269 (2015), 714-721. [73] M. Krnc and R. Skrekovski, On Wiener Inverse Interval Problem, MATCH Commun. Math. Comput. Chem. 75 (2016), 71-80. [74] M. Lepovic and I. Gutman, A collective property of trees and chemical trees, J. Chem. Inf. Comput. Sci. 38 (1998), 823-826. [75] X. Li and L. Wang, Solutions for two conjectures on the inverse problem of the Wiener index of peptoids, Siam J. Discrete Math. 17 (2003), 210-218. [76] H. Lin, A congruence relation for the Wiener index of trees with path factors, MATCH Commun. Math. Comput. Chem. 70 (2013), 575-582. [77] H. Lin, Extremal Wiener index of trees with all degrees odd, MATCH Commun. Math. Com-put. Chem. 70 (2013), 287-292. [78] H. Lin, Extremal Wiener Index of Trees with Given Number of Vertices of Even Degree, MATCH Commun. Math. Comput. Chem. 72 (2014), 311-320. [79] H. Lin, A Note on the Maximal Wiener Index of Trees with Given Number of Vertices of Maximum Degree, MATCH Commun. Math. Comput. Chem. 72 (2014), 783-790. [80] M. J. Nadjafi-Arani, H. Khodashenas and A. R. Ashrafi, On the differences between Szeged and Wiener indices of graphs, Discrete Math. 311 (2011), 2233-2237. [81] M. J. Nadjafi-Arani, H. Khodashenas, A.R. Ashrafi, Graphs whose Szeged and Wiener numbers differ by 4 and 5, Math. Comput. Modelling 55 (2012), 1644-1648. [82] J. W. Moon, On the total distance between nodes in tournaments, Discrete Math. 151 (1996), 169-174. [83] S. Mukwembi and T. Vertik, Wiener index of trees of given order and diameter at most 6, Bull. Aust. Math. Soc. 89 (2014), 379-396. M. Knor et al.: Mathematical aspects of Wiener index 351 [84] O. Orí, F. Cataldo, D. Vukicevic and A. Graovac, Wiener Way to Dimensionality, Iranian J. Math. Chem. 1 (2010), 5-15. [85] J. Plesnik, Critical graph of given diameter, Acta Math. Univ. Comenian. 30 (1975), 71-93. [86] J. Plesnik, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984), 1-21. [87] L. Pogliani, From molecular connectivity indices to semiempirical connectivity terms: Recent trends in graph theoretical descriptors, Chemical Reviews 100 (2000), 3827-3858. [88] M. Randic, Aromaticity of Polycyclic Conjugated Hydrocarbons, Chemical Reviews 103 (2003), 3449-3606. [89] H. P. Schultz, Topological organic chemistry. 1. Graph theory and topological indices of alka-nes, J. Chem. Inf. Comput. Sci. 29 (1989), 239-257. [90] J. Sedlar, D. Vukicevic, F. Cataldo, O. Ori and A. Graovac, Compression ratio of Wiener index in 2-d rectangular and polygonal lattices, Ars Math. Contemp. 7 (2014), 1-12. [91] A. V. Sills and H. Wang, On the maximal Wiener index and related questions, Discrete Appl. Math 160 (2012), 1615-1623. [92] R. Shi, The average distance of trees, Sys. Sci. Math. Sci. 6 (1993), 18-24. [93] L. Soltes, Transmission in graphs: a bound and vertex removing, Math. Slovaca 1 (1991), 11-16. [94] D. Stevanovic, Maximizing Wiener index of graphs with fixed maximum degree, MATCH Commun. Math. Comput. Chem. 60 (2008), 71-83. [95] S. Tan, N. Wei, Q. Wang and D. Wang, Ordering trees with given matching number by their Wiener indices, J. Appl. Math. Comput., OI 10.1007/s12190-014-0840-z. [96] X. D. Zhang, Q. Y. Xing, L. Q. Xu and R. Y. Pang, The Wiener index of trees with given degree sequences, MATCH Commun. Math. Comput. Chem. 60 (2008), 623-644. [97] X. D. Zhang, Y. Liu and M. X. Han, Maximum Wiener index of trees with given degree sequence, MATCH Commun. Math. Comput. Chem. 64 (2010), 661-682. [98] B. Zhou and N. Trinajstic, The Kirchhoff index and the matching number, Int. J. Quantum Chem. 109 (2009), 2978-2981. [99] B. Zhou, A. Graovac and D. Vukicevic, Variable Wiener indices of thorn graphs, MATCH Commun. Math. Comput. Chem. 56 (2006), 375-382. [100] D. Vukicevic and A. Graovac, On modified Wiener indices of thorn graphs. MATCH Commun. Math. Comput. Chem. 50 (2004), 93-108. [101] S. Wagner, A class of trees and its Wiener index, Acta Appl. Math. 91(2) (2006), 119-132. [102] S. Wagner, A note on the inverse problem for the Wiener index, MATCH Commun. Math. Comput. Chem. 64 (2010), 639-646. [103] S. Wagner, H. Wang and G. Yu, Molecular graphs and the inverse Wiener index problem, Discrete Appl. Math. 157 (2009), 1544-1554. [104] H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, Discrete Appl. Math. 156 (2009), 2647-2654. [105] S. Wang and X. Guo, Trees with extremal Wiener indices, MATCH Commun. Math. Comput. Chem. 60 (2008), 609-622. [106] H. Wang and G. Yu, All but 49 numbers are Wiener indices of trees, Acta Appl. Math. 92(1) (2006), 15-20. [107] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947), 17-20. 352 Ars Math. Contemp. 11 (2016) 247-254 [108] B. Wu, Wiener index of line graphs, MATCH Commun. Math. Comput. Chem. 64 (2010), 699-706. [109] K. Xu, M. Liu, K.C. Das, I. Gutman and B. Furtula, A survey on graphs extremal with respect to distance-based topological indices MATCH Commun. Math. Comput. Chem. 71 (2014), 461-508. [110] Z. You and B. Liu, Note on the minimal Wiener index of connected graphs with n vertices and radius r, MATCH Commun. Math. Comput. Chem. 66 (2011), 343-344.