Abstract
In 1984, Plesník determined the minimum total distance for given order and diameter and characterized the extremal graphs and digraphs. We prove the analog for given order and radius, when the order is sufficiently large compared to the radius. This confirms asymptotically a conjecture of Chen et al. We show the connection between minimizing the total distance and maximizing the size under the same conditions. We also prove some asymptotically optimal bounds for the maximum total distance.
Introduction
The total distance W (G) of a graph G equals the sum of distances between all unordered pairs of vertices, i.e. W (G) = {u,v}⊂V d(u, v). In 1984, Plesník [7] determined the minimum total distance among all graphs of order n and diameter d. He did this both for graphs and digraphs and characterized the extremal examples. In this paper we solve the analogous questions for given order n and radius r, when n is sufficiently large compared with r.
Introduction
The extremal graphs attaining the minimal total distance among all graphs with order n and radius r ∈ {1, 2} are easily characterized; complete graphs when r = 1, complete graphs minus a maximum matching when r = 2 and 2 | n and complete graphs minus a maximum matching and an additional edge adjacent to the vertex not in the maximum matching, when r = 2 and 2 ∤ n. For r ≥ 3 the question is harder and a conjecture of the extremal graphs was made by Chen, Wu and An [3] . Here G n,r,s is a cycle C 2r in which we take blow-ups in 2 consecutive vertices by cliques K s and K n−2r+2−s , as defined in Section 2.
Conjecture 1.1 ([3]
). Let n and r be two positive integers with n ≥ 2r and r ≥ 3. For any graph G of order n with radius r, W (G) ≥ W (G n,r,1 ). Equality holds if and only if G ∼ = G n,r,s for some 1 ≤ s ≤ n−2r+2 2
.
Although there are counterexamples to Conjecture 1.1 when n is small (as we discuss below), we will show that Conjecture 1.1 is true asymptotically, i.e. when n ≥ n 1 (r) for some value n 1 (r), in Section 3. Theorem 1.2. For any r ≥ 3, there exists a value n 1 (r) such that for all n ≥ n 1 (r) the following hold
.
There are some main ideas in the proof which are somewhat intuitive. Since the minimum average distance is close to 1, we expect there are many vertices of high degree and there is a large clique. Because the conjectured extremal graphs contain large blow-ups, we can expect there are vertices such that G\v satisfies the original statement as well. By proving that the total distance W (G) and W (G\v) differ by a certain amount with equality if and only if a structure close to the conjectured structure appears, at the end we only need to prove that an extremal graph is exactly of the form G n,r,s .
.
For small values of n with respect to a fixed r, there might be a few exceptions to Conjecture 1.1. The graph Q 3 is a counterexample for the equality statement when r = 3 and n = 8, as it also has a total distance equal to 48. A computer check has shown that this is the only counterexample for n < 10. In the digraph setting, the total distance W (D) of a digraph D equals the sum of all distances between all ordered pairs of vertices. The outradius of D is equal to the smallest value r such that there exists a vertex x for which d(x, v) ≤ r for every vertex v of the digraph D.
.
In this setting, when the outradius r = 1, the extremal digraphs are obviously bidirected cliques, their total distance being 2 n 2 . When r = 2, the extremal digraphs are bidirected cliques missing n edges, one starting in every vertex, with the restriction that no n − 1 of those missing edges end in the same vertex. In this case the total distance W (D) = n 2 . For r ≥ 3, we propose the digraph analog to Conjecture 1.1. The definition of D n,r,s being stated in Section 2. Figure 2 shows D n,r,s for r = 3. Just as in the graph case, like with Conjecture 1.1, for fixed r there may be a few counterexamples for small n. Also Conjecture 1.3 is asymptotically true. Theorem 1.4. For r ≥ 3, there exists a value n 1 (r) such that for all n ≥ n 1 (r) the following hold The proof for this in Section 4 uses the same main ideas as in the graph case, but turns out to be slightly more difficult as the distance function is not symmetric. In this case we consider an expression which gives information about W (D) − W (D\v) in a more general setting.
.
We also prove some asymptotically sharp results on the maximum average distance given the radius. Here the behaviour depends on the exact notion of the radius used in the digraph case. An overview of those results are presented in the Conclusion in Tables 1 and 2 .
Relation between maximum size and minimum average distance
In this subsection, we explain the relation between maximizing the size and minimizing the average distance.
Relation between maximum size and minimum average distance
When one wants to minimize the average distance, one wants to have lots of small distances, so one may expect the minimum occurs when most distances are equal to one. That is, one can expect that the extremal graphs attaining the minimum average distance are the same as those attaining the maximum size. When the diameter of the graph or digraph equals 2, these two extremum problems are obviously equivalent.
Relation between maximum size and minimum average distance
Vizing [8] determined the maximum size of a graph of given order and radius. Through the same arguments, one can check that the graphs G n,r,s are the only extremal graphs without cutvertices having the maximum size when r ≥ 3.
Theorem 1.5 ([8])
. Let f (n, r) be the maximum of edges in a graph with radius r. Then
Theorem 1.5 ([8])
Equality occurs if and only if G is a complete graph when r = 1 or a complete graph minus a maximum matching (and an additional edge covering the remaining vertex when n is odd) if r = 2. When r ≥ 3 and G has no cutvertex, equality occurs if and only if G is isomorphic to G n,r,s for some 1 ≤ s ≤ n−2r+2 2 .
Theorem 1.5 ([8])
So we see the extremal graphs are exactly the same as the ones conjectured by Chen et al [3] . The graph Q 3 is an example showing that the family of extremal graphs are not exactly the same, as its size (12) is strictly smaller than the size of D 8,3,1 (13), but the total distance is the same (48). It may be a possibility that the set of extremal graphs for one problem is a subset of the set of extremal graphs for the other problem.
Theorem 1.5 ([8])
The digraph version of Vizing's result for biconnected digraphs is trivial when r ∈ {1, 2}. When r ≥ 3 and n ≥ 2r, we conjecture that the extremal graphs are exactly those of the form D n,r,s for some 1 ≤ s ≤ n−2r+2 2
Theorem 1.5 ([8])
. Conjecture 1.6. Let r ≥ 3 and n ≥ 2r. Then the maximum size of biconnected digraphs with order n and outradius r is attained by D n,r,1 . Furthermore the extremal digraphs are exactly the ones of the form D n,r,s for some
Theorem 1.5 ([8])
We note that in Theorem 5 of [4] , the maximum size of a digraph with out-radius r has been determined in the case the digraph need not be biconnected. In Section 5 we will prove Conjecture 1.6 for r = 3, as well as the case where r ≥ 4 and n is large enough. Due to Theorem 1.2 and Theorem 1.4 we see that the extremal graphs agree for large n.
Theorem 1.5 ([8])
When one is working with the diameter instead of radius, the results are known and one can see similar relationships, when comparing the extremal (di)graphs attaining the minimum average distance (Plesník [7] ) and minimum size (Ore [6] ). The set of (di)graphs attaining the minimum average distance being a subset of the set of (di)graphs attaining the maximum size in this case.
Theorem 1.5 ([8])
The extremal (di)graphs in the latter case are formed by taking two blow-ups at 2 consecutive non-end vertices of a path of length d (graph case) or the sum of a transitive tournament on d + 1 vertices and the unique longest path in its complement (digraph case). To get the extremal (di)graphs in the former case one needs to take blow-ups only at the 2 central vertices (or one central vertex).
Notation and definitions
A graph will be denoted by G = (V, E) and a digraph will be denoted by D = (V, A). The order |V | will be denoted by n. A clique or bidirected clique on n vertices will be denoted by K n . A cycle or directed cycle of length k will be denoted by C k . The clique number of a graph G, ω(G), is the order of the largest clique which is a subgraph of G. The complement G c of graph G = (V, E) is the graph with vertex set V and edge set E c = In the case of digraphs, the distance function between vertices is not symmetric and so there is a difference between the inner-and outer eccentricity ecc
Notation and definitions
We use the conventions as in e.g. [1] . The in-and outradius of a digraph D are defined by rad
Notation and definitions
Sometimes authors refer to the outradius as radius, as outradius is the most common one between those three definitions.
Notation and definitions
The total distance, also called the Wiener index, of a graph G equals the sum of distances between all unordered pairs of vertices, i.e.
Notation and definitions
. The Wiener index of a digraph equals the sum of distances between all ordered pairs of vertices, i.e.
Notation and definitions
The statement f (x) = O(g(x)) as x → ∞ implies that there exist fixed constants
Notation and definitions
) as x → ∞. Sometimes we do not write the "as x → ∞" if the context is clear. , be the graph obtained by taking two blow-ups of two consecutive vertices in a cycle C 2r by cliques K s and K n−2r+2−s respectively. Let D 2r,r,1 be a digraph with 2r vertices v 1 , v 2 , . . . v r and w 1 , w 2 , . . . , w r , such that there are directed edges from v i to v j and from w i to w j if and only if j ≤ i + 1 and a directed edge from any v i to w 1 and from any w i to v 1 .
Notation and definitions
Let D n,r,s , n ≥ 2r and 1 ≤ s ≤ n−2r+2 2
Notation and definitions
, be the graph obtained by taking the blow-up of v 1 by a bidirected clique K s and a blow-up of w 1 by a bidirected clique K n−2r+2−s .
Conjecture 1.1 for large order
We start with the calculation of the total distance of the graphs G n,r,s and D n,r,s , which we want to prove to be extremal.
Conjecture 1.1 for large order
Lemma 3.1. Suppose G is a graph with order n and total distance W (G) < n 2 + an, for some constant a. Then ω(G) ≥ n 8a , i.e. G contains a clique of order at least n 8a . Furthermore there exists such a clique such that all its vertices have degree at least equal to n − 4a.
Conjecture 1.1 for large order
Proof. Let S be the set of vertices of degree at least n − 4a. Note that |S| ≥ n 2 since otherwise 2W (G) ≥ 2 n 2 + n 2 4a. Now the following algorithm returns a set T of at least n 8a vertices in S which form a clique, since every time T increases by one, U decreases by at most 4a.
Conjecture 1.1 for large order
Start with T = ∅ and U = S. While U is nonempty , do :
Conjecture 1.1 for large order
Take arbitrary v ∈ U and set T :=T ∪ {v} and
Conjecture 1.1 for large order
There is a value n 0 (r) such that for any n ≥ n 0 and any graph G of order n and radius r with minimal total distance among such graphs, there is a vertex v ∈ G such that G\v has radius r and the distance between any 2 vertices of G\v equals the distance between them in G.
Conjecture 1.1 for large order
Proof. Note that such a graph G satisfies W (G) < n 2 + an, where a := a(r) = (r − 1) 2 due to the example G n,r,s and Equation 1. Let n 0 := n 0 (r) = 192a 3 . By Lemma 3.1, we know that G contains a clique K k with k ≥ n 8a = 24a 2 , such that the degree of all its vertices is at least n − 4a. We can take a subset S of vertices of K k of size at most 16a 2 such that for any 2 vertices v, w in G\K k which are connected with a common neighbour in K k have a common neighbour in S and any vertex v in G\K k with a neighbour in K k has a neighbour in S.
Conjecture 1.1 for large order
Taking a first vertex x in K k , it has degree at least n − 4a and hence it is connected to all vertices except for
Conjecture 1.1 for large order
For every of the s vertices v i which has a neighbour x i in K k , add a single x i to S. For every v i , 1 ≤ i ≤ s, there are at most 4a − 1 vertices which are not neighbours of x i . For any such one which has a common neighbour in K k with v i , add the common neighbour to S. We end with a set S of size at most 4a(4a − 1) + 1 < 16a 2 which satisfies the properties. Now for any vertex v ∈ K k \S, the distance measure in G\v equals the restriction to G\v of the distance measure in G. The radius of G\v is at least r − 1, with equality if and only if there is at least one vertex w v in G\K k such that its eccentricity as a vertex in G\v equals r − 1 and d G (v, w v ) = r. Let T be the set of all vertices v ∈ K k \S for which this happens. Note that
Conjecture 1.1 for large order
Lemma 3.3. Let G be a graph with radius r and order n such that there is some vertex v ∈ G such that G\v has also radius r and the same restricted distance function. Then
Conjecture 1.1 for large order
Equality occurs if and only if there is a path Q = w r w r−1 . . .
Conjecture 1.1 for large order
for every vertex w ∈ G which is not on this path.
Conjecture 1.1 for large order
Proof. Let the eccentricity of v in G be r ′ ≥ r. This implies that there exists a path P = vu 1 u 2 . . . u r ′ in G which is the shortest path between u r ′ and v = u 0 . If
Conjecture 1.1 for large order
> (r−1) 2 and the statement is true. Since G has radius r, there exists a vertex z with d(u r ′ −r+1 , z) = r. Since we now assume r ′ < 2r − 1, z is not a vertex of P. Take a shortest path P ′ from v to z and let u i be the vertex in P ∩P ′ with the largest index.
Conjecture 1.1 for large order
Here we used 2r − 1 > r ′ ≥ r, i ≥ 0 and the inequality between the quadratic and arithmetic mean (QM-AM). Equality occurs if and only if r ′ = r, i = 0, d(v, z) = r − 1 and d(w, v) = 1 for every vertex w which is not part of P nor of P ′ .
Conjecture 1.1 for large order
Proof of Theorem 1.2. Take a = a(r) = (r − 1) 2 and n 1 := n 1 (r) = n 0 (r) + a(r)n 0 (r). Let n ≥ n 1 . By Lemma 3.2 we know that there is a sequence of n − n 0 ≥ an 0 vertices v n 0 +1 , . . . , v n which are consecutively added, starting from some graph H with order n 0 and radius r, such that distances and the radius do not change. If no addition of such a vertex gives equality in Lemma 3.3, then
Conjecture 1.1 for large order
which is a contradiction as G n,r,1 has a smaller total distance. Let v = v m be the first vertex whose addition gives equality in Lemma 3.3 and let G m be the final graph at that step. We know part of the characterization of this graph G m . Furthermore, we note that u i is not connected with w j when j < i as otherwise d(w 1 , u i ) = j < i. Similarly, u i is not connected with w j when j > i as otherwise d(u 1 , w j ) = i < j. Also vertices u i and w i are not connected when 1 < i ≤ r − 1 as otherwise ecc(w i ) < r. For any neighbour w of v = w 1 , it is easy to see that we need N [w] ∩ Q ⊂ {w 3 , w 2 , w 1 , u 1 , u 2 }. A small case distinction shows that N [w]∩Q is part of one of the sets {w 3 , w 2 , w 1 }, {w 2 
Conjecture 1.1 for large order
Using the previous observations, we conclude that the graph with minimal total distance at this point (i.e. equality in the three above estimates) was some G m,r,s and the minimum attained after having added v m+1 , . . . , v n will give some G n,r,s .
Conjecture 1.3 for large order
We first prove two lemmas which are formulated more generally.
Conjecture 1.3 for large order
Lemma 4.1. Let D be a digraph with average total degree at least being equal to 2(n − 1) − 2t. Then at least half of the vertices have total degree more than 2(n − 1) − 4t. Also ω(D) ≥ n 8t , i.e. D contains a bidirected clique of size at least n 8t . Proof. The first part is trivial, as the contrary would lead to a contradiction. The second part is analogous to the proof of Lemma 3.1, with S now being the set of vertices with total degree more than 2(n − 1) − 4t. In the algorithm, N (v) = N + (v) ∩ N − (v), will denote the set of vertices w which are both in-neighbours and out-neighbours of v.
Conjecture 1.3 for large order
Lemma 4.2. Let D be a digraph with outradius r ≥ 3, order n and size at least n(n − 1 − t) such that it contains a bidirected clique K k for which all of its vertices have total degree at least 2(n − 1) − 4t. If k > 32t 2 + 4t + tn k , there is a vertex v ∈ K k such that D\v has outradius r and the distance between any 2 vertices of D\v equals the distance between them in D.
Conjecture 1.3 for large order
Proof. We will first construct a set S of vertices of K k of size at most 32t 2 + 4t such that for any 2 vertices x, y in D\K k for which there exists a vertex v ∈ K k such that xv and vy are edges of D, there is an s ∈ S with xs and sy being edges of D as well. Take a first vertex s 1 of K k and assume Z is the set of vertices z of D\K k such that there are no edges in both directions between s 1 and z. For any vertex z ∈ Z that has an edge towards K k , take an additional vertex s i ∈ K k (which we put in S) such that there is an edge from z to s i . Similarly for every vertex z ∈ Z such that there is an edge from K k to z, we take some s i ∈ K k for which there is an edge from s i to z. Note at this point |S| ≤ 4t. Now there are less than 2 · 4t · 4t = 32t 2 pairs of vertices (x, y) in D\K k such that the property is not satisfied by S yet. Adding a corresponding vertex of K k to S gives a set S satisfying the property. Now for any vertex v ∈ K k \S, the distance measure in D\v equals the restriction to D\v of the distance measure in D. The outradius of D\v is at least r − 1. In case equality holds, there is at least one vertex w v in D\K k such that d(w v , v) = r and the outer eccentricity of w v as a vertex in D\v equals r − 1. Let T be the set of all vertices v ∈ K k \S for which this happens. Then for every v ∈ T , there is an associated w v which is not associated with another element from T , for which there is no edge from w v to any element of K k . This implies that at least |T |k arrows are missing, which has to be at most tn, i.e. |T | ≤ tn k .
Conjecture 1.3 for large order
There is a value n 0 (r) such that for any n ≥ n 0 and any digraph D of order n and outradius r with minimal total distance among such digraphs, there is a vertex v ∈ D such that D\v has outradius r and the distance between any 2 vertices of D\v equals the distance between them in D.
Conjecture 1.3 for large order
Proof. Note that such a graph D satisfies W (D) < 2 n 2 + an, where a := a(r) = (r − 1) 2 due to the example D n,r,s and Equation 2. If the size of the digraph would be smaller than n(n−1−a), then W (D) ≥ n(n−1−a)+2an = 2 n 2 +an, which is a contradiction. Due to the equivalent of the handshaking lemma, we know the average total degree is at least 2(n−1)−2a and hence by Lemma 4.1 we know that D contains a clique K k with k ≥ n 8a , such that the (total) degree of all its vertices is at least 2(n − 1) − 4a. Let n 0 := n 0 (r) = 8a(40a 2 + 4a). Since k ≥ n 8a > 32a 2 + 4a + an k ≥ 32a 2 + 4a + 8a 2 when n > n 0 , the result follows from Lemma 4.2. 
Conjecture 1.3 for large order
with equality if and only if the following conditions (up to labeling) are satisfied
Conjecture 1.3 for large order
If this is not possible we take a shortest (directed) path Q from v to x i which has the least number of vertices in common with P. Let P ∩ Q be the directed path vu 1 . . . u j . Then we say x i is of type j. First we notice that there will be no x i of type j for any j ≥ 2. So having no x i of type j ≥ 1, we know that there is some directed path Q = vw 2 w 3 . . . w s for some s ≤ r ′ which is disjoint from P (except from v) or we could take x i = u i−1 in all cases.
Conjecture 1.3 for large order
In the second case, we have that the LHS of Equation 3 is at least
Conjecture 1.3 for large order
where we used the inequality between the quadratic and arithmetic mean (QM-AM).
Conjecture 1.3 for large order
In the first case, we have that d(u i , v) + s − 1 ≥ r when r ′ − r + 1 ≤ i ≤ s − 1 where we can assume 2 ≤ s ≤ r, as s ≥ r + 1 implies the result trivially. When s ≤ i ≤ r, we have
we get that the LHS of Equation 3 is at least
This expression is strictly increasing for r ′ ≥ r, so the minimum is attained when r ′ = r. So the expression reduces to r 2 − r − s + 1 which is minimal for s = r and gives exactly (r − 1) 2 .
we get that the LHS of Equation 3 is at least
In case of equality, we also need d(v, u) = 1 for vertices u not considered (not on the paths), from which the characterization of the equality constraints is clear as well. 
we get that the LHS of Equation 3 is at least
with equality if and only if D[V 1 ] is isomorphic to D 2r,r,1 and for any y ∈ V \V 1 we have
we get that the LHS of Equation 3 is at least
Proof of (4). First note that for every u ∈ V \V 1 and v ∈ V , we have
we get that the LHS of Equation 3 is at least
By the given conditions, we know that
we get that the LHS of Equation 3 is at least
We also have d(u i , w j ) = j for all 1 ≤ i ≤ r − 1, j being an upper bound since d(u i , w 1 ) = 1 and d(w 1 , w j ) = j − 1, while d(u i , w j ) < j for some j would imply d(u i , w r ) < r and hence ecc + (u i ) < r, which would be a contradiction.
we get that the LHS of Equation 3 is at least
Next, we see d(w i , u j ) ≥ j for all 1 ≤ j ≤ r − 1. When min{i, j} = 1, this is by definition. When d(w i , u j ) < j for some 1 < j < r and 1 < i, we would get ecc + (w i ) < r, since
we get that the LHS of Equation 3 is at least
So the digraphs for which Equation 4 is not immediate, satisfy d(u r , w j ) < j for some j or d(w i , u r ) < r for some i. Since d(w 1 , u r ) = r, d(w 1 , w i ) = i − 1 and d(w i , u r−1 ) ≥ r − 1, we see that d(w i , u r ) < r is only possible if there is an arc from w r to u r . The condition d(u r , w j ) < j for some j > 1 would imply d(u r , w j ) = j − 1 since otherwise ecc + (u r−1 ) < r and hence d(u r , u r−1 ) = r as ecc + (u r ) = r and so d(u r , u i ) ≥ 1 + i for all 1 ≤ i ≤ r − 1. Note this already implies that if d(w i , u r ) = r for all i, Equation 4 is satisfied.
we get that the LHS of Equation 3 is at least
So assume d(w r , u r ) = 1 and remark we now need d(w i , u r−1 ) = r for every 1 < i ≤ r, so d(w i , u j ) ≥ j + 1 for all 1 ≤ j ≤ r − 1 and 1 < i ≤ r. So at least (r − 1) 2 distances are at least 1 larger than the corresponding distances in D 2r,r,1 , while the edge between w r and u r made we won only 
we get that the LHS of Equation 3 is at least
from which the result follows again as the sum is at least (r − 1) 2 + 1.
we get that the LHS of Equation 3 is at least
Proof of Theorem 1.4. Let a = a(r) = (r − 1) 2 and n 1 := n 1 (r) = n 0 (r) + a(r)n 0 (r). Let n ≥ n 1 . By Lemma 4.3 we know that there is a sequence of n − n 0 ≥ an 0 vertices v n 0 +1 , . . . , v n which are consecutively added, starting from some digraph H with order n 0 and radius r, such that distances and the radius do not change. Note that a digraph of radius r satisfies the conditions of Proposition 4.4. If no addition of any of the an 0 vertices gives equality in Proposition 4.4, then 
Minimum for digraphs given order and radius
For small r, we easily can determine the exact minimum Wiener index of digraphs with given order and radius r. Note that r can be an integer or a half-integer, i.e. 1 ≤ r with r ∈ 
Minimum for digraphs given order and radius
When r ∈ N, we can take the blow-up of a vertex of a directed cycle C r+1 . When r ∈ between two neighbours. Now take a blow-up of the startvertex of that additional directed edge.
Minimum for digraphs given order and radius
Note that taking a blow-up by a clique K n−4 in vertex 4 or 2 of the digraph in Figure 3 gives a digraph with a smaller total distance than the blow-up of a vertex of a C r+1 when r = 3. 
Maximum size biconnected digraphs
In this section, we prove that Conjecture 1.6 is true when r = 3, as well as in the case r > 3 and n large enough with respect to r. Note that X is not empty, as otherwise D has at most the size of a digraph formed by taking a blowup of a vertex of a directed C 4 , which has a smaller size than (n − 2) 2 . For this, remark that there cannot be a directed edge from some y ∈ Y or a 2 to c as then the outereccentricity of that vertex is at most 2. So there is a directed edge from a 3 to c. For the same reason, there cannot be directed edges from a 3 to a 2 or some y ∈ Y . It is possible there is an edge from a 2 to some y ∈ Y , but then these vertices cannot have Y ⊂ N + [y] and hence the outdegree of these vertices is lower than in the blowup of the directed C 4 , from which the bound on the size follows. Now we do some case analysis. Case 1 There is a y ∈ Y with d + (y) = n − 3. Note that there is no directed edge from y to c since otherwise ecc + (y) = 2 and so there is an arrow from y to all vertices different from c and a 3 , i.e. F (y) = {a 3 , c}. Now we see {a 2 , a 3 , c} ⊂ F (x) for all x ∈ X (using d(y, c) = 3 and d(y, x) = 1), {c, y} ⊂ F (a 2 ), Y ∪{a 2 } ⊂ F (a 3 ) and {c, a 3 } ⊂ F (y ′ ) for all y ′ ∈ Y different from y. From this we see |A(D)| ≤ n 2 − 4n + 4 and equality is not possible, since then ecc + (a 2 ) = 2.
Maximum size biconnected digraphs
case 2 The set X 2 containing the vertices x ∈ X with d + (x) = n−3 has size at least 2, note that we have F (x) = {a 2 , a 3 } for those x. Furthermore we remark that X 2 ∪ {c, a 3 } ⊂ F (y) for every y ∈ Y and X 2 ∪ {c} ⊂ F (a 2 ). We get |A(D)| ≤ n 2 − 4n + 4 − |Y | (|X 2 | − 1) in this case.
Maximum size biconnected digraphs
case 3 In the last case, there is one vertex x 2 ∈ X with d + (x 2 ) = n − 3. Furthermore we need d + (a 2 ) = d + (a 3 ) = d + (c) = n − 3 and d + (v) = n − 4 for all the remaining vertices v. We see that F (x 2 ) = F (c) = {a 2 , a 3 } and F (a 2 ) = {c, x 2 }.
Maximum size biconnected digraphs
Also F (y) = {a 3 , c, x 2 } as ecc + (y) ≥ 3 for every y ∈ Y. If X = {x 2 }, then we get a contradiction as there should be a directed edge from a 3 to exactly one of c and x 2 and consequently there cannot be a directed edge to some y ∈ Y or to a 2 . So now assume X = {x 2 }. By definition we already have {a 2 , a 3 } ⊂ F (x) for any x ∈ X. Since ecc + (a 2 ) = 3 and F (a 2 ) = {c, x 2 }, we see that there can't be directed edges from X\{x 2 } to both c and x 2 . Wlog there is no directed edge towards c, i.e. F (x) = {a 2 , a 3 , c} for every x ∈ X\{x 2 }. Finally, we see F (y) = {c, x 2 } since there cannot be a directed edge towards both c and x 2 and if there is exactly one, then we need d(a 3 , a 2 ) = 3 which cannot either. So we conclude D is isomorphic to D n,r,s where s = min{|X|, |Y |}. Now, we prove that Conjecture 1.6 holds when n is large enough wrt to a fixed r. First, we note that the analog of Lemma 4.3 holds.
Maximum size biconnected digraphs
Lemma 5.2. Let r ≥ 3. There is a value n 0 (r) such that for any n ≥ n 0 and any digraph D = (V, A) of order n and outradius r with maximum size among such digraphs, there is a vertex v ∈ D such that D\v has outradius r and the distance between any 2 vertices of D\v equals the distance between them in D.
Maximum size biconnected digraphs
Proof. Note that such a digraph D satisfies |A| > n(n − 1 − t), where t := t(r) = 2r − 3 due to the example D n,r,s . We know from Lemma 4.1 that D contains a clique K k with k ≥ n 8t , such that the (total) degree of all its vertices is at least 2(n−1)−4t. Let n 0 := n 0 (r) = 8t(40t 2 +4t). Since k ≥ n 8t > 40t 2 + 4t ≥ 32t 2 + 4t + tn k when n > n 0 , the result follows from Lemma 4.2. 
Maximum size biconnected digraphs
The shortest path from v to x does not pass u r ′ −r+1 and so we have at least r ′ − i − 1 vertices w on this path for which there is no edge from v to w. There is no edge from v to u j when r ′ − r + 2 ≤ j ≤ r ′ either. Furthermore v is not in the outneighbourhood of v j when r ′ − r + 1 ≤ j < i. If r ′ > r, then d(v, u r ′ −r+1 ) > 1 as well and in this case deg(v) ≤ 2(n − 1) − (2r − 2). So now r ′ = r. If i = r, one has deg(v) ≤ 2(n − 1) − (2r − 2) again. If 1 < i < r, one gets a contradiction since ecc + (u i ) < r. In the remaining case of equality, we have the desired form.
Maximum size biconnected digraphs
Theorem 5.4. For r ≥ 4, there exists a value n 1 (r) such that for all n > n 1 (r) the following hold Proof. Let n 1 := n 1 (r) = (2r − 2)n 0 . Take a digraph D of size n > n 1 which has the maximum size among all digraphs of order n and outradius r. By Lemma 5.2 there exists a digraph D ′ such that D is formed by adding vertices v n 0 +1 . . . v n . If for all of these additions, there is no equality in Proposition 5.3, then as n > (2r − 2)n 0 we have
Maximum size biconnected digraphs
So now assume there was equality in some step in Lemma 5.2. Then we know a partial characterization of the digraph D m = (V m , A m ) in that step. Let B = {u 1 , u 2 , . . . , u r−1 , u r , v, w 2 , . . . , w r } and R = V m \B. Note that there is no directed edge from u i to w j if 1 ≤ i ≤ r−1 and 2 ≤ j ≤ r as otherwise ecc + (u i ) < r. Similarly, there is no directed edge from w i to u j if 2 ≤ i ≤ r and 2 ≤ j ≤ r − 1 and at most one to u 1 or u r . Since ecc + (u r ) ≥ r, we need d(u r , u r−1 ) = r or d(u r , w r ) = r. This implies that it is impossible there are directed edges from u r to both some w i and u j with 2 ≤ i ≤ r and 1 ≤ j ≤ r − 1. If N + (u r ) ∩ B = {v, w 2 , w 3 , . . . , w r }, then ecc + (u r−1 ) < r which is a contradiction again. Knowing all of this, we already have an upper bound on the number of directed edges between vertices in B. Next, let z ∈ R be a remaining vertex. We now prove that there cannot be more than 2r +3 directed edges between z and B. Note that 
Maximum total distance
The maximum total distance of graphs given their order and diameter was derived asymptotically in Theorem 3.1 of [2] .
Maximum total distance
The maximum Wiener index of a graph with order n and diameter d ≥ 3 is
Maximum total distance
As a corollary, we have the following theorem for the same question when considering the radius instead of the diameter.
Maximum total distance
Corollary 6.2. The maximum Wiener index among graphs of order n and radius r equals rn 2 − r 3/2 Θ(n 3/2 ). The extremal graphs are trees.
Maximum total distance
Proof. A graph with radius r has diameter d ≤ 2r. By Theorem 3.1 of [2] and using d ≤ 2r, we have an upper bound of the desired form. On the other hand, the construction in Section 3 of [2] for d being even is a rooted tree of radius r with Wiener index of the desired form. Taking a center c of any graph G with radius r, we can construct a spanning tree T with a breadth-first search algorithm which has radius r as well. If G was not a tree, then W (G) < W (T ), so we conclude extremal graphs are trees.
Maximum total distance
In the following two subsections, we derive results in the digraph case. Here we only consider biconnected digraphs, as otherwise the total distance can be infinite.
in terms of order and radius
Theorem 6.3. When D is a digraph with radius r, then the maximal possible Wiener index of a digraph with order n and radius r is of the form 2rn 2 − 4r 2 n + Θ r (1). For n > 32r 3 , the extremal digraphs contain DP 2r n , a directed cycle of length d = 2r with a blow-up of one vertex by an independent set of size n − d + 1, as a subdigraph and for small r the extremal digraphs are known. . Let D ′ be the digraph formed from adding the two additional directed edges u r u 1 and u 2r−1 u r to DP 2r n . Then rad(D ′ ) = r and
in terms of order and radius
from which the first part of the theorem follows.
in terms of order and radius
Let d = 2r and define
in terms of order and radius
Analogously For r = 1, the extremal digraphs are exactly DP 2 n . For r ≥ 2, we need to add some edges u i u j where i > j such that d(u r , V ) = d(V, u r ) = r. For r = 2, there are 3 possible directed edges to add and so it is easy to see that we only need to add u 3 u 1 to get the extremal digraph. Using a computer program, we found the optimal ways to do this to get the maximal Wiener index for r ≤ 4. They are presented in Figure 4 .
in terms of order and radius
For small r, the extremal digraphs are formed by adding some small number k directed edges to DP 2r n between the 2r − 1 vertices from the cycle different from the vertex which is used in the blow-up process. For 5 ≤ r ≤ 7, we used a computer program to find the constructions which achieve the first local maximum of the total distance as a function of k. We conjecture these digraphs to be extremal for large n and present them in Figure 5 . Proof. Analogous to the proof of Theorem 6.5, we find that W (D) ≤ n 3 −n 3 + (r − 1)(n 2 − n). For this, note that d(v, x) has been increased by at most r − 1 and so has every term d(u, x).
in terms of order and radius
To prove the bound of this theorem is sharp, take the digraph D in Figure 6 which has out-radius r, where n = qr +k with 2 ≤ k ≤ r +1. When the out-radius equals one, the problem can be solved exactly.
in terms of order and radius
Theorem 6.5. Given a digraph D of order n with outradius equal to 1, the Wiener index of D is at most
in terms of order and radius
with equality if and only if the graph is isomorphic to one of the two configurations given in Figure 7 .
in terms of order and radius
Proof. By definition of rad + , there is some vertex v such that for every vertex u ∈ V (D) different from v, there is a directed edge from v towards u. There is a shortest path from every u to v, having some length i. and f obtains the same values in n − 1 and n − 2. Since i is at most n − 1, we find that
in terms of order and radius
with equality if and only if X i = 1 for every i ≤ n − 3, from which one can conclude that there are only the two given cases of equality. 
Conclusion
The question of determining the minimum total distance among all graphs or digraphs of order n and (out)radius r and characterizing the extremal (di)graphs has been solved for n large enough compared with r. This question has been solved only asymptotically in the digraph case using the radius. In both the graph-and digraph case, it might be challenging to solve the question completely for every order, as there might be sporadic extremal graphs or digraphs other than Q 3 to the two conjectures. The question about finding the maximum total distance given n and r has been considered as well in the three scenarios. The asymptotic results for these and related questions are summarized in Table 1 and Table 2 . For purpose of brevity and intuition, the results are summarized in terms of average rather than total distances.
Conclusion
A problem which may be interesting to solve exactly is the following one.
Conclusion
Problem 7.1. What is the maximum Wiener index of a biconnected digraph with out-radius r > 1? Characterize the extremal digraphs.
Conclusion
It may be possible that the digraph in Figure 6 is the unique extremal digraph for this problem, corresponding to an the analog of Theorem 6.5.
µ(G)
min max
µ(G)
1 + r 2 Θ We also obtained relationships between the extremal graphs and digraphs attaining the mimumum average distance/ maximum size given order and radius/ diameter.
µ(G)
Perhaps the most basic question arising from this paper is conjecture 1.6, what is the maximum size of biconnected digraphs given order and outradius?

{'paper_id': '119143757', 'title': 'Extremal total distance of graphs of given radius', 's2_url': 'https://api.semanticscholar.org/CorpusID:119143757', 'source': 'S2ORC'}