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≤m
(s− r) = 2
(
(m−2)1 + (m−3)2 + · · ·+ 1(m−2)
)
=2
m−2∑
i=1
(m−1−i)i = 1
3
(m3 − 3m2 + 2m).
We divide all distances in Cm,n into 7 groups.
1. Distances from (1, k) to all vertices of Cm,n. Recall that Cm,n contains a Hamilto-
nian cycle C with some chords. Using these chords one cannot shorten the distance from
(1, k) to (x, y), where 2 ≤ x ≤ m and 1 ≤ y ≤ n. Only the distances to (1, ℓ), where
ℓ < k, can be shortened. Hence, the sum of distances from (1, k) equals
(
mn
2
)
−∆k, where
∆k sums the shortenings of k − 1 distances on C, those from (1, k) to (1, ℓ), 1 ≤ ℓ < k.
Observe that each pair (1, k), (1, ℓ), 1 ≤ ℓ < k, contributes to ∆k by the number of ver-
tices which are avoided when using the edge (2, ℓ)(1, ℓ) instead of the directed blue path
from (2, ℓ) to (1, ℓ). Obviously, ∆1 = ∆2 = 0, but ∆3 = 2m−2, ∆4 = (2m−2) + 2m,
6 Art Discrete Appl. Math. 6 (2023) #P3.02
etc. For ∆ =
∑n
k=1 ∆k we have
∆ =[(2m−2)] + [(2m−2) + 2m] + [(2m−2) + 2m+ (4m−2)] + . . .
+ [(2m−2) + 2m+ · · ·+ ((n−2)m−2) + (n−2)m]
=(n−2)(m+m−2) + (n−3)(2m) + · · ·+ 2((n−3)m+m−2) + 1(n−2)m
=(n−2)1m+ · · ·+ 1(n−2)m+ (m−2)(n−2) + · · ·+ (m−2)2
=m
n−2∑
i=1
(n−1−i)i+ (m−2)2
n/2−1∑
i=1
(n2 − i)
=m(n−1)
n−2∑
i=1
i−m
n−2∑
i=1
i2 + 2(m−2)
n/2−1∑
i=1
i
=
1
12
(2mn3 − 3mn2 − 2mn− 6n2 + 12n).
So the sum of distances considered in this case is
W1 = n
(
mn
2
)
−∆ = 1
12
(6m2n3 − 2mn3 − 3mn2 + 2mn+ 6n2 − 12n).
2. Distances from (k, t) to (1, ℓ), where 2 ≤ k ≤ m and 1 ≤ ℓ < t ≤ n. Here the
distances
to (1, 1) are m+ (m+1) + · · ·+ (m−1)n =
(
(m−1)n+1
2
)
−
(
m
2
)
to (1, 2) are 2 + 3 + · · ·+ ((m−1)(n−2)+1) =
(
(m−1)(n−2)+2
2
)
− 1
to (1, 3) are m+ (m+1) + · · ·+ (m−1)(n−2) =
(
(m−1)(n−2)+1
2
)
−
(
m
2
)
to (1, 4) are 2 + 3 + · · ·+ (m−1)(n−4) + 1 =
(
(m−1)(n−4)+2
2
)
− 1
...
to (1, n−2) are 2 + 3 + · · ·+ ((m−1)2+1) =
(
(m−1)2+2
2
)
− 1
to (1, n−1) are m+ (m+1) + · · ·+ (m−1)2 =
(
(m−1)2+1
2
)
−
(
m
2
)
to (1, n) are 0.
And their sum is
W2 =
n/2∑
i=1
(
(m−1)2i+ 1
2
)
−
n/2∑
i=1
(
m
2
)
+
n/2−1∑
i=1
(
(m−1)2i+ 2
2
)
−
n/2−1∑
i=1
1
=
1
12
(2m2n3 +m2n− 4mn3 + 6mn2 − 11mn+ 2n3 − 6n2 + 10n).
3. Distances from (k, t) to (1, ℓ), where 2 ≤ k ≤ m and 1 ≤ t = ℓ ≤ n. Here the
distances
to (1, ℓ) for odd ℓ are 1 + 2 + · · ·+ (m−1) =
(
m
2
)
to (1, ℓ) for even ℓ < n are 1 + 4 + 5 + · · ·+ (m+1) =
(
m+2
2
)
− 5
to (1, ℓ) for ℓ = n are (m+1) + (m+2) + · · ·+ (2m−1) =
(
2m
2
)
−
(
m+1
2
)
M. Knor and R. Škrekovski: On maximum Wiener index of directed grids 7
And their sum is
W3 =
(n
2
− 1
)((m
2
)
+
(
m+ 2
2
)
− 5
)
+
(
m
2
)
+
(
2m
2
)
−
(
m+ 1
2
)
=
1
12
(6m2n+ 12m2 + 6mn− 36m− 24n+ 48).
4. Distances from (k, t) to (1, ℓ), where 2 ≤ k ≤ m and 1 ≤ t < ℓ ≤ n. In this case
when t is odd or k = 2 then the shortest path is
(k, t), (k−1, t), . . . , (1, t), (1, t+1), . . . , (1, ℓ).
On the other hand if t is even and k ≥ 3 then the shortest path is
(k, t), (k, t+1), (k−1, t+1), . . . , (1, t+1), (1, t+2), . . . , (1, ℓ).
So the sum of distances
for ℓ− t = 1 is (n−1)(2 + 3 + · · ·+m) = (n−1)
((
m+1
2
)
−
(
2
2
))
for ℓ− t = 2 is (n−2)(3 + 4 + · · ·+ (m+1)) = (n−2)
((
m+2
2
)
−
(
3
2
))
...
for ℓ− t = n−1 is 1(n+ (n+1) + · · ·+ (n+m−2)) = 1
((
n+m−1
2
)
−
(
n
2
))
.
And the sum of distances considered in this case is
W4 =
n−1∑
i=1
(n−i)
((
m+ i
2
)
−
(
1 + i
2
))
=
1
12
(3m2n2 − 3m2n+ 2mn3 − 3mn2 +mn− 2n3 + 2n).
So, we are done with this case.
It remains to consider the distances between the vertices (r, t) and (s, ℓ) where 2 ≤
r, s ≤ m and 1 ≤ t, ℓ ≤ n. Let P be the subpath of the Hamiltonian cycle C in Cm,n
starting at (2, n) and terminating at (2, 1). We say that (r, t) preceeds (s, ℓ) if (r, t) preceeds
(s, ℓ) on P .
5. Distances from (r, t) to (s, ℓ), where 2 ≤ r, s ≤ m and 1 ≤ t, ℓ ≤ n when (r, t)
preceeds (s, ℓ) on P .
In this case the distance from (r, t) to (s, ℓ) equals the distance of these vertices on P .
Hence,
W5 =
(m−1)n∑
i=1
(
i
2
)
=
1
12
(2m3n3 − 6m2n3 + 6mn3 − 2mn− 2n3 + 2n).
6. Distances from (r, t) to (s, ℓ), where 2 ≤ r, s ≤ m and 1 ≤ t = ℓ ≤ n when (s, ℓ)
preceeds (r, t) on P . Since both (r, t) and (s, ℓ) are in the same column, see Figure 2, we
have r < s if t is odd and 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≤m
(2m+ 2− r − s) =
(
m− 1
2
)
(2m+2)−
∑
2≤r<s≤m
(r + s)
=
(
m− 1
2
)
(2m+2)− (m−2)
m∑
i=2
i =
1
12
(6m3 − 18m2 + 12m).
Now let t = n. We argue similarly. In this case 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≤m
(2m+ 2− r − s) = ∆1 =
1
12
(6m3 − 18m2 + 12m).
Now let m be odd and 2 ≤ t ≤ n−1. First assume that t is odd. Then r < s and the
shortest path from (r, t) to (s, ℓ) either uses the column t− 1 or t+ 1. Hence, the shortest
path is one of the following two
(r, t), (r, t+1), . . . , (m, t+1), (m, t), (m−1, t), . . . , (s, t) with length 2m+ 2− r − s,
(r, t), (r−1, t), . . . , (2, t), (2, t−1), . . . , (s, t−1), (s, t) with length r + s+ 2.
Hence the distance from (r, t) to (s, ℓ) is min{2m + 2 − r − s, r + s + 2}. Let us split
the distances according to the value of r. Observe that if r = 2 then the second path is the
shortest one, while if s = m (i.e., in the last column) then the first path is the shortest one.
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 = m+12 : m + + (m−
m−1
2 +2)
...
...
r = m−2 : 5 + 4
r = m−1 : 3
These 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− 1
2
m+ 2
(m− 1
2
(
1 + 2 + · · ·+ (m−1)
)
−
(m−1)/2∑
i=1
(
1 + 2 + · · ·+ 2i
))
=
1
12
(4m3 − 9m2 + 2m+ 3).
M. Knor and R. Škrekovski: On maximum Wiener index of directed grids 9
Now assume that t is even, so that 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.