ISSN 2590-9770 The Art of Discrete and Applied Mathematics 6 (2023) #P3.02 https://doi.org/10.26493/2590-9770.1526.2b3 (Also available at http://adam-journal.eu) On maximum Wiener index of directed grids Martin Knor * Slovak University of Technology in Bratislava, Bratislava, Slovakia Riste Škrekovski† University of Ljubljana, FMF, 1000 Ljubljana, Slovenia and Faculty of Information Studies, 8000 Novo Mesto, Slovenia Received 1 February 2022, accepted 12 January 2023, published online 6 March 2023 Abstract This paper is devoted to Wiener index of directed graphs, more precisely of directed grids. The grid Gm,n is the Cartesian product Pm□Pn of paths on m and n vertices, and in a particular case when m = 2, it is a called the ladder graph Ln. Kraner Šumenjak et al. in 2021 proved that the maximum Wiener index of a digraph, which is obtained by orienting the edges of Ln, is obtained when all layers isomorphic to one factor are directed paths directed in the same way except one (corresponding to an endvertex of the other factor) which is a directed path directed in the opposite way. Then they conjectured that the natural generalization of this orientation to Gm,n will attain the maximum Wiener index among all orientations of Gm,n. In this paper we disprove the conjecture by showing that a comb-like orientation of Gm,n has significiantly bigger Wiener index. Keywords: Wiener index, topological graph theory, graph distance. Math. Subj. Class.: 1 Introduction Let G be a graph. Its Wiener index, W (G), is the sum of distances between all pairs of vertices of G. Thus, W (G) = ∑ {u,v}⊆V (G) d(u, v). *Author aknowledges partial support by Slovak research grants VEGA 1/0206/20, VEGA 1/0567/22, APVV– 17–0428, APVV–19–0308. Author acknowledges partial support of the Slovenian research agency ARRS pro- gram P1-0383 and ARRS project J1-3002. †Corresponding author. Author acknowledges partial support of the Slovenian research agency ARRS program P1-0383 and ARRS project J1-3002. E-mail addresses: knor@math.sk (Martin Knor), skrekovski@gmail.com (Riste Škrekovski) cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 2 Art Discrete Appl. Math. 6 (2023) #P3.02 Wiener index was introduced by Wiener [28] in 1947 for its correlation with the boiling point of alkanes, and afterwards it became popular among chemists. By graph theorists it has been considered later under various names, see [10, 13, 24]. More about this invariant can be found in [6, 7, 15, 17, 29]. Wiener index is also tightly related to the average distance, for which µ(G) = W (G)/ ( n 2 ) , see [4, 9], and also [11] for a brief survey. Wiener index of directed graphs. Let D be a directed graph (a digraph). A (directed) path in D is a sequence of vertices v0, v1, . . . , vt such that vi−1vi is an arc of D, where 1 ≤ i ≤ t. The distance dD(u, v) is the length of a shortest path from u to v, and if there is no such path, we set dD(u, v) = 0. (1.1) In real directed networks, there could be no path connecting some pairs of vertices. Strictly speaking, the distance between such a pair of vertices is infinite (thus the study of the Wiener index of digraphs in pure mathematical papers is usually limited to strongly con- nected digraphs, i.e. digraphs in which a directed path between every pair of vertices exists). However, for practical purposes, in the case when a directed path between two vertices does not exist, the distance between them can be defined in different ways. For instance, Botafogo et al. [3] defined it as the number of vertices in the analyzed network, while Bonchev [1, 2] assumed the condition (1.1). We adopt the latter in this paper. Denote wD(u) = ∑ v∈V (D) dD(u, v). Wiener index of D, W (D), is the sum of all distances in D, where each ordered pair of vertices has to be taken into account. Hence, W (D) = ∑ (u,v)∈V (D)×V (D) dD(u, v) = ∑ u∈V (D) wD(u). The study of Wiener index of digraphs was initiated by Harary [13], who applied it to sociometric problems. Strict lower bound for the Wiener index of digraphs was found by Ng and Teh [20]. Wiener index of digraphs was considered also indirectly, through the study of the average distance, see [5, 8]. Wiener theorem for directed trees. In [28], Wiener proved that for a tree T W (T ) = ∑ e=ij∈E(T ) ne(i)ne(j), where ne(i) and ne(j) are the orders of components of T − ij. The result is known as the Wiener theorem. We have shown an analogous statement for directed trees assuming the condition (1.1) in [18]. Let T (a) denote the set of vertices x with the property that there exists a directed path from x to a. Similarly, let S(a) denote the set of vertices x with the property that there exists a directed path from a to x. Note that a ∈ S(a) and a ∈ T (a). Let t(a) = |T (a)| and s(a) = |S(a)|. A directed tree is a digraph whose underlying graph is a tree. We have the following. Theorem 1.1. Let T be a directed tree. Then W (T ) = ∑ ab∈A(T ) t(a)s(b). M. Knor and R. Škrekovski: On maximum Wiener index of directed grids 3 Wiener index vs. betweenness centrality. Additional motivation for using (1.1) arises from betweenness cetrality in complex networks. White and Borgatti [27] generalized Freeman’s geodesic centrality measures for betweenness on graphs to the case of digraphs in the following way. Let P (D) denote the set of ordered pairs (u, v) of distinct vertices u and v such that there exists a directed path from u to v in D. Furthermore, σu,v denotes the number of all shortest directed paths in D from u to v and σu,v(x) stands for the number of all shortest directed paths from u to v passing through the vertex x. The (directed) betweenness centrality B(x) of a vertex x in a digraph D is defined as B(x) = ∑ (u,v)∈P (D) x̸=u,v σu,v(x) σu,v . Note that σu,v ̸= 0 as (u, v) ∈ P . Gutman and Škrekovski [25] showed that for a connected graph G the following holds W (G) = ∑ x∈V (G) B(x) + ( n 2 ) . This formula shows that the Wiener index is related to the betweenness centrality. In [18] we extended the above relation to directed graphs. Theorem 1.2. For any digraph D of order n W (D) = ∑ x∈V (D) B(x) + |P (D)|. Maximum and minimum orientations. For a graph G, let Wmax(G) and Wmin(G) be the maximum and the minimum, respectively, Wiener index among all digraphs obtained by orienting the edges of G. The following problem was posed in [16]. Problem 1.3. For a graph G, find Wmax(G) and Wmin(G). Plesník [22] proved that finding a strongly connected orientation of a given graph G that minimizes the Wiener index is NP-hard, but the case for non-necessarily strongly connected digraphs is unsolved [18]. Problem 1.4. What is the complexity of finding Wmax(G) (resp. Wmin(G))? If the graph is from some specific class, e.g. ladders, then we know these values directly. However for general grids we have no such a strucutral theorem and the complexity is unkown. Let Kn be the complete graph on n vertices. In [19, 22] Plesník and Moon solved Problem 1.3 for Wmax(Kn) under an additional assumption that the extremal graph is strongly connected. In [16] it was shown that the results of Plesník and Moon hold also without the additional assumption (i.e., assuming the condition (1.1)). One may expect that when G is 2-connected, Wmax(G) is attained for some strongly connected orientation. This was disproved in [16] using some Θ-graphs Θa,b,1. More about this topic can be found in [5, 14, 16, 18]. 4 Art Discrete Appl. Math. 6 (2023) #P3.02 Let Pn be a directed path on n vertices. Then W (Pn) = ( n+1 3 ) = 16n 3 +O(n2). Now suppose that G is a graph on n vertices which has a Hamiltonian path H . Direct all edges of H in one direction and direct remaining edges of G in the opposite way. Let DH be the resulting directed graph. Then the orientation of H is a directed path P and if dP (u, v) > 0 then dP (u, v) = dDH (u, v) since the arcs obtained by directing edges not in H cannot be used as “shortcuts". Consequently, Wmax(G) ≥ W (Pn) = 16n 3 + O(n2). This gives a simple lower bound for Wmax(G) if G has a Hamiltonian path. Wiener index of directed grids. In this paper we consider Wiener index of directed grids. The m×n grid Gm,n is the Cartesian product Pm□Pn of paths on m and n vertices. If m = 2, the grid is called the ladder graph Ln. Kraner Šumenjak et al. [26] proved that the maximum Wiener index of a digraph whose underlying graph is Ln is (8n3 + 3n2 − 5n+ 6)/3. Moreover, the optimal orientation of Ln is attained for orientation presented in Figure 1. Figure 1: An orientation of the ladder P2□P6 with the maximum Wiener index. Let Dm,n be the orientation of Gm,n with all Pm-layers oriented up except the last Pm- layer which is oriented down, and all Pn-layers oriented to the left except the first Pn-layer which is oriented to the right, see Figure 3. The following conjecture was stated in [26]. Conjecture 1.5. For every m,n ≥ 2, we have Wmax(Gm,n) = W (Dm,n). The conjecture naturally generalizes the result for m = 2, but in this paper we show that it is not true if m ≥ 3. Let Cm,n be an orientation of Gm,n in which the top Pn- layer is directed to the right and this layer is completed to a directed Hamiltonian cycle C in a zig-zag way as shown by blue arrows on Figure 2. Moreover, the other edges are directed in such a way that they do not shorten directed blue path starting at vertex (1, 1). Of course, Cm,n exists only if n is even. We show that if n is even n ≥ 4 and m ≥ 3, then W (Cm,n) > W (Dm,n). To do this, we calculate W (Cm,n) and W (Dm,n). 2 Wiener indices of Cm,n and Dm,n We start with calculating the Wiener index of a comb-like orientation of a grid. Theorem 2.1. Let n be even and m,n ≥ 4. Then W (Cm,n) = 1 12 (2m 3n3 + 2m3n2 + 2m3n+ 4m3 + 4m2n3 − 3m2n2 −m2n− 6m2 − 2mn3 + 4mn2 − 2mn− 16m+ 24n2 − 72n+ 72 + β) where β = 3n− 6 if m is odd and β = 0 if m is even. M. Knor and R. Škrekovski: On maximum Wiener index of directed grids 5 (5, 1) (5, 2) (5, 8) (1, 1) (1, 2) (1, 8) Figure 2: A comb orientation of the grid G5,8. Proof. We denote the vertices of Cm,n as in Figure 2. In the calculation we use ∑k i=1 i = 1 2 (k 2 + k) and ∑k i=1 i 2 = 16 (2k 3 + 3k2 + k). However, we need also to evaluate the following two sums. First, k/2∑ i=1 (1 + 2 + · · ·+ 2i) = k/2∑ i=1 ( 1 2 ( (2i)2 + 2i )) = k/2∑ i=1 (2i2 + i) = 1 24 (2k3 + 9k2 + 10k). Second, ∑ 2≤r,s≤m |r − s| =2 ∑ 2≤r s if t is even. First assume that t = 1. Then r < s and the shortest path from (r, t) to (s, ℓ) is (r, 1), (r, 2), (r+1, 2), . . . , (m, 2), (m, 1), (m−1, 1), . . . , (s, 1) 8 Art Discrete Appl. Math. 6 (2023) #P3.02 with length 1 + (m− r) + 1 + (m− s) = 2m+ 2− r − s. Hence the sum of considered distances in the first column is ∆1 = ∑ 2≤r s and the shortest path from (r, t) to (s, ℓ) is (r, n), (r+1, n), . . . , (m,n), (m,n−1)(m−1, n−1), . . . , (s, n−1), (s, n) with length (m− r) + 1 + (m− s) + 1 = 2m+ 2− r − s. Hence the sum of considered distances in the n-th column is ∆n = ∑ 2≤r s. Again, the shortest path is one of the following two (r, t), (r, t+1), . . . , (2, t+1), (2, t), . . . , (s, t) with length r + s+ 2, (r, t), . . . , (m, t), (m, t−1), . . . , (s, t−1), (s, t) with length 2m+ 2− r − s. Hence the distance from (r, t) to (s, t) is again min{2m + 2 − r − s, r + s + 2}, and we get the same formula as in the case when t is odd. Now let m be even and 2 ≤ t ≤ n−1. We already know that regardless of the parity of t it holds d ( (r, t), (s, t) ) = min{2m+ 2− r − s, r + s+ 2}. Nevertheless, assume that t is odd and split the distances according to the value of r. r = 2 : 3 + 4 + 5 + 6 + · · · + (m−1) + m r = 3 : 5 + 6 + 7 + · · · + m + (m−1) r = 4 : 7 + 8 + · · · + (m−1) + (m−2) ... r = m2 : (m−1) + m + (m−1) · · · r = m2 + 1 : (m−1) + (m−2) · · · ... r = m−2 : 5 + 4 r = m−1 : 3 Again the summands are symmetric with respect to the diagonal formed by values m. Therefore using the formula derived in the beginning of this proof we get ∆t = m− 2 2 m+ 2 (m− 2 2 ( 1 + 2 + · · ·+ (m−1) ) − (m−2)/2∑ i=1 ( 1 + 2 + · · ·+ 2i )) = 1 12 (4m3 − 9m2 + 2m). And since for even t we get the same distances, ∆t does not depend on the parity of t though it depends on the parity of m. Hence, the contribution of considered pairs to W (Dm,n) is W6 = 2∆1 + (n−2)∆2 = 1 12 (4m3n+ 4m3 − 9m2n− 18m2 + 2mn+ 20m+ β) where β = 3(n−2) if m is odd and β = 0 if m is even. 7. Distances from (r, t) to (s, ℓ), where 2 ≤ r, s ≤ m and 1 ≤ t < ℓ ≤ n. Obviously, in this case (s, ℓ) preceeds (r, t) on P . Using the paths (m, q), (m−1, q), . . . , (2, q) for odd q, (2, q), (3, q), . . . , (m, q) for even q, and for 2 < p < m the paths (p, 1), (p, 2), . . . , (p, n) which exist if m ≥ 4, one can see that the distance from (r, t) to (s, ℓ) in Dm,n equals the distance from (r, t) to (s, ℓ) in the underlying graph. The only exceptions occure when r = s = 2 or r = s = m. If r = s = 2 then the distance from (r, t) to (s, ℓ) is ℓ − t + 2 except the case when ℓ = t + 1 and t is odd, in which case the distance is 1. On the other hand if r = s = m then the distance from (r, t) to (s, ℓ) is ℓ− t+ 2 except the case when 10 Art Discrete Appl. Math. 6 (2023) #P3.02 ℓ = t + 1 and t is even, in which case the distance is 1 again. So for any parity of t, two distances between the layers t and ℓ exceed the corresponding distance in the underlying graph by 2, except the case when ℓ = t + 1, when only one distance between the layers t and ℓ exceeds the corresponding distance in the underlying graph by 2. Using the formula from the beginning of the proof, the sum of all distances from the vertices of {(r, t)}mr=2 to the vertices of {(s, ℓ)}ms=2 is ∆t,ℓ = ∑ 2≤r,s≤m |r − s|+ ∑ 2≤r,s≤m (ℓ− t) + 4− δ = 1 3 (m3 − 3m2 + 2m) + (m−1)2(ℓ− t) + 4− δ, where δ = 2 if ℓ = t+1 and δ = 0 otherwise. Consequently, the contribution of considered distances is W7 = n−1∑ t=1 ( n∑ ℓ=t+1 (1 3 (m3 − 3m2 + 2m) + (m−1)2(ℓ− t) + 4 ) − 2 ) = n(n−1) 2 1 3 (m3 − 3m2 + 2m) + (m−1)2 n−1∑ i=1 (n− i)i+ n(n−1) 2 4− 2(n−1) = 1 12 (2m3n2 − 2m3n+ 2m2n3 − 6m2n2 + 4m2n− 4mn3 + 4mn2 + 2n3 + 24n2 − 50n+ 24). Now W (Cm,n) = ∑7 i=1 Wi. (5, 1) (5, 2) (5, 8) (1, 1) (1, 2) (1, 8) Figure 3: The orientation Dm,n of the grid G5,8 from Conjecture 1.5. In [26], the authors did not evaluate the Wiener index of Dm,n. In order to be able to compare the Wiener indices of Cm,n and Dm,n, we prove the following statement. M. Knor and R. Škrekovski: On maximum Wiener index of directed grids 11 Theorem 2.2. We have W (Dm,n) = 1 12 (10m 3n2 + 10m2n3 − 6m3n− 24m2n2 − 6mn3 + 4m3 + 14m2n+ 14mn2 + 4n3 − 12mn− 4m− 4n). Proof. We denote the vertices of G = Dm,n as in Figure 3. Let (x, y) ∈ V (G). We describe specific subgraphs of G with respect to (x, y) and we describe a formula for cal- culating distances from (x, y) to the vertices of the specific subgraph. Let H be a sub- graph of G which is an orientation of Pr□Ps. Of course, r ≤ m and s ≤ n. More- over, let H has a vertex (a, b) in its corner, such that for every (u, v) ∈ V (H) we have dG((x, y), (u, v)) = dG((x, y), (a, b)) + dG((a, b), (u, v)). I.e., the corner vertex (a, b) is on a shortest path from (x, y) to every vertex of H . Finally, let the distance from (a, b) to vertices of H are the same in H as in the underlying graph. We denote the graph H by Q(a, b, c, d), where (c, d) is a corner of H opposite to (a, b). Obviously, |a − c| = r − 1 and |b− d| = s− 1. Denote t = dG((x, y), (a, b)). Then the sum of distances from (x, y) to the vertices of H is B(t, r, s) =t+ · · ·+ (t+r−1) + (t+1) + · · ·+ (t+r) + . . . + (t+s−1) + · · ·+ (t+s+r−2) = ( t+ r + s 3 ) − ( t+ r 3 ) − ( t+ s 3 ) + ( t 3 ) . We divide the vertices of G into three groups, S1, S2 and S3, and for each group Si, 1 ≤ i ≤ 3, we calculate the contribution of vertices of Si to W (G), i.e., we calculate∑ u∈Si wG(u). However, our calculation is not so detailed as in the proof of Theorem 2.1. The reason is that when we find that the formulae do not split into cases (like the parity of m in Theorem 2.1), then the resulting formula is a polynomial which is of at most 3rd order in both m and n. Hence, its 16 coefficients can be calculated using a system of linear equations for small m and n (2 ≤ m,n ≤ 5), for which W (Dm,n) can be calculated by a computer. (In fact, the resulting polynomial was checked on a much wider range of m and n.) 1. S1 = {(1, a); 1 ≤ a ≤ n}. Let 1 ≤ a ≤ n. Observe that G contains Q(2, n,m, 1). So considering first the distances to the vertices of S1 and then to the vertices of Q(2, n,m, 1) we get wG(1, a) =1 + 2 + · · ·+ (n−a) + (2(n−a)+3) + (2(n−a)+4) + · · ·+ (2(n−a)+a+1) +B(n−a+1,m−1, n) = ( n− a+ 1 2 ) + ( 2n− a+ 2 2 ) − ( 2n− 2a+ 3 2 ) + ( 2n+m− a 3 ) − ( n+m− a 3 ) − ( 2n− a+ 1 3 ) + ( n+ 1− a 3 ) , which gives W1 = n∑ a=1 wG(1, a) = 1 12 (6m2n2 + 12mn3 − 18mn2 − 4n3 + 12n2 − 8n). 12 Art Discrete Appl. Math. 6 (2023) #P3.02 2. S2 = {(a, n); 2 ≤ a ≤ m}. Let 2 ≤ a ≤ m. Then the distances to (x, y), where 1 ≤ x ≤ m and 1 ≤ y ≤ n − 1, are the same in G as in the underlying graph. So considering first the distances to vertices of S2 ∪ {(1, n)} and then to the other vertices we get wG(a, n) =1 + 2 + · · ·+ (m−a) + (a+1) + (a+2) + · · ·+ (2a−1) + (n−1) m∑ s=1 |s− a|+m n−1∑ i=1 i = ( m− a+ 1 2 ) + ( 2a 2 ) − ( a+ 1 2 ) + (n−1) m∑ s=1 |s− a|+m ( n 2 ) , which gives W2 = m∑ a=2 wG(a, n) = 1 12 (4m3n+ 6m2n2 + 4m3 − 12m2n− 6mn2 + 8mn− 4m). 3. S3 = {(a, b); 2 ≤ a ≤ m; 1 ≤ b ≤ n−1}. Let 2 ≤ a ≤ m and 1 ≤ b ≤ n−1. Now we consider first the distances to the vertices of Q(a, b, 1, 1), second the distances to (1, i) where b < i ≤ n, then the distances to vertices of Q(2, n, a, b+1), and finally the distances to the vertices of Q(a+1, n,m, 1). We get wG(a, b) =B(0, a, b) + a+ (a+1) + · · ·+ (a+(n−b)−1) +B(a+n−b, a−1, n−b) +B(2a+n−b−1,m−a, n) = ( a+ b 3 ) − ( a 3 ) − ( b 3 ) + ( n+ a− b 2 ) − ( a 2 ) + ( 2n+ 2a− 2b− 1 3 ) − ( n+ 2a− b− 1 3 ) − ( 2n+ a− 2b 3 ) + ( n+ a− b 3 ) + ( 2n+m+ a− b− 1 3 ) − ( n+m+ a− b− 1 3 ) − ( 2n+ 2a− b− 1 3 ) + ( n+ 2a− b− 1 3 ) , which gives m∑ a=2 wG(a, b) = ( m+ b+ 1 4 ) − ( b+ 2 4 ) − ( m+ 1 4 ) − (m−1) ( b 3 ) + ( n+m− b+ 1 3 ) − ( n− b+ 2 3 ) − ( m+ 1 3 ) + m∑ i=1 ( 2n− 2b− 1 + 2i 3 ) − ( 2n− 2b+ 1 3 ) − ( 2n+m− 2b+ 1 4 ) + ( 2n− 2b+ 2 4 ) + ( n+m− b+ 1 4 ) − ( n− b+ 2 4 ) + ( 2n− 2m− b 4 ) − ( 2n+m− b+ 1 4 ) − ( n+ 2m− b 4 ) + ( n+m− b+ 1 4 ) − m∑ i=1 ( 2n− b− 1 + 2i 3 ) + ( 2n− b+ 1 3 ) , M. Knor and R. Škrekovski: On maximum Wiener index of directed grids 13 and consequently W3 = n−1∑ b=1 m∑ a=2 wG(a, b) = 1 12 (10m3n2 + 10m2n3 − 10m3n− 36m2n2 − 18mn3 + 26m2n+ 38mn2 + 8n3 − 20mn− 12n2 + 4n). Now W (Dm,n) = ∑3 i=1 Wi. 3 Comparing Wiener indices By Theorems 2.1 and 2.2, in variables m and n the polynomial W (Cm,n) is of 6th order while W (Dm,n) is only of 5th order. Therefore, for big m and n we have W (Cm,n) > W (Dm,n). In the next proof we show that W (Cm,n) > W (Dm,n) for all m and n for which Cm,n exists. Theorem 3.1. Let m ≥ 3 and let n be even, n ≥ 4. Then W (Cm,n) > W (Dm,n). Proof. Observe that 3n − 6 > 0 if n ≥ 4. Moreover, part 7 of the proof of Theorem 2.1 is the only one in which we assume m > 3. If m > 3 then the distances considered there are the shortest ones, that is as in the underlying graph, with a few exceptions. In these exceptions the distances are second shortest, i.e. increased by 2, since the graph is bipartite. In the same cases the distances are not shortest possible if m = 3 and they are not shortest even in some other cases. Therefore for all m ≥ 3 and even n ≥ 4 the expression in Theorem 2.1 without β is a lower bound for W (Cm,n). Hence 12 ( W (Cm,n)−W (Dm,n) ) ≥ 2m3n3 − 8m3n2 − 6m2n3 + 8m3n+ 21m2n2 + 4mn3 − 15m2n− 10mn2 − 4n3 − 6m2 + 10mn+ 24n2 − 12m− 68n+ 72 = 2(m−3)3(n−3)3 + 10(m−3)3(n−3)2 + 12(m−3)2(n−3)3 + 14(m−3)3(n−3) + 57(m−3)2(n−3)2 + 22(m−3)(n−3)3 + 6(m−3)3 + 75(m−3)2(n−3) + 98(m−3)(n−3)2 + 8(n−3)3 + 30(m−3)2 + 130(m−3)(n−3) + 39(n−3)2 + 54(m−3) + 61(n−3) + 30 > 0, since m,n ≥ 3 and all the coefficients are positive. By Theorem 2.2, we have W (Dm,n) = W (Dn,m). This is not the case of W (Cm,n). If both m and n are even and m < n, which of W (Cm,n) and W (Cn,m) is bigger? The next statement answers this question. Theorem 3.2. If both m and n are even and 4 ≤ m < n then W (Cm,n) > W (Cn,m). Proof. By Theorem 2.1 12 ( W (Cm,n)−W (Cn,m) ) = −2m3n2 + 2m2n3 + 4m3n− 4mn3 − 5m2n+ 5mn2 + 4m3 − 4n3 − 30m2 + 30n2 + 56m− 56n = (n−m) [ 2m2n2 − 4mn(m+n)− 4m2 − 4n2 +mn+ 30(m+n)− 56 ] . (3.1) 14 Art Discrete Appl. Math. 6 (2023) #P3.02 Denote by ∆ the long expression in brackets of (3.1). If m,n ≥ 6 then m2n2 − 4m2n− 4m2 = m2(n2 − 4n− 4) > 0 m2n2 − 4mn2 − 4n2 = n2(m2 − 4m− 4) > 0 mn+ 30(m+ n)− 56 > 0, and so ∆ > 0. On the other hand if m = 4 then ∆ = 32n2 − 64n− 16n2 − 64− 4n2 + 4n+ 120 + 30n− 56 = 12n2 − 30n > 0 as well. Hence, if m ≥ 4 then ∆ > 0 and consequently W (Cm,n) > W (Cn,m). 4 Concluding remarks and possible further work Figure 4: Grids G3,4 and G3,5 with optimal orientations M3,4 and M3,5, respectively, Hamiltonian paths are thick. Let Cq be a directed cycle on q vertices. Then W (Cq) = q ( q 2 ) = 12q 3 + O(q2). It is known that if G is a directed graph on q vertices then W (G) ≤ W (Cq). Thus, we have the following observation. Figure 5: Gird G3,6 with the optimal orientation M3,6. Observation 4.1. Among all orientations of Gm,n, where m ≥ 3 and n ≥ 4 is even, W (Cm,n) has the best possible order, i.e. W (Cm,n) = Θ(Wmax(Gm,n)). Observe that this is not the case of Dm,n if cn ≤ m ≤ n for a constant c. Even if both m and n are odd, it is easy to find an orientation of the grid in which the Wiener index has the correct order. Just take a Hamiltonian path H of the grid G, and construct GH as decsribed in the Introduction. M. Knor and R. Škrekovski: On maximum Wiener index of directed grids 15 By Theorem 2.1, if c1n ≤ m ≤ c2m where c1 and c2 are constants, then for q = mn we have W (Cm,n) = 16q 3+o(q3). Here the leading term has multiplier as the leading term for W (Pq). But if m is a constant, we have a better bound. In such a case W (Cm,n) = 1 6 (1 + 2 m − 1 m2 )q 3 + O(q2) and for m = 3 the Wiener index is probably even higher. Anyway, C3,n is not the orientation of G3,n with the biggest Wiener index at least if n ∈ {4, 6}. The orientations M3,n of G3,n, 4 ≤ n ≤ 6, with the biggest Wiener index are in Figures 4 and 5. They were found by a computer and W (M3,4) = 578, W (M3,5) = 1116, W (M3,6) = 1928. Just to compare let us mention that W (C3,4) = 538, W (C3,6) = 1740, W (D3,4) = 516, W (D3,5) = 968, W (D3,6) = 1626. In M3,4 and M3,5, thick lines form a Hamiltonian path such that all arcs not in this path are directed oppositely. However, M3,6 does not have such a path. Although W (M3,k) > W (C3,k) for k ∈ {4, 6}, it can be true that limm,n→∞ Wmax(Gm,n)/W (Cm,n) = 1 for even n. Hence, we have the following problem. Problem 4.2. Find the biggest possible constant c, such that Wmax(Gm,n) ≥ c(mn)3 + o ( (mn)3 ) . Of course, the main problem is the following one. Problem 4.3. Find an orientation of Gm,n with the maximum Wiener index. The above problem may be difficult. The extremal graphs M3,4, M3,5 and M3,6 do not have any obvious simple property, but they are at least strongly connected. Therefore, we conclude the paper with the following question. Question 4.4. Let Mm,n be an orientation of Gm,n with the maximum Wiener index. Is Mm,n strongly connected? ORCID iDs Martin Knor https://orcid.org/0000-0003-3555-3994 Riste Škrekovski https://orcid.org/0000-0001-6851-3214 References [1] D. Bonchev, Complexity of protein-protein interaction networks, complexes and pathways, in: Handbook of Proteomics Methods, Humana Press, New York, pp. 451–462, 2003, doi:10.1007/ 978-1-59259-414-6_31, https://doi.org/10.1007/978-1-59259-414-6_31. [2] D. Bonchev, On the complexity of directed biological networks, SAR QSAR Environ Res. 14 (2003), 199–214, doi:10.1080/1062936031000101764, https://doi.org/10.1080/ 1062936031000101764. [3] R. A. Botafogo, E. Rivlin and B. Shneiderman, Structural analysis of hypertexts: Identifying hierarchies and useful metrics, ACM Trans. Inf. Syst. 10 (1992), 142–180, doi:10.1145/146802. 146826, https://doi.org/10.1145/146802.146826. [4] P. Dankelmann, Average distance and independence number, Discrete Appl. Math. 51 (1994), 75–83, doi:10.1016/0166-218X(94)90095-7, https://doi.org/10.1016/ 0166-218X(94)90095-7. [5] P. Dankelmann, O. R. Oellermann and J.-L. Wu, Minimum average distance of strong orien- tations of graphs, Discrete Appl. Math. 143 (2004), 204–212, doi:10.1016/j.dam.2004.01.005, https://doi.org/10.1016/j.dam.2004.01.005. 16 Art Discrete Appl. Math. 6 (2023) #P3.02 [6] A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001), 211–249, doi:10.1023/a:1010767517079, https://doi.org/ 10.1023/a:1010767517079. [7] A. A. Dobrynin, I. Gutman, S. Klavžar and P. Žigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002), 247–294, doi:10.1023/a:1016290123303, https://doi.org/10. 1023/a:1016290123303. [8] J. K. Doyle and J. E. Graver, Mean distance in a graph, Discrete Math. 7 (1977), 147–154, doi:10.1016/0012-365X(77)90144-3, https://doi.org/10.1016/0012-365X(77) 90144-3. [9] J. K. Doyle and J. E. Graver, Mean distance in a directed graph, Environ. Plan. B 5 (1978), 19–29, doi:10.1068/b050019, https://doi.org/10.1068/b050019. [10] R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs, Czechoslovak Math. J. 26(101) (1976), 283–296. [11] W. Goddard and O. R. Oellermann, Distance in graphs, in: Structural Analysis of Com- plex Networks, Birkhäuser, New York, pp. 49–72, 2011, doi:10.1007/978-0-8176-4789-6\_3, https://doi.org/10.1007/978-0-8176-4789-6_3. [12] K. Hajdinová, Wiener index in directed trees, Master’s thesis, Slovak University of Technology in Bratislava, Slovakia, 2015. [13] F. Harary, Status and contrastatus, Sociometry 22 (1959), 23–43. [14] M. Knor, R. Škrekovski and A. Tepeh, Digraphs with large maximum Wiener index, Appl. Math. Comput. 284 (2016), 260–267, doi:10.1016/j.amc.2016.03.007, https://doi.org/ 10.1016/j.amc.2016.03.007. [15] M. Knor, R. Škrekovski and A. Tepeh, Mathematical aspects of Wiener index, Ars Math. Contemp. 11 (2016), 327–352, doi:10.26493/1855-3974.795.ebf, https://doi.org/10. 26493/1855-3974.795.ebf. [16] M. Knor, R. Škrekovski and A. Tepeh, Orientations of graphs with maximum Wiener index, Discrete Appl. Math. 211 (2016), 121–129, doi:10.1016/j.dam.2016.04.015, https://doi. org/10.1016/j.dam.2016.04.015. [17] M. Knor and R. Škrekovski, Wiener index of line graphs, in: M. Dehmer and F. Emmert-Streib (eds.), Quantitative Graph Theory: Mathematical Foundations and Applications, pp. 279–301, 11 2014, doi:10.1201/b17645-10, https://doi.org/10.1201/b17645-10. [18] M. Knor, R. Škrekovski and A. Tepeh, Some remarks on wiener index of oriented graphs, Applied Mathematics and Computation 273 (2016), 631–636, doi:10.1016/j.amc.2015.10.033, https://doi.org/10.1016/j.amc.2015.10.033. [19] J. W. Moon, On the total distance between nodes in tournaments, volume 151, pp. 169–174, 1996, doi:10.1016/0012-365X(94)00094-Y, graph theory and combinatorics (Manila, 1991), https://doi.org/10.1016/0012-365X(94)00094-Y. [20] C. P. Ng and H. H. Teh, On finite graphs of diameter 2, Nanta Math. 1 (1966/67), 72–75. [21] I. Pesek, M. Rotovnik, D. Vukičević and J. Žerovnik, Wiener number of directed graphs and its relation to the oriented network design problem, MATCH Commun. Math. Comput. Chem. 64 (2010), 727–742. [22] J. Plesník, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984), 1–21, doi:10.1002/jgt.3190080102, https://doi.org/10.1002/jgt.3190080102. [23] M. Sampels, On generalized Moore digraphs, in: Parallel Processing and Applied Mathematics, Springer, Berlin Heidelberg, volume 3019, 2004 pp. 42–49, doi:10.1007/ 978-3-540-24669-5_6, https://doi.org/10.1007/978-3-540-24669-5_6. M. Knor and R. Škrekovski: On maximum Wiener index of directed grids 17 [24] L’. Šoltés, Transmission in graphs: a bound and vertex removing, Math. Slovaca 41 (1991), 11–16. [25] R. Škrekovski and I. Gutman, Vertex version of the Wiener theorem, MATCH Commun. Math. Comput. Chem. 72 (2014), 295–300. [26] T. K. Šumenjak, S. Špacapan and D. Štesl, A proof of a conjecture on maximum Wiener index of oriented ladder graphs, J. Appl. Math. Comput. 67 (2021), 481–493, doi:10.1007/ s12190-021-01498-w, https://doi.org/10.1007/s12190-021-01498-w. [27] D. R. White and S. P. Borgatti, Betweenness centrality measures for directed graphs, Social Networks 16 (1994), 335–346, doi:10.1016/0378-8733(94)90015-9, https://doi.org/ 10.1016/0378-8733(94)90015-9. [28] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947), 17–20, doi:10.1021/ja01193a005, https://doi.org/10.1021/ja01193a005. [29] 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, https://match.pmf.kg.ac.rs/electronic_versions/ Match71/n3/match71n3_461-508.pdf.