affil0affil0affiliationtext: University of California San Diego, La Jolla, CA,
92093

This is the preprint version of the following article: Nicholas C. Orndorff,
and John T. Hwang. Air-taxi trajectory optimization with
aerodynamic and motor models. Journal of Aircraft, Submitted. Preprint pdf:
https://github.com/LSDOlab/lsdo_bib/blob/main/pdf/orndorff2023trajopt.pdf
Bibtex:
https://github.com/LSDOlab/lsdo_bib/blob/main/bib/orndorff2023trajopt.bib

#  Air-taxi trajectory optimization with
aerodynamic and motor models 00footnotetext:  A version of this paper was
originally presented at the _AIAA SciTech 2023 FORUM_ held in National Harbor,
MD on January 23-27, 2023. Paper number: AIAA 2023-0324.
https://doi.org/10.2514/6.2023-0324

Nicholas C. Orndorff111PhD Student, Department of Mechanical and Aerospace
Engineering and John T. Hwang222Assistant Professor, Department of Mechanical
and Aerospace Engineering

###### Abstract

Many air-taxi concepts are capable of vertical takeoff and landing, enabling
them to fly to and from urban locations. An important capability for these air
taxis is the transition between hover and forward flight. We propose a robust
methodology for computing optimal takeoff and transition trajectories using
surrogate models trained on data from physics-based models. The use of
surrogate models reduces the computational complexity and improves the
robustness of the trajectory optimization algorithm. We demonstrate the
versatility and robustness of the proposed methodology by applying it to 12
trajectory optimization problems that involve air-taxi takeoff and outbound
transition. These trajectories are representative of real air-taxi operations,
with a variety of constraints derived, in part, from proposed mission
requirements.

## Nomenclature

$v$ = | velocity (m/s)
---|---
$\gamma$ = | flight path angle (rad)
$h$ = | altitude (m)
$x$ = | horizontal position (m)
$\alpha$ = | angle of attack (rad)
$\theta$ = | pitch angle (rad)
$m$ = | mass (kg)
$g$ = | acceleration due to gravity ($\text{m/s}^{2}$)
$T_{C}$, $T_{L}$ = | cruise thrust and lift thrust (N)

$L$, $D$ = | lift, drag (N)
---|---
$C_{L}$, $C_{D}$ = | lift/drag coefficients
$C_{T}$, $C_{P}$ = | thrust/power coefficients
$T$, $P$, $Q$ = | thrust (N) power (W) and torque (N-m)
$\rho$ = | density ($\text{kg/m}^{3}$)
$d_{C}$, $d_{L}$ = | cruise and lift rotor diameter (m)
$n$ = | rotor speed (revolutions/s)
$\eta$ = | efficiency (%)

## 1 Introduction

Electric air-taxi concepts are rapidly being developed to meet the vision for
large-scale urban air mobility (UAM). To fulfill this vision, aircraft
designers must carefully model and analyze a wide variety of systems and
design conditions that span a number of engineering disciplines. As such, air-
taxi design is a problem that is well-suited to benefit from large-scale
multidisciplinary design optimization (MDO). Within a large-scale MDO
framework, an entire aircraft concept can be analyzed and optimized in the
presence of many, perhaps hundreds of variables and constraints.

Large-scale MDO has been applied to the design of air-taxis [1, 2] and the
system-level design of electric aircraft [3]. These examples of aircraft
design optimization consider multiple steady mission segments, that provide a
reasonable approximation of the complete mission profile. However, many
proposed air-taxi missions include significant dynamic mission segments [4,
5]. These segments primarily occur at the start and end of each UAM mission,
when the air taxi must transition between hover and cruising flight [6, 7].
This transition is characterized by highly nonlinear flight dynamics and
complex interactions between the aircraft and the environment. Because of this
complexity, optimal trajectories are not necessarily intuitive. One method of
finding these trajectories is to apply a trajectory optimization algorithm
within an MDO framework [6, 8, 9].

Trajectory optimization problems are typically solved with one of three
techniques: dynamic programming, indirect methods, and direct methods [10,
11]. Dynamic programming yields a globally optimal solution but relies upon a
discretized state space which it often must explore in its entirety [12].
Because of this, dynamic programming is best suited to small state spaces and
discrete dynamics. More complex problems are often solved by indirect or
direct methods [13]. Indirect methods rely upon the analytical derivation of
the necessary conditions for optimality [10]. These conditions depend upon the
system model and constraints, and must be re-derived whenever the problem is
modified. Direct methods start by discretizing the system and then applying
optimization. Generally, the discretized system is transcribed as a nonlinear
programming (NLP) problem that can be solved using established gradient-based
optimization methods [14, 15]. With direct transcription, there is no need to
analytically derive the problem-specific necessary conditions for optimality
[8]. Because of this, direct transcription is well-suited to complex problems
with constraints and models that rapidly evolve (e.g., the aircraft design
process).

The conversion from an optimal control problem to a nonlinear program requires
both discretization and simulation. Generally, continuous-time systems are
discretized by introducing collocation points that represent finite points in
time where controls and constraints can be defined [10]. The state values at
the collocation points are defined through simulation. Simulating trajectories
by explicitly propagating states across the collocation points is known as
shooting and typically makes use of standard ODE solution methods [8]. Hwang
and Munster [16] applied the general linear methods (GLM) approach in the
development of an ODE solver within an MDO framework. The GLM method
simplifies the implementation of collocation within an NLP problem by allowing
rapid implementation of multiple integration methods. In order to combine the
GLM method with gradient-based optimization, the derivatives of the resulting
ODE representation must be provided. These can be computed using the modular
analysis and unified derivatives approach [17, 18].

Direct trajectory optimization has been successfully applied to a wide variety
of aerospace applications. For example, Blackmore et al. [19] used direct
methods to develop a Mars landing guidance algorithm that minimizes the
landing target error given specific fuel constraints. By formulating the
dynamics and constraints to be convex, they guarantee finite-time convergence
to an optimal solution. However, the physical phenomena we wish to model are
complex, and it is difficult to create a convex problem. In this case,
convergence of the NLP is not guaranteed and the complexity of the models used
plays a large role in determining the feasibility of the optimization problem.
Despite this, there are many examples of successful trajectory optimization
problems with complex and nonlinear models. In one relevant example, Chauhan
and Martins [6] used nonlinear physics-based models to find optimal takeoff
and transition trajectories for the Airbus Vahana tilt-wing air taxi with a
variety of wing loading and stall constraints. Other examples include the
optimization of supersonic minimum-time-climb trajectories [20, 21], rocket
ascent and evasive maneuvers [22], and electric aircraft trajectories subject
to thermal constraints [23].

In certain cases, physics-based models are too computationally expensive to
include within a trajectory optimization problem due to limitations on
computer power and time. In other cases, these models may contain numerical
singularities (e.g., equations might become undefined when certain variables
are zero). These possibilities hurt the robustness of the optimization
algorithm. Anderson et al. [7] evaluated the effect of model fidelity for
trajectory optimization of a small bi-wing tailsitter aircraft. They
specifically evaluated rotor-wing interactions, and found that higher-fidelity
models were significantly more conservative when predicting rotor power and
wing stall. This example highlights the importance of using higher-fidelity
models in trajectory optimization. One method of reducing model complexity
while maintaining model fidelity is to use surrogate models [24, 25, 26, 27].
This approach generates data offline using the original physics-based model. A
function can then be fit to the data and used as a surrogate model within the
trajectory optimization problem. Because these surrogate models are often
simple continuous functions, they are robust and fast to evaluate. The
popularity of surrogate modeling within MDO problems has led to the creation
of several surrogate modeling toolboxes that include a variety of functions
and allow easy access to derivatives [28, 29].

In this paper we use direct transcription and fast surrogate models to find
optimal takeoff and transition trajectories for NASA’s Lift-plus-Cruise air-
taxi concept [4, 30] (Figure 1). We use four physics-based models: flight
dynamics, lifting-surface aerodynamics, rotor aerodynamics, and motors. With
the exception of the flight dynamics model, the other three models are used to
train new surrogate models that are evaluated within the optimization
algorithm. Every model is written in the Computational System Design Language
(CSDL) [31], which leverages a computational graph to automatically derive
models for computing all the derivatives required for optimization.

We begin by describing our methodology in Section 2. This includes a
description of the individual physics-based models, their corresponding
surrogates, and the complete optimization problem formulation. Next, we
present our results in Section 3. This section demonstrates the robustness of
our approach by using the same models and problem formulation to compute 12
air taxi takeoff and transition trajectories that satisfy minimum-energy and
minimum-time objectives. Our goal with these results is to show that the fast
surrogate modeling approach is not purely academic, and can be directly
applied to complex real-world trajectories. To date, little research exists
that shows optimal trajectories for large air taxis. Therefore these results
also begin to answer the question: what do optimal takeoff and transition
trajectories look like? We conclude by summarizing our results and research
contributions in Section 4.

Figure 1: NASA’s Lift-plus-Cruise air-taxi concept [4].

## 2 Methodology

In this section we present four physics-based models for flight dynamics, wing
aerodynamics, rotor aerodynamics, and motors. When combined, these models
represent all the key disciplines relevant in air-taxi takeoff and transition
trajectory design. Because air-taxi trajectories traverse a wide range of
flight regimes, we paid close attention to the following three areas when
developing these models:

  1. 1.

Robustness: the models must accept a wide range of inputs (e.g., angles of
attack within $\pm 90^{\circ}$)

  2. 2.

Validity: the models must be accurate across many operating conditions (e.g.,
Mach numbers between 0 and 0.3)

  3. 3.

Efficiency: the model evaluations must be inexpensive (surrogate models reduce
the computation time).

Surrogate models are used to improve the computational complexity of model
evaluations. Often, the physics-based models described in this section are
slow (due to the inherent complexity required to model the phenomena in
question) or they contain numerical singularities (e.g., when inputs go to
zero). However, by training surrogate models based on data generated offline,
we can significantly improve the robustness and speed of the optimization
algorithm. Figure 2 shows an evaluation-time comparison between the original
physics-based models and their corresponding surrogate models.

Figure 2: Model evaluation time comparisons between the original physics-based
models and their surrogate-based counterparts (averaged over 40 samples).

###  2.1 Flight Dynamics

Aircraft trajectories are simulated with a three-degree-of-freedom flight
dynamics model. The following four equations allow for the explicit
propagation of the aircraft velocity $(v_{x}\text{ and }v_{z})$, the
horizontal position $(x)$, and the altitude $(h)$ with respect to time:

$m\dot{v}_{x}=T_{c}\cos{\theta}-T_{l}\sin{\theta}-D\cos{\gamma}-L\sin{\gamma}$
(1)

$m\dot{v}_{z}=T_{c}\sin{\theta}+T_{l}\cos{\theta}-D\sin{\gamma}+L\cos{\gamma}-mg$
(2)

$\dot{h}=v_{z}$ (3)

$\dot{x}=v_{x}.$ (4)

Figure 3 depicts these four aircraft states and their corresponding coordinate
systems. The inputs to these equations are the lift and cruise rotor thrust
($T_{c}$, $T_{l}$), the pitch angle ($\theta$), the flight-path angle
($\gamma=\tan^{-1}{(v_{z}/v_{x})}$), lift ($L$), and drag ($D$). In previous
work [32], we found that (a) the difference in thrust between the front and
rear sets of lifting rotors that is required to generate a large pitching
moment is negligible, and (b) the difference in inflow velocities due to
aircraft rotation is also negligible. Consequently, we reduce the
computational complexity of the model by analyzing a single lift rotor and
multiplying the thrust and power by $k$ lift rotors to get the total lift
rotor thrust and the total lift rotor power (e.g., $T_{L}=kT$). This approach
makes the assumption that the aircraft is capable of instantaneously tracking
any commanded pitch angle.

Figure 3: Coordinate system for the 3-DOF flight dynamics model.

###  2.2 Rotors

Blade-element-momentum (BEM) rotor models have been successfully included in
air-taxi trajectory optimization problems [32][9]. However, these BEM
implementations only guarantee accuracy for axial inflow velocities. Air-taxi
transition trajectories inherently contain large segments of edgewise flight
that result in large tangential inflow velocities. We account for this by
implementing the dynamic inflow rotor model developed by Pitt and Peters [33,
34]. The Pitt-Peters model accounts for edgewise flight with three inflow
states that represent the uniform, side-to-side, and fore-to-aft flow
variations respectively. These inflow parameters are combined with standard
blade element theory to compute thrust and moment coefficients ($C_{T}$,
$C_{M_{y}}$, and $C_{M_{x}}$). The thrust and power coefficients ($C_{T}$, and
$C_{P}$) in the rotor axes are found via a simple transformation of the thrust
and moment coefficients. To simplify the implementation of this rotor model,
we use surrogate models for $C_{T}$, and $C_{P}$. The surrogate models are
created with regularized minimal-energy tensor-product splines (RMTS) [35]
using the surrogate modeling toolbox (SMT) developed by Bouhlel et al. [28].
Figure 4 shows a subset of the surrogate models created for the cruise rotor.
Rotor thrust, torque, and power ($T$, $Q$, and $P$) are calculated using these
surrogate models and the rotor diameter $(d)$ (see $d_{C}$ and $d_{L}$ in
Table 1), rotations per second $(n)$, and the atmospheric density $(\rho)$
(computed from a standard atmosphere model):

$T=\rho n^{2}d^{4}C_{T}$ (5) $P=\rho n^{3}d^{5}C_{P}$ (6) $Q=\rho
n^{2}d^{5}C_{Q}.$ (7)

The torque coefficient $C_{Q}$ is found as a function of the power
coefficient: $C_{Q}=C_{P}/2\pi$. To compute the total aircraft power we sum
the individual rotor powers (with $k$ lifting rotors):
$P=P_{\text{Cruise}}+kP_{\text{Lift}}$. The total energy $E$ consumed by the
aircraft is expressed as an additional ordinary differential equation:
$\dot{E}=P$. The total energy used by the aircraft for a given trajectory is
the final entry in the resulting discrete-time energy vector.

Figure 4: Cruise rotor surrogate models for thrust and power coefficients
($C_{T}$ and $C_{P}$) as a function of axial and edgewise free-stream
velocity. Dots represent the training points for the model.

###  2.3 Aerodynamics

Aircraft aerodynamics are analyzed using standard lift and drag equations:
$L=\frac{1}{2}\rho v^{2}sC_{L}$ and $D=\frac{1}{2}\rho v^{2}sC_{D}$, where $s$
is the wing area (see Table 1 for aircraft specifications), and $\rho$ is the
atmospheric density computed, as above, from a standard atmospheric model. The
lift and drag coefficients ($C_{L}$ and $C_{D}$) are found in a surrogate
model that spans a wide range of angle of attack values ($\pm 90^{\circ}$)
(Figure 5). This is necessary since vertical flight near hover can result in
angles of attack that extend to $\pm 90^{\circ}$. These surrogate models are
constructed with radial basis functions (RBF) [36] using the SMT toolbox [28]
based in part on vortex lattice method analyses performed in OpenVSP [37] and
extrapolated to high $\alpha$ using computational fluid dynamics data from
Petrilli et al. [38] and experimental data presented by Sheldahl and Klimas
[39].

Figure 5:  The aerodynamic surrogate model for lift and drag coefficients. Table 1:  Lift-plus-Cruise aircraft specifications Parameter ($m$) | Value
---|---
Mass ($m$) | 3000 kg
Wing area ($s$) | $19.6\text{ m}^{2}$
Cruise / lift rotor diameters ($d_{C}$, $d_{L}$) | 2.6 m / 2.4 m
Number of lift rotors | 8
Cruise / lift rotor blades | 3 / 2

###  2.4 Motors

We account for the effects of motor efficiency by including a motor efficiency
map. We begin by calculating the basic motor geometry using a sizing model
based on empirical relationships [40]. These relationships represent the
internal motor geometry as a function of two high-level parameters: stator
diameter and motor length. Next, the outputs of the sizing model are inputs to
a second model, which calculates the motor efficiency map as a function of
load torque and motor speed by solving the following residual:
$r=\eta\tau_{EM}-\tau_{load}=0$.

The motor analysis model is formulated as an implicit function in order to
relate the unknown electromagnetic torque $\tau_{EM}$ and efficiency $\eta$ to
the load torque $\tau_{load}$. The motor power and current are calculated with
two discrete control modes: flux weakening [41] and maximum torque per ampere
[42]. These modes govern motor operation at the voltage limit ($V_{lim}=400$
V) and below the voltage limit respectively. We note that air-taxi motors are
not expected to operate in the flux-weakening regime, and we include this mode
entirely for model robustness. These models are used to generate motor
efficiency maps ( Figure 6). We train an RBF surrogate model to approximate
this map, with which we calculate the total power as a function of the ideal
rotor power $P=P_{r}/\eta$.

Figure 6: The motor efficiency map surrogate model: $\eta=f(\tau,n)$.

###  2.5 Trajectory Optimization

We begin by describing the trajectory optimization problem with an optimal
control representation in continuous time. The system dynamics are described
in a general form: $\dot{x}=f(t,x(t),u(t))$, and we aim to find control
profiles $u(t)$ that minimize a certain objective function
$J=\phi(t,x(t),u(t))$. The resulting state trajectories $x(t)$ must satisfy
certain path and terminal constraints ($c_{p}$ and $c_{t}$). The complete
optimal control representation is summarized as:

$\begin{array}[]{r l}\underset{u(t)}{\text{minimize}}&J=\phi(t,x(t),u(t))\\\
\text{subject to}&\dot{x}=f(t,x(t),u(t))\\\ &c_{p}(t,x(t),u(t))\leq 0\\\
&c_{t}(t_{f},x(t_{f}),u(t_{f}))=0.\\\ \end{array}$ (8)

We consider two objectives: energy and time. Energy is calculated as the
integral of total motor power $E=\int P(t,x(t),u(t))dt$, and time is
represented by the integrator time step $\Delta t$ where $t_{f}=N\Delta t$ for
$N$ time steps. Using direct transcription, we reformulate the continuous-time
optimal control problem in a discrete-time form for the minimum energy
objective:

$\begin{array}[]{r l l}\underset{\mathbf{u},\Delta
t}{\text{minimize}}&E=\sum_{t=0}^{t_{f}}P(x_{t},u_{t}),\forall\mathbf{t},\mathbf{x},\mathbf{u}\in\mathit{R}^{N+1}&\text{(objective
function)}\\\ \text{subject
to}&\dot{\mathbf{x}}=f(\mathbf{t},\mathbf{x}(t),\mathbf{u}(t))&\text{(system
dynamics)}\\\ &c_{p}(\mathbf{x},\mathbf{u})\leq 0&\text{(path constraints)}\\\
&c_{t}(\mathbf{x},\mathbf{u})=0&\text{(terminal constraints)}\\\
\text{with}&\mathbf{t}=[t_{i},t_{i}+\Delta t,t_{i}+2\Delta
t,\ldots,t_{i}+N\Delta t]&\text{(discrete time vector).}\\\ \end{array}$ (9)

For the minimum time objective, we minimize the time step $\Delta t$ instead
of the energy $E$ in (9). We consider three dynamic variables (vectorized
across time) as the inputs $u$: pitch angle, cruise rotor speed, and lift
rotor speed. We include a single scalar input: the integrator time step
$\Delta t$. Since the number of time steps is a fixed quantity $(N)$, $\Delta
t$ is effectively a method of adjusting the total time $t_{f}$.

The aircraft trajectories are simulated with a fourth-order Runge-Kutta
integration scheme using initial conditions that are derived from a steady
hovering condition at an initial altitude $h_{i}$ ($v_{0}=0.1$ m/s,
$\gamma_{0}=0^{\circ}$, $x_{0}=0\text{ m}$, and $h_{0}=h_{i}$), ($v_{0}$ is
slightly positive so that the flight-path angle remains defined). The maneuver
is considered complete when several terminal constraints are satisfied
($h_{f}$, $v_{f}$, and $\gamma_{f}$). Path constraints are comprised of a
variety of practical aircraft and trajectory limitations. For example, rotor
power is constrained by the maximum available power, and the minimum altitude
is constrained by ground collisions and no-fly zones. There are two
constraints motivated by passenger comfort. First, the pitch angle is
constrained to be less than $20^{\circ}$ (the typical airliner maximum pitch
angle during takeoff is approximately $20^{\circ}$ [43]). Second, we constrain
the maximum acceleration (in any direction) to be no greater than 0.5g, a
value determined by Gebhard [44] to be the maximum acceleration that
passengers can endure without discomfort. All path constraints are implemented
using maximum and minimum operators across time-instances in state vectors
(approximated with Kreisselmeier–Steinhauser (KS) functions [45]) in order to
reduce the total number of constraints and increase the optimization speed.
The complete optimization problem is summarized in Table 2.

In Section 3.3, we include a single obstacle constraint that enforces a no-fly
zone. The no-fly zone altitude is given by a function of the horizontal
position ($h_{NFZ}=h(x)$). This function is then used to construct a residual
$r=(h-h_{NFZ})$ which we constrain to always be greater than or equal zero.
This constraint is not mathematically rigorous because it is only enforceable
at the collocation points of the NLP, and the trajectory between these points
can violate the no-fly zone. However, in practice the collocation points are
close-enough together that this is not a significant limitation. This
constraint formulation allows us to rapidly evaluate different obstacle
geometries without changing the optimization problem. The obstacle function
$h_{NFZ}$ is constructed using radial basis functions in SMT [28]. This
provides the freedom to generate obstacles of nearly any smooth shape, which
in this paper consists of a sinusoidal ramp to a constant altitude (Figure
11).

Table 2:  Optimization problem formulation |  | Variable/Description |  Quantity ($N$ timesteps)
---|---|---|---
Objective | Energy or time |  $J=E,$ $\Delta t$ |
Design variables | Lift rotor speed | $n_{L}$ | $N$
| Cruise rotor speed | $n_{C}$ | $N$
| Pitch angle | $\theta$ | $N$
| Timestep | $\Delta t$ | 1
|  |  |  Total design variables: $(3N+1)$
Constraints | Maximum lift power | $\max{P_{L}}\leq 103,652\text{ W}$ | 1
| Maximum cruise power | $\max{P_{C}}\leq 468,300\text{ W}$ | 1
| Final altitude | $h_{f}=300\text{ m}$ | 1
| Minimum altitude | $\min{h}\geq 0\text{ m}$ | 1
| Maximum acceleration | $\max{|\dot{v}/g|}\leq 0.5\text{ g}$ | 1
| Maximum pitch angle | $\max{|\theta|}\leq 20^{\circ}$ | 1
| Final velocity | $v_{f}=58\text{ m/s}$ | 1
| Final flight path angle | $\gamma_{f}=0^{\circ}$ | 1
|  |  |  Total constraints: $8$
Other constraints | No-fly zone | $\min{(h-h_{NFZ})}\geq 0$ | 1

We solve the discretized optimization problem with gradient-based optimization
leveraging the automatic adjoint-based derivative computation enabled by our
use of CSDL. The computational expense of adjoint derivative computation
scales well with the number of design variables, and is well suited to large-
scale MDO. The optimizer is SNOPT-7.7 [46] (a sparse nonlinear optimizer),
which in most cases converges to an optimal solution within 30 minutes using a
desktop computer with an Intel i7-13700K processor and 32GB of memory. The
system is discretized with $N=40$ time steps, a number that is empirically
determined to provide sufficient resolution without unnecessary computation
time. This results in a nominal optimization problem with 121 design variables
and eight constraints.

Certain variables such as power are large (approx. $10^{6}$) while others are
small such as angle of attack (approx. $10^{-2}$). This leads to a poorly
conditioned problem that struggles to converge. We address this by scaling the
design variables, constraints, and the objective before optimization. For
variables that are roughly constant, we accomplish this by multiplying the
variable by the inverse of the expected value. Once properly scaled, we
converge all our results to an optimality and feasibility tolerance of
$10^{-8}$.

## 3 Results

Using the problem formulation described above, we now present optimal
transition trajectories for the minimum-energy and minimum-time objectives. We
characterize these trajectories by plotting the time histories of the system
states ($x$, $h$). To gain further insight, we also plot functions of the
states (e.g., power vs. time).

To facilitate comparisons between trajectories, we use a transition efficiency
parameter $\eta$ as defined by Chauhan and Martins [6]. This parameter
computes the ratio of the increase in mechanical energy (kinetic plus
potential energy) to the total energy consumed by the aircraft:

$\eta=(0.5m\Delta v^{2}+mg\Delta h)/E.$ (10)

This equation is equivalent to the ratio of the specific energies (energy per
unit mass), and enables comparisons between different trajectories and
different aircraft configurations.

###  3.1 Optimal Transition and Takeoff Trajectories

The first two trajectories that we explore are minimum-energy and minimum-time
transition. For these results, the aircraft begins at hover and must
transition to cruise at the same altitude. The key feature of these
trajectories is that the altitude is not fixed during transition; that is, the
aircraft is free to climb/dive to whatever extent is necessary to minimize the
objective function. The minimum energy and minimum time transition
trajectories are shown in Figure 7. In every figure that follows, the aircraft
markers are equally spaced with respect to time and the marker rotation
indicates the instantaneous pitch angle.

Figure 7: Top left: the minimum-energy transition trajectory. Top right: the
minimum-time transition trajectory. Bottom left: the power profiles for the
minimum-energy transition. Bottom right: the power profiles for the minimum-
time transition.

Each trajectory in Figure 7 exhibits distinctive behaviors. First we examine
the minimum-energy transition trajectory. This trajectory is characterized by
an initial dive, followed by a climb back to the initial altitude. By
following this path, the aircraft trades potential energy for kinetic energy
(by diving) and is able to switch to full wing-based lift as early as
possible. This minimizes any reliance on the lifting rotors, which are less
efficient at generating lift than the wing. Second, we examine the minimum-
time transition trajectory. This trajectory shows a rapid initial
acceleration, similar to how a conventional helicopter accelerates in a nose-
down configuration (with a negative pitch angle). However, a helicopter
accelerates in this way due to the balance of forces and moments. For the
Lift-plus-Cruise aircraft, this nose-down acceleration is the fastest way of
reaching the cruise velocity while maintaining enough lift to avoid large
excursions from the shortest path (a straight line).

Further comparisons between these two transition trajectories are evident by
plotting the time-histories of the cruise and lift rotor power (Figure 7).
Notably, the minimum-time transition trajectory uses near-maximum power for
all rotors for the full duration of the transition. The power never quite
reaches the maximum power constraint likely because the KS function (used to
aggregate the power vector into a single constraint) does not perfectly fit
the data. The power profiles for the minimum-energy transition show that the
lift rotors do very little. In fact, they are only used initially to slightly
arrest the descent in order to avoid violating the maximum acceleration
constraint. The cruise rotor power shows that initially maximum power is used
to reach a velocity at which the aircraft can rely on wing-based lift,
followed by a gradual climb at reduced power.

Next, we present two more trajectories that demonstrate the versatility of the
fast surrogate modeling approach (Figure 8). Both these trajectories have
additional constraints that mimic possible operating constraints for proposed
air-taxi missions. First, we find a minimum energy constant-altitude
transition trajectory. This includes one added constraint that the minimum
altitude cannot be less than the initial altitude. This trajectory is modeled
after the proposed mission profiles by Silva [4], which contain a constant-
altitude transition segment. Second, we model a complete takeoff (transition
plus climb) trajectory. We add two additional constraints: the altitude cannot
be less than zero to avoid ground collisions and the aircraft must reach
cruise conditions by 3 km.

Figure 8: Left: the constant-altitude, minimum-energy transition trajectory.
Right: the minimum-energy takeoff (transition plus climb) trajectory.

The constant-altitude transition trajectory in Figure 8 shows that the
aircraft pitches down initially, followed by a rapid pitch-up maneuver all by
500 m. In this case, the initial nose-down maneuver corresponds with the
lowest drag configuration which enables the most efficient acceleration. Once
the velocity becomes large enough, the aircraft pitches upwards to utilize
lift generated by the wing. As the velocity further increases, the pitch angle
can gradually reduce such that the lift matches the weight. The minimum energy
takeoff trajectory in Figure 8 includes a low-altitude acceleration followed
by a gradual climb. Similar to the other trajectories shown here, this
minimizes the use of the lifting rotors and maximizes the time spent in an
airplane-mode of flight. However, this trajectory is perhaps impractical
because it would require future air-taxi hubs to include a long, flat, and
unpopulated corridor within which an air taxi could perform the early
acceleration.

As before, we compare the time-histories of the lift and cruise rotor power
(Figure 8) to gain insight on the trajectories. Both of these trajectories
contain a nearly identical initial high-power acceleration. In fact, the only
noticeable difference is that the cruise rotor power for the takeoff
trajectory is higher during the latter half of the trajectory to sustain the
climb to 300 m altitude. The cruise rotor power for the constant-altitude
trajectory decreases gradually as the aircraft approaches the target cruise
speed.

Table 3:  Numerical results for the minimum-energy and minimum-time trajectories | Energy (MJ / Wh) | Time (s) | Efficiency (%)
---|---|---|---
Minimum-energy transition | 11.4 / 3167 | 67.2 | 47.4
Minimum-time transition | 28.1 / 7806 | 15.7 | 19.2
Minimum-energy constant-altitude transition | 27.0 / 7500 | 64.2 | 20.0
Minimum-time constant-altitude transition | 37.9 / 10528 | 22.1 | 14.2
Minimum-energy takeoff | 35.3 / 9806 | 62.0 | 27.8

The numerical data for the four trajectories presented in this section is
summarized in Table 3. For comparison Table 3 also includes a minimum-time
constant-altitude transition trajectory that is not shown in any figure
because it is visually the same in profile as the minimum-energy constant-
altitude transition in Figure 8.

###  3.2 Constrained Transition Trajectories

The optimal trajectories presented in Section 3.1 contain behaviors that are
not necessarily desirable for real-world air-taxi operations (e.g., the
minimum energy transition contains large altitude fluctuations and the
constant-altitude transition requires more than 3 km of horizontal distance).
In this section, we present results that show the sensitivity of the minimum-
energy transition trajectories to constraints on horizontal distance and
altitude.

Figure 9: Minimum-energy transition trajectories with horizontal displacement
constraints.

The trajectories in Figure 9 are variants of the minimum-energy transition
trajectory in Figure 7 with one additional constraint on the maximum allowable
horizontal position. These results show that the energy design space is
relatively flat with respect to this constraint. Constraining the aircraft to
transition within 1 km results in only 15% more energy consumption than the
original, unconstrained transition trajectory.

Next, we show minimum energy transition trajectories with altitude-loss
constraints in Figure 10. The original trajectory in Figure 7 is impractical
because it requires a high initial altitude (e.g., takeoff from the top of a
tall building). If this initial altitude is much lower, the optimal
trajectories will have a minimum altitude constraint like we show in Figure
10. As the altitude constraint becomes more aggressive we find that the energy
expenditure increases. Finally, as the constraint on altitude loss reaches 0
m, we recover the same constant-altitude transition trajectory from Figure 8.
This trajectory requires 138% more energy than the unconstrained trajectory.
Based on these results, it is evident that, if given the chance, minimum-
energy transition trajectories will exploit a trade of potential for kinetic
energy. A final observation is that the constant-altitude transition
trajectory requires more horizontal distance to reach cruise than either of
the trajectories with 50 m and 100 m altitude-loss constraints. This is
unexpected because there appears to be a trend of decreasing horizontal
distance with increasingly restrictive altitude-loss constraints. This
behavior is somewhat explained because the aircraft cannot dive to gain
velocity due to the constant-altitude constraint. Instead, it accelerates
horizontally and travels farther than expected.

Figure 10: Minimum-energy transition trajectories with altitude-loss
constraints.

###  3.3 Takeoff with a No-Fly Zone

The takeoff trajectory in Figure 8 contains low-altitude, high-speed flight
that may pose regulatory and safety issues for commercial UAM missions. In
this section we present a minimum-energy takeoff trajectory with a no-fly zone
constraint. We formulate this constraint to force a near-vertical liftoff,
followed by a transition and climb that must occur above 100 m. Because this
trajectory contains three distinct segments (liftoff, transition, and climb),
it represents a complete optimization of the pre-cruise portion of proposed
UAM mission profiles [5, 4]. The results of this optimization are shown in
Figure 11.

The minimum-energy takeoff trajectory in Figure 11 contains two additional
constraints: the minimum altitude must be greater than the no-fly zone and the
maximum horizontal displacement must be less than 3 km. Upon inspection, the
trajectory in Figure 11 is a composite of the constant-altitude transition
trajectory and the takeoff trajectory in Figure 8. The aircraft lifts off in
hover, and climbs to 100 m (tightly following the no-fly zone profile) using
the full power of both the lift rotors and the cruise rotor. This is followed
by a constant-altitude transition at 100 m and a steady climb to 300 m. The
addition of the no-fly zone requires 67% more energy than the unconstrained
takeoff trajectory (Figure 8) and requires ten more seconds to complete.
Because this trajectory is heavily constrained, the optimization problem
requires nearly two hours to converge to a solution.

Figure 11: Left: the minimum-energy takeoff trajectory with a no-fly zone
constraint. Right: the corresponding power time-histories for the minimum-
energy takeoff trajectory (left).

## 4 Conclusion

In this paper, we presented the results of 12 variants of the takeoff and
transition trajectory optimization problem for NASA’s Lift-plus-Cruise air-
taxi concept. These results demonstrate the versatility and robustness of the
fast surrogate modelling approach. This approach allows us to simulate
realistic air-taxi trajectories that are representative of real UAM missions.
The contribution of this paper is as follows: (a) we introduce a novel,
surrogate-based aircraft trajectory optimization framework, and (b) we present
optimal air-taxi transition and takeoff trajectories.

This study provides insight into the solution-space for the air-taxi
trajectory design problem. For example, we find that the Lift-plus-Cruise air
taxi can transition from hover to cruise in as little as 16 seconds; however,
this requires nearly 200% more energy than trajectories which complete the
transition in roughly 60 seconds. Many proposed air-taxi mission profiles
include a near-vertical liftoff followed by a transition to cruise at a
substantial altitude. This makes sense when considering these aircraft must
operate in or near urban areas. However, the takeoff trajectories presented
here shows that low-altitude transition uses 40% less energy than the
trajectories that include a vertical liftoff and a higher-altitude transition.
These examples are indicative of the trade-offs that air-taxi designers face
when considering commercial UAM operations.

We recognize certain limitations and/or assumptions in this work. The models
used are of low fidelity. Specifically, the aerodynamic model is incapable of
modeling any rotor-wing interactions, and the rotor model cannot model
negative axial inflow velocities. This means, among other things, that these
models can only be applied to forward transitions and takeoff trajectories
because the reverse (cruise to hover) transition could include regimes where
the rotors fly into their own wake.

Direct methods for solving trajectory optimization problems are notorious for
requiring good initial guesses for the control inputs. Without these, the
solution diverges or converges to sub-optimal local minima. The methods
presented here are also susceptible to these potential pitfalls. However, the
robustness of the surrogate models signifies that the optimizer can recover
from poor initial trajectories without encountering any numerical
difficulties.

## Acknowledgments

The material presented in this paper is, in part, based upon work supported by
NASA under award No. 80NSSC21M0070 and by DARPA under grant No. D23AP00028-00.

## References

## References

  * [1] Darshan Sarojini et al.  “Large-Scale Multidisciplinary Design Optimization of an eVTOL Aircraft using Comprehensive Analysis”  In _AIAA SCITECH 2023 Forum_ , 2023, pp. 0146  DOI: 10.2514/6.2023-0146
  * [2] Marius Ruh et al.  “Large-scale multidisciplinary design optimization of the NASA lift-plus-cruise concept using a novel aircraft design framework”  In _VFS_ , 2023  DOI: 10.48550/arXiv.2304.14889
  * [3] John T Hwang and Andrew Ning  “Large-scale multidisciplinary optimization of an electric aircraft for on-demand mobility”  In _2018 AIAA/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference_ , 2018, pp. 1384  DOI: 10.2514/6.2018-1384
  * [4] Christopher Silva et al.  “VTOL urban air mobility concept vehicles for technology development”  In _2018 Aviation Technology, Integration, and Operations Conference_ , 2018, pp. 3847  DOI: 10.2514/6.2018-3847
  * [5] Michael D Patterson, Kevin R Antcliff and Lee W Kohlman  “A proposed approach to studying urban air mobility missions including an initial exploration of mission requirements”  In _Annual Forum and Technology Display_ , 2018
  * [6] Shamsheer S Chauhan and Joaquim RRA Martins  “Tilt-wing eVTOL takeoff trajectory optimization”  In _Journal of aircraft_ 57.1 American Institute of AeronauticsAstronautics, 2020, pp. 93–112  DOI: 10.2514/1.C035476
  * [7] Ryan Anderson et al.  “A comparison of aerodynamics models for optimizing the takeoff and transition of a bi-wing tailsitter”  In _AIAA Scitech 2021 Forum_ , 2021, pp. 1008  DOI: 10.2514/6.2021-1008
  * [8] John T Betts  “Survey of numerical methods for trajectory optimization”  In _Journal of guidance, control, and dynamics_ 21.2, 1998, pp. 193–207  DOI: 10.2514/2.4231
  * [9] Shugo Kaneko and Joaquim RRA Martins  “Simultaneous Optimization of Conceptual Design and Takeoff Trajectory of a Lift-Plus-Cruise UAV”  In _10th Autonomous VTOL Technical Meeting_ Vertical Flight Society, 2023
  * [10] Matthew P. Kelly  “An introduction to trajectory optimization: How to do your own direct collocation”  In _SIAM Review_ 59.4 SIAM, 2017, pp. 849–904  DOI: 10.1137/16M1062569
  * [11] Matthew P Kelly  “Transcription methods for trajectory optimization: a beginners tutorial”  In _arXiv_ , 2017  DOI: 10.48550/arXiv.1707.00284
  * [12] Richard S Sutton and Andrew G Barto  “Reinforcement learning: An introduction”  MIT press, 2018, pp. 73–90
  * [13] Oskar Von Stryk and Roland Bulirsch  “Direct and indirect methods for trajectory optimization”  In _Annals of operations research_ 37 Springer, 1992, pp. 357–373  DOI: 10.1007/BF02071065
  * [14] Charles R Hargraves and Stephen W Paris  “Direct trajectory optimization using nonlinear programming and collocation”  In _Journal of guidance, control, and dynamics_ 10.4, 1987, pp. 338–342  DOI: 10.2514/3.20223
  * [15] Arthur Earl Bryson and Walter F Denham  “A steepest-ascent method for solving optimum programming problems”  In _Journal of Applied Mechanics_ The American Society of Mechanical Engineers (ASME), 1962  DOI: 10.1115/1.3640537
  * [16] John T Hwang and Drayton Munster  “Solution of ordinary differential equations in gradient-based multidisciplinary design optimization”  In _2018 AIAA/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference_ , 2018, pp. 1646  DOI: 10.2514/6.2018-1646
  * [17] Joaquim RRA Martins and John T Hwang  “Review and unification of methods for computing derivatives of multidisciplinary computational models”  In _AIAA journal_ 51.11 American Institute of AeronauticsAstronautics, 2013, pp. 2582–2599  DOI: 10.2514/1.J052184
  * [18] John T Hwang and Joaquim RRA Martins  “A computational architecture for coupling heterogeneous numerical models and computing coupled derivatives”  In _ACM Transactions on Mathematical Software (TOMS)_ 44.4 ACM New York, NY, USA, 2018, pp. 1–39  DOI: 10.1145/3182393
  * [19] Lars Blackmore, Behçet Açikmeşe and Daniel P Scharf  “Minimum-landing-error powered-descent guidance for Mars landing using convex optimization”  In _Journal of guidance, control, and dynamics_ 33.4, 2010, pp. 1161–1171  DOI: 10.2514/1.47202
  * [20] John T Betts and Evin J Cramer  “Application of direct transcription to commercial aircraft trajectory optimization”  In _Journal of Guidance, Control, and Dynamics_ 18.1, 1995, pp. 151–159  DOI: 10.2514/3.56670
  * [21] John T Betts  “Practical methods for optimal control and estimation using nonlinear programming”  SIAM, 2010
  * [22] Charles Hargraves, Forrester Johnson, Stephen Paris and Ian Retties  “Numerical computation of optimal atmospheric trajectories”  In _Journal of Guidance and Control_ 4.4, 1981, pp. 406–414  DOI: 10.2514/3.56093
  * [23] Robert D Falck et al.  “Trajectory optimization of electric aircraft subject to subsystem thermal constraints”  In _18th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference_ , 2017, pp. 4002  DOI: 10.2514/6.2017-4002
  * [24] Pramudita Satria Palar, Rhea Patricia Liem, Lavi Rizki Zuhal and Koji Shimoyama  “On the use of surrogate models in engineering design optimization and exploration: The key issues”  In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , 2019, pp. 1592–1602  DOI: 10.1145/3319619.3326813
  * [25] Xiaosong Du, Ping He and Joaquim RRA Martins  “Rapid airfoil design optimization via neural networks-based parameterization and surrogate modeling”  In _Aerospace Science and Technology_ 113 Elsevier, 2021, pp. 106701  DOI: 10.1016/j.ast.2021.106701
  * [26] Yolanda Mack, Tushar Goel, Wei Shyy and Raphael Haftka  “Surrogate model-based optimization framework: a case study in aerospace design”  In _Evolutionary computation in dynamic and uncertain environments_ Springer, 2007, pp. 323–342  DOI: 10.1007/978-3-540-49774-5˙14
  * [27] Daniel L Clark Jr, Darcy L Allison, Harok Bae and Edwin E Forster  “Effectiveness-based design of an aircraft considering mission uncertainties”  In _Journal of Aircraft_ 56.5 American Institute of AeronauticsAstronautics, 2019, pp. 1961–1972  DOI: 10.2514/1.C035402
  * [28] Mohamed Amine Bouhlel et al.  “A Python surrogate modeling framework with derivatives”  In _Advances in Engineering Software_ , 2019, pp. 102662  DOI: https://doi.org/10.1016/j.advengsoft.2019.03.005
  * [29] Paul Saves et al.  “SMT 2.0: A Surrogate Modeling Toolbox with a focus on Hierarchical and Mixed Variables Gaussian Processes”  In _arXiv_ , 2023  DOI: 10.48550/arXiv.2305.13998
  * [30] Wayne Johnson, Christopher Silva and Eduardo Solis  “Concept vehicles for VTOL air taxi operations”  In _AHS Specialists”Conference on Aeromechanics Design for Transformative Vertical Flight_ , 2018
  * [31] Victor Gandarillas et al.  “A graph-based methodology for constructing computational models that automates adjoint-based sensitivity analysis”  In _Structural and Multidisciplinary Optimization_ StructuralMultidisciplinary Optimization, 2023
  * [32] Nicholas C Orndorff and John T Hwang  “Investigation of Optimal Air-Taxi Transition Profiles using Direct-Transcription Trajectory Optimization”  In _AIAA AVIATION 2022 Forum_ , 2022, pp. 3485  DOI: 10.2514/6.2022-3485
  * [33] Dale Marvin Pitt  “Rotor dynamic inflow derivatives and time constants from various inflow models”  Washington University in St. Louis, 1980
  * [34] Dale M Pitt  “Theoretical prediction of dynamic inflow derivatives”  In _Vertica_ 5, 1981, pp. 21–34
  * [35] John T Hwang and Joaquim RRA Martins  “A fast-prediction surrogate model for large datasets”  In _Aerospace Science and Technology_ 75 Elsevier, 2018, pp. 74–87  DOI: 10.1016/j.ast.2017.12.030
  * [36] Martin Dietrich Buhmann  “Radial basis functions”  In _Acta numerica_ 9 Cambridge university press, 2000, pp. 1–38  DOI: 10.1080/00107510903372134
  * [37] Robert A. McDonald and James R. Gloudemans  “Open Vehicle Sketch Pad: An Open Source Parametric Geometry and Analysis Tool for Conceptual Aircraft Design”  In _AIAA SCITECH 2022 Forum_ , 2022  DOI: 10.2514/6.2022-0004
  * [38] Justin L Petrilli, Ryan C Paul, Ashok Gopalarathnam and Neal T Frink  “A CFD database for airfoils and wings at post-stall angles of attack”  In _31st AIAA applied aerodynamics conference_ , 2013, pp. 2916  DOI: 10.2514/6.2013-2916
  * [39] Robert E Sheldahl and Paul C Klimas  “Aerodynamic characteristics of seven symmetrical airfoil sections through 180-degree angle of attack for use in aerodynamic analysis of vertical axis wind turbines”, 1981  DOI: 10.2172/6548367
  * [40] Nan Hnin Hnin Htwe  “Design of 50 kw Permanent Magnet Synchronous Motor for HEV”  In _IRE_ 3, 2019
  * [41] Dongyun Lu and Narayan C Kar  “A review of flux-weakening control in permanent magnet synchronous machines”  In _2010 IEEE Vehicle Power and Propulsion Conference_ , 2010, pp. 1–6  IEEE  DOI: 10.1109/VPPC.2010.5728986
  * [42] SF Zhao, XY Huang, YT Fang and J Li  “A control scheme for a High Speed Railway traction system based on high power PMSM”  In _2015 6th International Conference on Power Electronics Systems and Applications (PESA)_ , 2015, pp. 1–8  IEEE  DOI: 10.1109/PESA.2015.7398905
  * [43] I Wakefield and C Dubuque  “Exceeding tire speed rating during takeoff”  In _Boeing AERO Quarterly_ , 2009
  * [44] JW Gebhard  “Acceleration and comfort in public ground transportation”  In _The National Academies of Sciences, Engineering, and Medicine_ , 1970
  * [45] G Kreisselmeier and R Steinhauser  “Systematic control design by optimizing a vector performance index”  In _Computer aided design of control systems_ Elsevier, 1980, pp. 113–117  DOI: 10.1016/S1474-6670(17)65584-8
  * [46] Philip E Gill, Walter Murray and Michael A Saunders  “SNOPT: An SQP algorithm for large-scale constrained optimization”  In _SIAM review_ 47.1 SIAM, 2005, pp. 99–131  DOI: 10.1137/S0036144504446096


2320211116956

# Wiener index in graphs with given minimum degree and maximum degree

Alex Alochukwu1 The results of this paper form part of the first authors PhD
thesis. Financial support by the University of Johannesburg Peter Dankelmann1
Financial support by the South African National Research Foundation, grant
118521, is gratefully acknowledged. University of Johannesburg, South Africa

(2020-12-03; 2021-04-15; 2021-04-19)

###### Abstract

Let $G$ be a connected graph of order $n$. The Wiener index $W(G)$ of $G$ is
the sum of the distances between all unordered pairs of vertices of $G$. In
this paper we show that the well-known upper bound
$\big{(}\frac{n}{\delta+1}+2\big{)}{n\choose 2}$ on the Wiener index of a
graph of order $n$ and minimum degree $\delta$ [M. Kouider, P. Winkler, Mean
distance and minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improved
significantly if the graph contains also a vertex of large degree.
Specifically, we give the asymptotically sharp bound
$W(G)\leq{n-\Delta+\delta\choose 2}\frac{n+2\Delta}{\delta+1}+2n(n-1)$ on the
Wiener index $W(G)$ of a graph $G$ of order $n$, minimum degree $\delta$ and
maximum degree $\Delta$. We prove a similar result for triangle-free graphs,
and we determine a bound on the Wiener index of $C_{4}$-free graphs of given
order, minimum and maximum degree and show that it is, in some sense, best
possible.

###### keywords:

Wiener index; average distance; mean distance; total distance; maximum degree;
minimum degree MSC-class: 05C12

##  1 Introduction

Let $G$ be a connected graph. The _Wiener index_ $W(G)$ of $G$ is defined as
the sum of the distances between all unordered pairs of vertices of $G$, i.e.,

$W(G)=\sum_{\\{u,v\\}\subseteq V(G)}d_{G}(u,v),$

where $V(G)$ denotes the vertex set of $G$ and $d_{G}(u,v)$ is the usual
distance between $u$ and $v$. A closely related graph invariant is the
_average distance_ $\mu(G)$ of $G$, defined as

$\mu(G)={|V(G)|\choose 2}^{-1}\sum_{\\{u,v\\}\subseteq V(G)}d_{G}(u,v).$

$W(G)$ and $\mu(G)$ differ by a factor of ${n\choose 2}$ if $n$ is the order
of $G$. For graphs of given order, these two invariants are thus essentially
interchangeable. The Wiener index was originally introduced as a tool in
chemistry, while the average distance is a useful tool for the analysis of
networks in mathematics and computer science since it is an indicator for the
expected distance between two randomly chosen points in a network.

The natural question which connected graph maximises the Wiener index among
all connected graphs of given order was answered, for example, in a classical
paper by Plesní k (1984). We find it convenient to state his result in terms
of average distance.

###### Proposition 1

If $G$ is a connected graph with $n$ vertices, then

$\mu(G)\leq\frac{n+1}{3},$

with equality if and only if $G$ is a path.

Much research has been devoted to improving the bound in Proposition 1. A
natural approach is to consider not only the order of a graph, but also the
degrees of the vertices. The _degree_ ${\rm deg}_{G}(v)$ of a vertex $v$ in
$G$ is the number of vertices adjacent to $v$. The _minimum degree_
$\delta(G)$ and _maximum degree_ $\Delta(G)$ is the smallest and largest
degree of the vertices in $G$, and a $\delta$-_regular_ graph is one in which
all vertices have degree $\delta$.

In response to a conjecture by the computer programme GRAFFITI Fajtlowicz and
Waller (1987), which states that in a $\delta$-regular graph of order $n$ the
average distance is bounded from above by $\frac{n}{\delta}$, Kouider and
Winkler (1997) proved that for every connected graph $G$ of order $n$ and
minimum degree $\delta$,

$\mu(G)\leq\frac{n}{\delta+1}+2,$ (1)

and this bound is sharp apart from an additive constant. Improved bounds for
triangle-free and $C_{4}$-free graphs were given in Dankelmann and Entringer
(2000), and for graphs not containing a complete bipartite graph $K_{3,3}$ as
a subgraph in Dankelmann et al. (2005). Beezer et al. (2001) slightly
strengthened 1 by taking into account also the number of edges, and thus
proved the above-mentioned conjecture. In Dankelmann (2006), the maximum
average distance of a graph in terms of order, minimum degree and size was
determined up to an additive constant.

It is easily shown that the above-mentioned GRAFFITI conjecture
$\mu\leq\frac{n}{\delta}$ for $\delta$-regular graphs cannot be generalised to
graphs that are not necessarily regular by replacing $\delta$ by the
arithmetic mean of the vertex degrees. However, the question whether replacing
$\delta$ by the harmonic mean of the vertex degrees yields a valid inequality,
i.e., the question if the inequality $\mu(G)\leq\sum_{v\in V(G)}\frac{1}{{\rm
deg}(v)}$ holds for every connected graph was answered in the negative by
Erdös et al. (1988), who showed that this conjecture becomes a true inequality
if the right hand side is multiplied by a term $O(\frac{\log n}{\log\log n})$.

Bounds on the Wiener index of trees in terms of vertex degree have also been
considered extensively. Every tree has minimum degree $1$, so it is natural to
ask how large or small the Wiener index can be in trees of given maximum
degree. Answering this question for the maximum value of the Wiener index is
fairly straightforward (see Plesní k (1984) and Stevanović (2008)), however
determining the minimum Wiener index requires more effort Fischermann et al.
(2002). For the more general problem of determining the extremal values on the
Wiener index of a tree with given degree sequence see, for example, Cela et
al. (2011), Schmuck et al. (2012) and Wang (2008). Trees in which all vertices
have odd degree were considered, for example, in Lin (2013) and Furtula
(2013).

A bound on the Wiener index of the strong product of graphs with given minimum
degree was derived in Casablanca and Dankelmann (2019). Sharp bounds on the
Wiener index of maximal $k$-degenerate graphs, i.e., graphs that are edge-
maximal with the property that every subgraph has a vertex of degree at most
$k$, were given by Bickle and Che (2021). The Wiener index of Eulerian
digraphs of given minimum degree was considered in Dankelmann (2019). For
further questions and results on the Wiener index of digraphs we refer the
reader to Knor et al. (2016a), Knor et al. (2016b) and the classical paper
Plesní k (1984). We mention two further noteworthy recent papers Mukwembi
(2014); Klavz̆ar and Nadjafi-Arani (2014) on the Wiener index.

The graphs that demonstrate that 1 is sharp apart from an additive constant
are either regular or close to regular, and this applies also to the
corresponding bounds for triangle-free graphs in Dankelmann and Entringer
(2000). This suggests that stronger bounds hold for graphs of given minimum
degree that contain a vertex whose degree is significantly larger, for example
if the maximum degree is $cn$, where $c\in(0,1)$ and $n$ is the order of the
graph. The aim of this paper is to show that this is indeed the case and to
determine upper bounds on the Wiener index or average distance of graphs in
terms of order, minimum degree and maximum degree that are sharp apart from an
additive constant. We note that similar bounds for the average eccentricity
were given in Dankelmann and Osaye (2020).

This paper is organised as follows. In Section 2 we define the most important
terms and the notation used in this paper. Section 3 defines the weighted
versions of the average distance and the Wiener index, and gives a result
which will be crucial to the proofs of our main results. In Section 4 we
determine, apart from an additive constant, the maximum Wiener index and
average distance of a graph of given order, minimum degree and maximum degree.
A corresponding result for triangle-free graphs is given in Section 5. We
consider graphs not containing a $4$-cycle as a subgraph in Section 6. In the
concluding Section 7 we pose an open problem arising from our investigations.

##  2 Terminology and Notation

The notation we use is as follows. We denote the vertex set and edge set of a
graph $G$ by $V(G)$ and $E(G)$, respectively, and $n(G)$ stands for the order
of $G$, i.e., for the number of vertices of $G$. The _neighbourhood_ of a
vertex $v$, i.e., the set of all vertices adjacent to $v$, is denoted by
$N_{G}(v)$ and its elements are the _neighbours_ of $v$. The _closed
neighbourhood_ of $v$ is the set $N_{G}(v)\cup\\{v\\}$, denoted by $N_{G}[v]$,
and the _second neighbourhood_ of $v$ is the set $\\{u\in V(G)\ |\
d_{G}(v,u)\leq 2\\}$, which we denote by $N_{\leq 2}(v)$.

If $A\subseteq V(G)$, then we write $G[A]$ for the subgraph of $G$ induced by
$A$, i.e., the subgraph of $G$ whose vertex set is $A$ and in which two
vertices are adjacent if and only if they are adjacent in $G$. The _line
graph_ of a graph $G$ is the graph $L$ whose vertex set is $E(G)$, with two
vertices of $L$ being adjacent in $L$ if, as edges of $G$, they share a
vertex. The $k$-th _power_ of $G$, denoted by $G^{k}$, is the graph with the
same vertex set as $G$ in which two vertices are adjacent if their distance is
not more than $k$.

A _$k$ -packing_ of $G$ is a set $A$ of vertices in which the distance between
any two vertices of $A$ is greater than $k$. A $2$-packing is often referred
to as a _packing_. A _matching_ of $G$ is a set of edges in which no two edges
share a vertex. The vertex set $V(M)$ of a matching $M$ is the set of vertices
incident with an edge in $M$. The _distance_ $d_{G}(e_{1},e_{2})$ between two
edges $e_{1}$ and $e_{2}$ is the smallest of the distances between a vertex
incident with $e_{1}$ and a vertex incident with $e_{2}$. (Note that in
general this is not equal to the distance in the line graph of $G$.) If $M$ is
a set of edges, then the distance $d(e,M)$ between an edge $e$ and $M$ is the
smallest of the distances between $e$ and the edges in $M$.

A _star_ is a tree that has one vertex which is adjacent to all other
vertices. A _double-star_ is a tree that has two vertices such that each of
the other vertices is adjacent to exactly one of them. By a triangle we mean
the complete graph on three vertices, and a graph is _triangle-free_ if it
does not contain a triangle as a subgraph. The cycle on $4$-vertices is
denoted by $C_{4}$, and we say a graph is $C_{4}$-free if it does not contain
$C_{4}$ as a subgraph. We note that some authors use the term $C_{4}$-free to
mean that $C_{4}$ is not an _induced_ subgraph, while we exclude $C_{4}$ as a
subgraph, irrespective whether it is induced or not.

##  3 Weighted Wiener index and average distance

In this section we recall the definitions of weighted versions of the Wiener
index and the average distance, as well as a bound on the weighted average
distance which is used in the proofs of our main theorems. Both were given in
Dankelmann and Entringer (2000); Klavz̆ar and Gutman (1997).

###### Definition 1

Let $G$ be a connected graph with weight function
$c:V(G)\rightarrow\reals^{\geq 0}$. Then the Wiener index of $G$ with respect
to $c$ is defined as

$W_{c}(G)=\sum_{\\{u,v\\}\subseteq V(G)}c(u)c(v)d(u,v).$

Let $N=\sum_{v\in V(G)}c(v)$. If $N>1$, then we define the average distance of
$G$ with respect to $c$ as

$\mu_{c}(G)={N\choose 2}^{-1}\sum_{\\{u,v\\}\subseteq V(G)}c(u)c(v)d(u,v).$

We note that the constant weight function $c$ with $c(v)=1$ for all $v\in
V(G)$ yields the usual Wiener index and average distance.

###### Lemma 1

Let $G$ be a connected graph with weight function
$c:V(G)\rightarrow\reals^{\geq 0}$ and let $k,N$ be two positive integers, $N$
a multiple of $k$, such that $c(v)\geq k$ for every vertex $v$ of $G$ and
$\sum_{v\in V(G)}c(v)\leq N$. Then

$\mu_{c}(G)\leq\frac{N-k}{N-1}\frac{N+k}{3k}.$

Equality holds if and only if $G$ is a path and $c(v)=k$ for every $v\in V$.

##  4 A bound involving the maximum degree

In this section we prove our first main result, an upper bound on the Wiener
index of graphs of given order, minimum degree and maximum degree. We state
our result in terms of the average distance and not the Wiener index as this
is more convenient for the proof.

###### Theorem 1

Let $G$ be a connected graph of order $n$, minimum degree $\delta\geq 3$ and
maximum degree $\Delta$. Then

$\mu(G)\leq\frac{N(N-1)}{n(n-1)}\frac{n+2\Delta}{\delta+1}+4,$

where $N=n-\Delta+\delta$, and this bound is sharp apart from an additive
constant.

######  Proof 4.2.

We first find a packing $A$ of $G$ as follows. Choose a vertex $v_{1}$ of
degree $\Delta$ in $G$ and let $A=\\{v_{1}\\}$. If there exists a vertex
$v_{2}$ of $G$ at distance exactly $3$ from $A$, then add $v_{2}$ to $A$ and
let $A=\\{v_{1},v_{2}\\}$. If there exists a vertex $v_{3}$ at distance
exactly $3$ from $A=\\{v_{1},v_{2}\\}$, then add also $v_{3}$ to $A$. Repeat
this step, i.e., successively add vertices at distance $3$ from $A$ until,
after $k$ steps say, each vertex of $G$ is within distance $2$ of $A$. Then
$A=\\{v_{1},v_{2},\ldots,v_{k}\\}$.

By the construction of $A$, the sets $N[v_{i}]$ are pairwise disjoint for
$i=1,2,\ldots,k$. For $i=1,2,\ldots,k$ let $T(v_{i})$ be the star with vertex
set $N[v_{i}]$ centred at $v_{i}$. The disjoint union
$\bigcup_{i=1}^{k}T(v_{i})$ forms a subforest $T_{1}$ of $G$. It follows from
the construction of $A$ that for every $i\in\\{2,3,\ldots,k\\}$ there exists
an edge $e_{i}$ in $G$ joining a vertex in $T(v_{i})$ to a vertex in
$T(v_{j})$ for some $j$ with $1\leq j<i$. Hence
$T_{2}:=T_{1}+\\{e_{2},e_{3},\ldots,e_{k}\\}$ is a subtree of $G$. By the
maximality of $A$ every vertex of $G$ not in $T_{2}$ is adjacent to some
vertex of $T_{2}$. Hence we can extend $T_{2}$ to a spanning tree of $G$ by
adding each vertex in $V(G)-V(T_{2})$ to $T_{2}$ and joining it to some vertex
of $T_{2}$ with an edge of $G$. Denote the resulting spanning tree of $G$ by
$T$.

Since the average distance of any spanning tree of $G$ is not less than the
average distance of $G$, it suffices to show that

$\mu(T)\leq\frac{n-\Delta+\delta}{n}\frac{n-\Delta+\delta-1}{n-1}\frac{n+2\Delta}{\delta+1}+4.$
(2)

The tree $T$ can be thought of as a weighted tree, where each vertex has
weight exactly $1$. Informally speaking, we now move the weight of every
vertex to the closest vertex in $A$. More precisely, for every vertex $u\in
V(T)$ let $u_{A}$ be a vertex in $A$ closest to $u$ and define a weight
function $c:V(T)\rightarrow\reals^{\geq 0}$ by

$c(v)=|\\{u\in V(T)\ |\ u_{A}=v\\}|.$

If $v\in A$, then every $u\in N[v]$ satisfies $u_{A}=v$, hence $c(v)\geq{\rm
deg}_{G}(v)+1$. Thus $c(v_{1})\geq\Delta+1$ and $c(v_{i})\geq\delta+1$ if
$i\in\\{2,3,\ldots,k\\}$. If $v\in V(G)-A$, then $c(v)=0$. We also note that
$\sum_{v\in V(T)}c(v)=n$. This yields $n=\sum_{v\in
A}c(v)\geq\Delta+1+(k-1)(\delta+1)$, and so

$k\leq\frac{n-\Delta+\delta}{\delta+1}.$ (3)

In our proof we consider $\mu_{c}(T)$ rather than $\mu(T)$. Informally, the
difference between these two values is not more than $4$ since no weight was
moved over a distance of more than $2$, so no distance between two weights has
changed by more than $4$. More formally,

$\displaystyle\mu(T)$ $\displaystyle=$ $\displaystyle{n\choose
2}^{-1}\sum_{\\{u,v\\}\subseteq V(T)}d_{T}(u,v)$ $\displaystyle=$
$\displaystyle{n\choose 2}^{-1}\Big{(}\sum_{\\{u,v\\}\subseteq
V(T)}d_{T}(u_{A},v_{A})+\sum_{\\{u,v\\}\subseteq
V(T)}\big{(}d_{T}(u,v)-d_{T}(u_{A},v_{A})\big{)}\Big{)}$ $\displaystyle=$
$\displaystyle\mu_{c}(T)+{n\choose 2}^{-1}\sum_{\\{u,v\\}\subseteq
V(T)}\Big{(}d_{T}(u,v)-d_{T}(u_{A},v_{A})\Big{)},$

and thus, since $d_{T}(u,v)-d_{T}(u_{A},v_{A})\leq
d_{T}(u,u_{A})+d_{T}(v,v_{A})\leq 4$ for all $u,v\in V(T)$, we have

$\mu(T)\leq\mu_{c}(T)+4.$ (4)

We note that only the vertices in $A$ have a nonzero weight. By the
construction of $T$, each vertex $v_{i}\in A$, $i\geq 2$, is at distance
exactly three in $T$ from some vertex $v_{j}\in A$ with $j<i$. This implies
that in the graph $T^{3}[A]$ there is a path from every vertex to $v_{1}$, and
so $T^{3}[A]$ is connected. Let $H=T^{3}[A]$. Then $d_{T}(u,v)\leq
3d_{H}(u,v)$ for all $u,v\in A$, and so

$\mu_{c}(T)\leq 3\mu_{c}(H).$ (5)

We modify the weight function $c$ to obtain a new weight function $c^{\prime}$
on $A$ which satisfies $c^{\prime}(v)\geq\delta+1$ for all $v\in A$. We let

$c^{\prime}(v)=\left\\{\begin{array}[]{cc}c(v)-\Delta+\delta&\textrm{if
$v=v_{1}$,}\\\ c(v)&\textrm{if $v\in A-\\{v_{1}\\}$}.\end{array}\right.$

Since ${\rm deg}_{G}(v)=\Delta$ if $v=v_{1}$ and ${\rm deg}_{G}(v)\geq\delta$
if $v\in A-\\{v_{1}\\}$, we have $c^{\prime}(v)\geq\delta+1$ for all $v\in A$.
Let $N:=\sum_{v\in A}c^{\prime}(v)$, so $N=n-\Delta+\delta$.

We now express $\mu_{c}(H)$ in terms of $\mu_{c^{\prime}}(H)$. We have

$\displaystyle{N\choose 2}\mu_{c^{\prime}}(H)$ $\displaystyle=$ $\displaystyle
W_{c^{\prime}}(H)$ $\displaystyle=$ $\displaystyle\sum_{\\{u,v\\}\subseteq
A-\\{v_{1}\\}}c(u)c(v)d_{H}(u,v)$ $\displaystyle+\sum_{u\in\subseteq
A-\\{v_{1}\\}}(c(v_{1})-\Delta+\delta)c(u)d_{H}(u,v_{1})$ $\displaystyle=$
$\displaystyle\sum_{\\{u,v\\}\subseteq A}c(u)c(v)d_{H}(u,v)$
$\displaystyle-(\Delta-\delta)\sum_{u\in\subseteq
A-\\{v_{1}\\}}c(u)d_{H}(u,v_{1})$ $\displaystyle=$ $\displaystyle
W_{c}(H)-(\Delta-\delta)\sum_{u\in A-\\{v_{1}\\}}c(u)d_{H}(u,v_{1}).$

Expressing $W_{c}(H)$ as ${n\choose 2}\mu_{c}(H)$ and rearranging yields

$\mu_{c}(H)=\frac{N(N-1)}{n(n-1)}\mu_{c^{\prime}}(H)+\frac{2(\Delta-\delta)}{n(n-1)}\sum_{u\in
A-\\{v_{1}\\}}c(u)d_{H}(u,v_{1}).$ (6)

We bound the two terms of the right hand side of 6 separately. Renaming the
vertices of $A-\\{v_{1}\\}$ as $u_{1},u_{2},\ldots,u_{k-1}$ such that
$d_{H}(v_{1},u_{1})\leq d_{H}(v_{1},u_{2})\leq\ldots\leq
d_{H}(v_{1},u_{k-1})$, we have $d_{H}(v_{1},u_{i})\leq i$ and so

$\sum_{u\in A-\\{v_{1}\\}}c(u)d_{H}(u,v_{1})\leq\sum_{i=1}^{k-1}c(u_{i})\,i.$
(7)

Now $c(u_{i})\geq\delta+1$ for $i=1,2,\ldots,k-2$ and
$\sum_{i=1}^{k-1}c(u_{i})=n-c(v_{1})\leq n-\Delta-1$. Subject to these
conditions the right hand side of 7 is maximised if
$c(u_{1})=c(u_{2})=\ldots=c(u_{k-2})=\delta+1$ and
$c(u_{k-1})=n-\Delta-1-(k-2)(\delta+1)$. Substituting these values yields,
after simplification,

$\sum_{i=1}^{k-1}c(u_{i})\,i\leq(n-\Delta-1)(k-1)-\frac{1}{2}(\delta+1)(k-1)(k-2).$
(8)

Since $k\leq\frac{n-\Delta+\delta}{\delta+1}$ by 3, and since the right hand
side is increasing in $k$ for $k\leq\frac{n-\Delta+\delta}{\delta+1}$, we
obtain by substituting this value and combining 7 and 8 that

$\sum_{u\in
A-\\{v_{1}\\}}c(u)d_{H}(u,v_{1})\leq\frac{(n-\Delta-1)^{2}}{2(\delta+1)}+\frac{n-\Delta-1}{2}.$

Since
$\frac{(n-\Delta-1)^{2}}{2(\delta+1)}+\frac{n-\Delta-1}{2}=\frac{(n-\Delta-1)(n-\Delta+\delta)}{2(\delta+1)}\leq\frac{N(N-1)}{2(\delta+1)}$,
this implies that

$\sum_{u\in A-\\{v_{1}\\}}c(u)d_{H}(u,v_{1})\leq\frac{(N-1)N}{2(\delta+1)}.$
(9)

To bound $\mu_{c^{\prime}}(H)$ we recall that $c^{\prime}(v)\geq\delta+1$ for
all vertices $v$ of $H$ and that $\sum_{v\in A}c^{\prime}(v)=n-\Delta+\delta$.
Let $C$ be the least multiple of $\delta+1$ with $C\geq N$. By Lemma 1 we have

$\mu_{c^{\prime}}(H)\leq\frac{C-\delta-1}{C-1}\frac{C+\delta+1}{3(\delta+1)}\leq\frac{C+1}{3(\delta+1)}.$

Since $C\leq N+\delta$, this yields

$\mu_{c^{\prime}}(H)\leq\frac{N+\delta+1}{3(\delta+1)}.$ (10)

Substituting 9 and 10 into 6 yields

$\displaystyle\mu_{c}(H)$ $\displaystyle\leq$
$\displaystyle\frac{N(N-1)}{n(n-1)}\frac{N+\delta+1}{3(\delta+1)}+\frac{2(\Delta-\delta)}{n(n-1)}\frac{N(N-1)}{2(\delta+1)}$
(11) $\displaystyle\leq$
$\displaystyle\frac{N(N-1)}{n(n-1)}\frac{n+2\Delta}{3(\delta+1)}.$

Combining the inequalities 4, 5 and 11 we obtain that

$\displaystyle\mu(T)$ $\displaystyle\leq$ $\displaystyle\mu_{c}(T)+4$
$\displaystyle\leq$ $\displaystyle 3\mu_{c}(H)+4$ $\displaystyle\leq$
$\displaystyle\frac{N(N-1)}{n(n-1)}\frac{n+2\Delta}{\delta+1}+4,$

which is 2, and so the bound in the theorem follows.

To show that the above bound is sharp apart from an additive constant we
consider the following graph for given $n,\Delta,\delta\in\naturals$ for which
$\Delta\geq\delta$ and $n\geq\Delta+\delta+1$. In order to keep our
calculations simple we assume that $n-\Delta$ is a multiple of $\delta+1$, but
we note that a similar construction, with slightly more labourious
calculations, can be done without this additional assumption. Let
$\ell=\frac{n-\Delta+\delta+1}{\delta+1}$. Let $G_{1}$ be a copy of the
complete graph $K_{\Delta}$, let $G_{2},G_{3},\ldots,G_{\ell}$ be disjoint
copies of $K_{\delta+1}$. For $i=1,2,\ldots,\ell$ let $u_{i}$ and $v_{i}$ be
two vertices of $G_{i}$. Define $G_{n,\Delta,\delta}$ to be the graph obtained
from $\bigcup_{i=1}^{\ell}G_{i}$ by deleting the edge $u_{i}v_{i}$ for
$i=2,3,\ldots,\ell-1$ and adding the edge $v_{i}u_{i+1}$ for
$i=1,2,\ldots,\ell-1$. The graph $G_{28,8,3}$ is shown in Figure 1.

$G_{6}$$G_{5}$$G_{4}$$G_{3}$$G_{2}$$G_{1}$ Figure 1: The graph $G_{28,8,3}$

It is easy to verify that $G_{n,\Delta,\delta}$ is a connected graph of order
$n$, maximum degree $\Delta$ and minimum degree $\delta$.

We now bound the average distance of $G_{n,\Delta,\delta}$ from below. For
$i=1,2,\ldots,\ell$ let $V_{i}=V(G_{i})$. Then $|V_{i}|=\delta+1$ for
$i=2,3,\ldots,\ell$, and $|V_{1}|=\Delta$. For our lower bound we only count
the distances between pairs $x,y$ with either $x\in V_{i}$ and $y\in V_{j}$
where $2\leq i<j\leq\ell$, or $x\in V_{1}$ and $y\in V_{j}$ for
$j=2,3,\ldots,\ell$, ignoring all other pairs of vertices. Clearly, if $x\in
V_{i}$, $y\in V_{j}$ and $i<j$, then $d(x,y)\geq 3(j-i)-2$. If $x\in V_{1}$
and $y\in V_{j}$, then $d(x,y)\geq 3j-5$. Hence

$\displaystyle W(G_{n,\Delta,\delta})$ $\displaystyle>$
$\displaystyle\sum_{2\leq i<j\leq\ell}\sum_{x\in V_{i},y\in
V_{j}}d(x,y)+\sum_{j=2}^{\ell}\sum_{x\in V_{1},y\in V_{j}}d(x,y)$
$\displaystyle\geq$ $\displaystyle\sum_{2\leq
i<j\leq\ell}|V_{i}|\,|V_{j}|\big{(}3(j-i)-2\big{)}+\sum_{j=2}^{\ell}|V_{1}|\,|V_{j}|\big{(}3j-5\big{)}$
$\displaystyle=$ $\displaystyle(\delta+1)^{2}\sum_{2\leq
i<j\leq\ell}\big{(}3(j-i)-2\big{)}+(\delta+1)\Delta\sum_{j=2}^{\ell}\big{(}3j-5\big{)}.$

Straightforward calculations show that $\sum_{2\leq
i<j\leq\ell}\big{(}3(j-i)-2\big{)}=\frac{1}{2}(\ell^{3}-5\ell^{2}+8\ell-4)>\frac{1}{2}(\ell^{3}-5\ell^{2})$
and
$\sum_{j=2}^{\ell}\big{(}3j-5\big{)}=\frac{1}{2}(3\ell^{2}-7\ell+4)>\frac{1}{2}(3\ell^{2}-7\ell)$.
Substituting these values, we obtain

$\displaystyle W(G_{n,\Delta,\delta})$ $\displaystyle>$
$\displaystyle\frac{1}{2}(\delta+1)^{2}(\ell^{3}-5\ell^{2})+\frac{1}{2}(\delta+1)\Delta(3\ell^{2}-7\ell)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\big{(}(\delta+1)^{2}\ell^{3}+3(\delta+1)\Delta\ell^{2}\big{)}-\frac{5}{2}(\delta+1)^{2}\ell^{2}-\frac{7}{2}(\delta+1)\Delta\ell.$

Let $N=n-\Delta+\delta$. Then $\ell(\delta+1)=N+1$. Therefore,
$(\delta+1)^{2}\ell^{3}+3(\delta+1)\Delta\ell^{2}=\frac{(N+1)^{3}}{\delta+1}+\frac{3\Delta(N+1)^{2}}{\delta+1}>\frac{N(N-1)(n+2\Delta)}{\delta+1}$.
Also
$\frac{5}{2}(\delta+1)^{2}\ell^{2}+\frac{7}{2}(\delta+1)\Delta\ell<\frac{7}{2}(N+1)((\delta+1)\ell+\Delta)=\frac{7}{2}(N+1)(n+\delta+1)<7n(n-1)$.
Applying these inequalities to the bound on $W(G_{n,\Delta,\delta})$ and
dividing by ${n\choose 2}$ thus yields

$\mu(G_{n,\Delta,\delta})>\frac{N(N-1)}{n(n-1)}\frac{n+2\Delta}{\delta+1}-14,$

which differs from the upper bound by at most $18$.

Define $\mu(n,\Delta,\delta)$ and $W(n,\Delta,\delta)$ to be the maximum
average distance and maximum Wiener index, respectively, among all connected
graphs of order $n$, minimum degree $\delta$ and maximum degree $\Delta$.
Theorem 1 shows that

$\mu(n,\Delta,\delta)=\frac{(n-\Delta+\delta)(n-\Delta+\delta-1)}{n(n-1)}\frac{n+2\Delta}{\delta+1}+O(1)$

and

$W(n,\Delta,\delta)={n-\Delta+\delta\choose
2}\frac{n+2\Delta}{\delta+1}+O(n^{2}).$

##  5 A bound for triangle-free graphs

In this section we show that the bound in Theorem 1 can be improved by a
factor of about $\frac{2}{3}$ for graphs not containing a triangle.

######  Theorem 5.3.

Let $G$ be a connected, triangle-free graph of order $n$, minimum degree
$\delta\geq 3$ and maximum degree $\Delta$. Then

$\mu(G)\leq\frac{2}{3}\frac{N(N-1)}{n(n-1)}\frac{n+2\Delta}{\delta}+7,$

where $N=n-\Delta+\delta$, and this bound is sharp apart from an additive
constant.

######  Proof 5.4.

We first find a matching $M$ of $G$ as follows. Choose an edge $e_{1}$ of $G$
that is incident with a vertex of degree $\Delta$ and let $M=\\{e_{1}\\}$. If
there exists an edge $e_{2}$ of $G$ at distance exactly $3$ from $M$, then add
$e_{2}$ to $M$, i.e., let $M=\\{e_{1},e_{2}\\}$. If there exists an edge
$e_{3}$ at distance $3$ from $M$ then add also $e_{3}$ to $M$. Repeat this
step, i.e., successively add edges at distance $3$ from $M$ until, after $k$
steps say, each edge of $G$ is within distance $2$ of $M$. Let
$M=\\{e_{1},e_{2},\ldots,e_{k}\\}$.

For $i=1,2,\ldots,k$ let $e_{i}=u_{i}v_{i}$. Let $T(e_{i})$ be the double-star
with vertex set $N_{G}(u_{i})\cup N_{G}(v_{i})$ that contains $e_{i}$ and all
edges of $G$ incident with $u_{i}$ or $v_{i}$. By the construction of $M$, the
trees $T(e_{i})$, $i=1,2,\ldots,k$, are disjoint. The union
$\bigcup_{i=1}^{k}T(e_{i})$ forms a subforest $T_{1}$ of $G$. It follows from
the construction of $M$ that for every $i\in\\{2,3,\ldots,k\\}$ there exists
an edge $f_{i}$ in $G$ joining a vertex in $T(e_{i})$ to a vertex in
$T(e_{j})$ for some $j$ with $1\leq j<i$. Then
$T_{2}:=T_{1}+\\{f_{2},f_{3},\ldots,f_{k}\\}$ is a subtree of $G$. By the
maximality of $M$, every edge of $G$ is within distance $2$ from some edge of
$M$, and so every vertex of $G$ is within distance $3$ from some vertex of
$V(M)$. We extend $T_{2}$ to a spanning tree $T$ of $G$ that preserves the
distances to a nearest vertex in $V(M)$.

Since the average distance of a spanning tree of $G$ is not less than the
average distance of $G$, it suffices to show that

$\mu(T)\leq\frac{2}{3}\frac{(n-\Delta+\delta)(n-\Delta+\delta-1)}{n(n-1)}\frac{n+2\Delta}{\delta}+7.$
(12)

For every vertex $u\in V(T)$ let $u_{M}$ be a vertex in $V(M)$ closest to $u$
in $T$. As in Theorem 1 we define a function $c:V(T)\rightarrow\reals^{\geq
0}$ by

$c(v)=|\\{u\in V(T)\ |\ u_{M}=v\\}|.$

As in Theorem 1, the weight of $c$ is concentrated in the vertices in $V(M)$.
Since no weight has been moved over a distance of more than $3$, a proof
similar to the proof of 4 yields that

$\mu(T)\leq\mu_{c}(T)+6.$ (13)

We now consider the line graph $L$ of $T$ and define a new weight function
$\overline{c}$ on the vertices of $L$, i.e., the edges of $T$, by

$\overline{c}(uv)=\left\\{\begin{array}[]{cc}c(u)+c(v)&\textrm{if $uv\in
M$,}\\\ 0&\textrm{if $uv\notin M$}.\end{array}\right.$

The weight of $\overline{c}$ is concentrated entirely in $M$, and $\sum_{e\in
E(T)}\overline{c}(e)=n$. Consider $e_{i}=u_{i}v_{i}\in M$. Since $G$ is
triangle-free, $u_{i}$ and $v_{i}$ have no common neighbours and so the
vertices in $N[u_{i}]-\\{v_{i}\\}$ contribute to $c(u_{i})$, and the vertices
in $N[v_{i}]-\\{u_{i}\\}$ contribute to $c(v_{i})$, implying that
$c(u_{i})\geq{\rm deg}_{G}(u_{i})$ and $c(v_{i})\geq{\rm deg}_{G}(v_{i})$.
Since $e_{1}$ is incident with a vertex of degree $\Delta$, while all the
other vertices in $V(M)$ have degree at least $\delta$, we conclude that

$\overline{c}(e_{i})\geq\left\\{\begin{array}[]{cc}\Delta+\delta&\textrm{if
$i=1$,}\\\ 2\delta&\textrm{if $i\in\\{2,3,\ldots,k\\}$.}\end{array}\right.$
(14)

Clearly $\sum_{e\in E(T)}\overline{c}(e)=n$, and so we have

$n\geq\sum_{i=1}^{k}\overline{c}(e_{i})\geq\Delta+\delta+2\delta(k-1)$

It follows that

$k\leq\frac{n-\Delta+\delta}{2\delta}.$ (15)

We now bound the difference between $\mu_{c}(T)$ and $\mu_{\overline{c}}(L)$.
If $u$ and $v$ are vertices of $T$, and $e_{u}$ and $e_{v}$ are edges of $T$
incident with $u$ and $v$, respectively, then it is easy to see that
$d_{T}(u,v)\leq d_{L}(e_{u},e_{v})+1$. Hence no distance between two weights
decreases by more than $1$ if we consider $L$ and $\overline{c}$ instead of
$T$ and $c$. Therefore,

$\mu_{c}(T)\leq\mu_{\overline{c}}(L)+1.$ (16)

Consider the induced subgraph $L^{4}[M]$. It follows from the construction of
$M$ that every $e_{i}\in M$ with $i\geq 2$ is at distance $4$ in $L$ from some
edge $e_{j}\in M$ with $1\leq j<i$, and so $L^{4}[M]$ is connected. Let
$H=L^{4}[M]$, so $V(H)=M$. If $e_{i},e_{j}\in M$, then clearly
$d_{L}(e_{i},e_{j})\leq 4d_{H}(e_{i}.e_{j})$, and so

$\mu_{\overline{c}}(L)\leq 4\mu_{\overline{c}}(H).$ (17)

We now modify the weight function $\overline{c}$ to obtain a new weight
function $c^{\prime}$ which satisfies $c^{\prime}(e)\geq 2\delta$ for all
$e\in M$. We let

$c^{\prime}(e_{i})=\left\\{\begin{array}[]{cc}\overline{c}(e_{1})-\Delta+\delta&\textrm{if
$i=1$,}\\\ \overline{c}(e_{i})&\textrm{if
$i\in\\{2,3,\ldots,k\\}$}.\end{array}\right.$

It follows from 14 that $c^{\prime}(e)\geq 2\delta$ for all $e\in M$. Letting
$N=\sum_{e\in M}c^{\prime}(e)$, we have $N=n-\Delta+\delta$.

We now express $\mu_{\overline{c}}(H)$ in terms of $\mu_{c^{\prime}}(H)$.
Arguments similar to those in the proof of 6 in the proof of Theorem 1 show
that

$\mu_{\overline{c}}(H)=\frac{N(N-1)}{n(n-1)}\mu_{c^{\prime}}(H)+\frac{2(\Delta-\delta)}{n(n-1)}\sum_{i=2}^{k}\overline{c}(e_{i})d_{H}(e_{1},e_{i}).$
(18)

We bound the two terms of the right hand side of 18 separately. Arguments
similar to the ones in the proof of 8 show that

$\sum_{i=2}^{k}\overline{c}(e_{i})d_{H}(e_{1},e_{i})\leq(n-\Delta-\delta)(k-1)-\delta(k-1)(k-2).$
(19)

Since $k\leq\frac{n-\Delta+\delta}{2\delta}$ by 15, and since the right hand
side is increasing in $k$ for $k\leq\frac{n-\Delta+\delta}{2\delta}$, we
obtain by substituting this value that

$\sum_{i=2}^{k}\overline{c}(e_{i})d_{H}(e_{1},e_{i})\leq\frac{(n-\Delta-\delta)^{2}}{4\delta}+\frac{n-\Delta-\delta}{2}.$

Since $N=n-\Delta+\delta$, the right hand side equals
$\frac{(N-2\delta)^{2}}{4\delta}+\frac{N-2\delta}{2}=\frac{N(N-2\delta)}{4\delta}$,
and so we obtain

$\sum_{i=2}^{k}\overline{c}(e_{i})d_{H}(e_{1},e_{i})\leq\frac{N(N-2\delta)}{4\delta}<\frac{N(N-1)}{4\delta}.$
(20)

To bound $\mu_{c^{\prime}}(H)$ we recall that $c^{\prime}(e)\geq 2\delta$ for
all $e\in V(H)=M$ and thus for every vertex $e$ of $H$, and that $\sum_{e\in
M}c^{\prime}(e)=N$. Let $C$ be the least multiple of $2\delta$ with $C\geq N$.
By Lemma 1 we have

$\mu_{c^{\prime}}(H)\leq\frac{C-2\delta}{C-1}\frac{C+2\delta}{6\delta}\leq\frac{C+1}{6\delta}.$

Since $C\leq N+2\delta-1$, this yields

$\mu_{c^{\prime}}(H)\leq\frac{N+2\delta}{6\delta}.$ (21)

Substituting 20 and 21 into 18 yields

$\displaystyle\mu_{\overline{c}}(H)$ $\displaystyle\leq$
$\displaystyle\frac{N(N-1)}{n(n-1)}\frac{N+2\delta}{6\delta}+\frac{2(\Delta-\delta)}{n(n-1)}\frac{N(N-1)}{4\delta}$
(22) $\displaystyle=$
$\displaystyle\frac{N(N-1)}{n(n-1)}\frac{n+2\Delta}{6\delta}.$

Combining the inequalities 13, 16, 17 and 22 we obtain that

$\displaystyle\mu(T)$ $\displaystyle\leq$ $\displaystyle\mu_{c}(T)+6$
$\displaystyle\leq$ $\displaystyle\mu_{\overline{c}}(L)+7$ $\displaystyle\leq$
$\displaystyle 4\mu_{\overline{c}}(H)+7$ $\displaystyle\leq$
$\displaystyle\frac{2}{3}\frac{N(N-1)}{n(n-1)}\frac{n+2\Delta}{\delta}+7,$

which is 12, and so the bound in the theorem follows.

To see that the bound is sharp apart from an additive constant let
$n,\Delta,\delta\in\naturals$ be given with $\Delta\geq\delta$ and
$n\geq\Delta+3\delta$. In order to keep our construction and calculations
simple, we assume that $n-\Delta-\delta$ is a multiple of $2\delta$, but as in
Theorem 1 this assumption is not essential. Let
$\ell=\frac{n-\Delta+\delta}{2\delta}$. Let $G_{1}$ be the complete bipartite
graph $K_{\delta,\Delta}$, and for $i=2,3,\ldots,\ell$ let $G_{i}$ be a copy
of the complete bipartite graph $K_{\delta,\delta}$. For $i=1,2,\ldots,\ell$
choose two adjacent vertices $u_{i}$ and $v_{i}$ of $G_{i}$, where ${\rm
deg}_{G_{1}}(u_{1})=\Delta$. Let $G_{n,\Delta,\delta}$ be the graph obtained
from $\bigcup_{i=1}^{\ell}G_{i}$ by deleting the edges $u_{i}v_{i}$ for
$i=2,3,\ldots,\ell-1$ and adding the edges $v_{i}u_{i+1}$ for
$i=1,2,\ldots,\ell-1$. Clearly, $G_{n,\Delta,\delta}$ is a triangle-free graph
of order $n$, minimum degree $\delta$ and maximum degree $\Delta$. A
calculation similar to the one in Theorem 1 shows that, with
$N=n-\Delta+\delta$,

$\mu(G_{n,\Delta,\delta})\geq\frac{2}{3}\frac{N(N-1)}{n(n-1)}\frac{n+2\Delta}{\delta}-8.$

Define $\mu^{\prime}(n,\Delta,\delta)$ and $W^{\prime}(n,\Delta,\delta)$ to be
the maximum average distance and maximum Wiener index, respectively, among all
connected, triangle-free graphs of order $n$, minimum degree $\delta$ and
maximum degree $\Delta$. Theorem 5.3 shows that

$\mu^{\prime}(n,\Delta,\delta)=\frac{2}{3}\frac{(n-\Delta+\delta)(n-\Delta+\delta-1)}{n(n-1)}\frac{n+2\Delta}{\delta}+O(1)$

and

$W^{\prime}(n,\Delta,\delta)=\frac{2}{3}{n-\Delta+\delta\choose
2}\frac{n+2\Delta}{\delta}+O(n^{2}).$

##  6 Bounds for $C_{4}$-free graphs

In this section we show that the bound in Theorem 1 can be improved
significantly for graphs not containing a $4$-cycle. If $\delta+1$ is a prime
power, then our bound is best possible in a sense specified later.

For the statement and proof of our bound for $C_{4}$-free graphs, we let
$\delta\in\naturals$ be fixed, and for given $d\in\\{\delta,\Delta\\}$ we
define

$\varepsilon_{d}:=d\delta-2\lfloor\frac{d}{2}\rfloor+1.$ (23)

We need the following lemma, whose special case $d=\delta$ can be found, for
example, in Erdös et al. (1989).

######  Lemma 1.

Let $G$ be a $C_{4}$-free graph of minimum degree $\delta$. If $v$ is a vertex
of $G$ of degree at least $d$, then

$|N_{\leq 2}(v)|\geq\varepsilon_{d}.$

######  Proof 6.5.

Let $w_{1},w_{2},\ldots,w_{d}$ be the neighbours of $v$. Then each $w_{i}$ is
adjacent to $v$ and at most one other vertex in $N(v)$. Hence each $w_{i}$ has
a set $U_{i}$ of at least $\delta-2$ neighbours in $N_{2}(v)$, and the sets
$U_{i}$, $i=1,2,\ldots,d$ are disjoint. Hence $|N_{\leq
2}(v)|\geq|N[v]|+\sum_{i=1}^{d}|U_{i}|=1+d+d(\delta-2)=d(\delta-1)+1$. If $d$
is even, then the lemma follows. If $d$ is odd, the inequality is strict since
otherwise, if $|N_{\leq 2}(v)|=d(\delta-1)+1$, each of the $d$ neighbours of
$v$ is adjacent to exactly one other neighbour of $v$, a contradiction to the
handshake lemma.

######  Theorem 6.6.

Let $G$ be a connected graph of order $n$, minimum degree $\delta\geq 3$ and
maximum degree $\Delta$. If $G$ does not contain $C_{4}$ as a subgraph, then

$\mu(G)\leq\frac{5}{3}\frac{N(N-1)}{n(n-1)}\frac{n+2\varepsilon_{\Delta}}{\varepsilon_{\delta}}+8,$

where $N=n-\varepsilon_{\Delta}+\varepsilon_{\delta}$, and
$\varepsilon_{\Delta}$, $\varepsilon_{\delta}$ as defined in equation 23.

######  Proof 6.7.

The proof is along similar lines as the proof of Theorem 1, hence we do not
give all the details.

We first find a $4$-packing $A$ of $G$ as follows. Choose a vertex $v_{1}$ of
degree $\Delta$ in $G$ and let $A=\\{v_{1}\\}$. If there exists a vertex
$v_{2}$ of $G$ at distance exactly $5$ from $A$, then add $v_{2}$ to $A$. If
there exists a vertex $v_{3}$ at distance exactly $5$ from $A$, then add also
$v_{3}$ to $A$. Repeat this step, i.e., successively add vertices at distance
exactly $5$ from $A$ until, after $k$ steps say, each vertex of $G$ is within
distance $4$ of $A$. Then $A=\\{v_{1},v_{2},\ldots,v_{k}\\}$.

By the construction of $A$ the sets $N_{\leq 2}(v_{i})$, $i=1,2,\ldots,k$, are
pairwise disjoint. For $i=1,2,\ldots,k$ let $T(v_{i})$ be a tree with vertex
set $N_{\leq 2}(v_{i})$ that preserves the distances from $v_{i}$. The
disjoint union $\bigcup_{i=1}^{k}T(v_{i})$ forms a subforest $T_{1}$ of $G$.
It follows from the construction of $A$ that for every
$i\in\\{2,3,\ldots,k\\}$ there exists an edge $e_{i}$ in $G$ joining a vertex
in $T(v_{i})$ to a vertex in $T(v_{j})$ for some $j$ with $1\leq j<i$. Hence
$T_{2}:=T_{1}+\\{e_{2},e_{3},\ldots,e_{k}\\}$ is a subtree of $G$. By the
maximality of $A$ every vertex of $G$ not in $T_{2}$ is within distance $4$
from some vertex in $A$. We extend $T_{2}$ to a spanning tree $T$ of $G$ that
preserves the distance in $G$ to $A$.

It suffices to show that

$\mu(T)\leq\frac{5}{3}\frac{(n-\varepsilon_{\Delta}+\varepsilon_{\delta})(n-\varepsilon_{\Delta}+\varepsilon_{\delta}-1)}{n(n-1)}\frac{n+2\varepsilon_{\Delta}}{\varepsilon_{\delta}}+8.$
(24)

For every vertex $u\in V(T)$ let $u_{A}$ be a vertex in $A$ closest to $u$ in
$T$. We define a weight function $c:V(T)\rightarrow\reals^{\geq 0}$ by

$c(v)=|\\{u\in V(T)\ |\ u_{A}=v\\}|.$

If $v\in A$, then every $u\in N_{\leq 2}(v)$ satisfies $u_{A}=v$. Lemma 1 thus
yields that $c(v_{1})\geq\varepsilon_{\Delta}$ and
$c(v_{i})\geq\varepsilon_{\delta}$ if $i\in\\{2,3,\ldots,k\\}$. If $v\in
V(G)-A$, then $c(v)=0$. We also note that $\sum_{v\in V(T)}c(v)=n$. This
yields $n=\sum_{v\in
A}c(v)\geq\varepsilon_{\Delta}+(k-1)\varepsilon_{\delta}$, and so

$k\leq\frac{n-\varepsilon_{\Delta}+\varepsilon_{\delta}}{\varepsilon_{\delta}}.$
(25)

Arguments similar to those in the proof of Theorem 1 show that

$\mu(T)\leq\mu_{c}(T)+8.$ (26)

As in the proof of Theorem 1, the graph $H:=T^{5}[A]$ is connected and
satisfies

$\mu_{c}(T)\leq 5\mu_{c}(H).$ (27)

We modify the weight function $c$ to obtain a new weight function $c^{\prime}$
on $A$. Let

$c^{\prime}(v)=\left\\{\begin{array}[]{cc}c(v)-\varepsilon_{\Delta}+\varepsilon_{\delta}&\textrm{if
$v=v_{1}$,}\\\ c(v)&\textrm{if $v\in A-\\{v_{1}\\}$}.\end{array}\right.$

We have $c^{\prime}(v)\geq\varepsilon_{\delta}$ for all $v\in A$. Let
$N=\sum_{i=1}^{k}c^{\prime}(v_{i})$, so
$N=n-\varepsilon_{\Delta}+\varepsilon_{\delta}$. As in the proof of 6 in
Theorem 1 shows that we can express $\mu_{c}(H)$ in terms of
$\mu_{c^{\prime}}(H)$ as follows:

$\mu_{c}(H)=\frac{N(N-1)}{n(n-1)}\mu_{c^{\prime}}(H)+\frac{2(\varepsilon_{\Delta}-\varepsilon_{\delta})}{n(n-1)}\sum_{i=2}^{k}c(v_{i})d_{H}(v_{1},v_{i}).$
(28)

Arguments similar to the proof of 8 show that
$\sum_{i=2}^{k}c(v_{i})d_{H}(v_{1},v_{i})\leq\frac{N(N-\varepsilon_{\delta})}{2\varepsilon_{2\delta}}$
and thus

$\sum_{v\in
A-\\{v_{1}\\}}c(v)d_{H}(v_{1},v)\leq\frac{N(N-1)}{2\varepsilon_{\delta}}.$
(29)

and

$\mu_{c^{\prime}}(H)\leq\frac{N+\varepsilon_{\delta}}{3\varepsilon_{\delta}}.$
(30)

Substituting 29 and 30 into 28 yields that

$\displaystyle\mu_{c}(H)$ $\displaystyle\leq$
$\displaystyle\frac{N(N-1)}{n(n-1)}\frac{N+\varepsilon_{\delta}}{3\varepsilon_{\delta}}+\frac{\varepsilon_{\Delta}-\varepsilon_{\delta}}{n(n-1)}\frac{N(N-1)}{\varepsilon_{\delta}}$
(31) $\displaystyle=$
$\displaystyle\frac{N(N-1)}{n(n-1)}\frac{n+2\varepsilon_{\Delta}-\varepsilon_{\delta}}{3\varepsilon_{\delta}}$
$\displaystyle<$
$\displaystyle\frac{N(N-1)}{n(n-1)}\frac{n+2\varepsilon_{\Delta}}{3\varepsilon_{\delta}}.$

Combining the inequalities 26, 27 and 31 we obtain that

$\displaystyle\mu(T)$ $\displaystyle\leq$ $\displaystyle\mu_{c}(T)+8$
$\displaystyle\leq$ $\displaystyle 5\mu_{c}(H)+8$ $\displaystyle\leq$
$\displaystyle\frac{5}{3}\frac{N(N-1)}{n(n-1)}\frac{n+2\varepsilon_{\Delta}}{\varepsilon_{\delta}}+8,$

which is 24, and so the bound in the theorem follows.

The following theorem shows that the bound in Theorem 6.6 is not far from best
possible if $\delta+1$ is a prime power. Our construction is based on the
graph $H_{q}$ described below, constructed independently by Erdös and Rényi
(1962) and Brown Brown (1966), and a modification $H_{q}^{\prime}$, first
described in Erdös et al. (1989).

Let $q$ be a prime power. Let $GF(q)$ be the field of order $q$ and let
$GF(q)^{3}$ be the $3$-dimensional vector space over $GF(q)$ whose vectors are
the triples of elements of $GF(q)$. We define $H_{q}$ to be the graph whose
vertices are the $1$-dimensional subspaces of $GF(q)^{3}$, where two vertices
are adjacent if, as subspaces, they are orthogonal. Using elementary linear
algebra it is easy to verify that $H_{q}$ has $q^{2}+q+1$ vertices, that its
vertices have degree either $q$ or $q+1$, and that $H_{q}$ is $C_{4}$-free and
connected.

Erdös et al. (1989) described a modification $H_{q}^{\prime}$ of the graph
$H_{q}$, obtained as follows. Choose a vertex $z$ of degree $q$ in $H_{q}$ and
let $u,v$ be two distinct neighbours of $z$. Delete $z$ and all edges joining
a neighbour of $u$ to a neighbour of $v$. The resulting graph $H_{q}^{\prime}$
is connected, $C_{4}$-free and has $q^{2}+q$ vertices, its minimum degree is
at least $q-1$, and $d_{H_{q}^{\prime}}(u,v)\geq 4$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$H_{q}^{\prime}$$H_{q}^{\prime}$$H_{q}^{\prime}$$H_{q}^{\prime}$$H_{q}$$H_{q}$$G_{1}$$G_{2}$$G_{3}$$G_{4}$$G_{5}$
Figure 2: The graph $G_{k,\ell,q}$ for $k=2$ and $\ell=5$.

######  Theorem 6.8.

Let $\delta\in\naturals$ such that $\delta\geq 3$ and $\delta+1$ is a prime
power. Let $\Delta\in\naturals$ such that $\Delta-1$ is a positive multiple of
$\delta+2$. Let $n\in\naturals$ such that $n-(\Delta-1)(\delta+1)-1$ is a
positive multiple of $(\delta+1)(\delta+2)$. Then there exists a $C_{4}$-free
graph $G$ of order $n$, maximum degree $\Delta$ and minimum degree at least
$\delta$ which satisfies

$\mu(G)>\frac{5}{3}\frac{M(M-1)}{n(n-1)}\frac{n+2\theta_{\Delta}}{\theta_{\delta}}-13,$

where $\theta_{\Delta}=(\Delta-1)(\delta+1)+1$,
$\theta_{\delta}=(\delta+2)(\delta+1)$, and
$M=n-\theta_{\Delta}+\theta_{\delta}$.

######  Proof 6.9.

Let $q=\delta+1$. By the assumptions on $\Delta$ and $n$ we can find
$k,\ell\in\naturals$ with $\ell\geq 2$ such that $\Delta=k(q+1)+1$ and
$n=(k+\ell-1)(q^{2}+q)+1$.

We construct a graph $G_{1}$ by taking $k$ disjoint copies of $H_{q}$,
choosing a vertex of degree $q+1$ in each copy, and then identifying these $k$
vertices to a new vertex $v_{1}$. Clearly, $n(G_{1})=k(q^{2}+q)+1$ and ${\rm
deg}_{G_{1}}(v_{1})=k(q+1)$. For $i=2,3\ldots,\ell$ let $G_{i}$ be a copy of
the graph $H_{q}^{\prime}$. Let $u_{i}$ and $v_{i}$ denote the vertices of
$G_{i}$ corresponding to $u$ and $v$, respectively, of $H_{q}^{\prime}$. Let
$G_{k,\ell,q}$ be the graph obtained from the disjoint union
$\bigcup_{i=1}^{\ell}G_{i}$ by adding the edges $v_{i}u_{i+1}$ for
$i=1,2,\ldots,\ell-1$. A sketch of the graph $G_{2,5,q}$ is shown in Figure 2.
Then $G_{k,\ell,q}$ has order $n$, maximum degree $\Delta$ and minimum degree
at least $\delta$. We define $\theta_{\Delta}=(\Delta-1)(\delta+1)+1$,
$\theta_{\delta}=(\delta+2)(\delta+1)$, and
$M=n-\theta_{\Delta}+\theta_{\delta}$.

We now bound the average distance of $G_{k,\ell,q}$ from below in terms of
$n$, $\theta_{\Delta}$ and $\theta_{\delta}$. Let $V_{i}:=V(G_{i})$ for
$i=1,2,\ldots,\ell$. Then $|V_{1}|=\theta_{\Delta}$ and
$|V_{i}|=\theta_{\delta}$ for $i=2,3,\ldots,\ell$.

For our lower bound we only count the distances between pairs $x,y$ with
either $x\in V_{i}$ and $y\in V_{j}$ where $2\leq i<j\leq\ell$, or $x\in
V_{1}$ and $y\in V_{j}$ for $j=2,3,\ldots,\ell$, ignoring all other pairs of
vertices. Clearly, if $x\in V_{i}$, $y\in V_{j}$ and $i<j$, then $d(x,y)\geq
5(j-i)-4$. If $x\in V_{1}$ and $y\in V_{j}$, then $d(x,y)\geq 5j-9$. Hence

$\displaystyle W(G_{k,\ell,q})$ $\displaystyle>$ $\displaystyle\sum_{2\leq
i<j\leq\ell}\sum_{x\in V_{i},y\in V_{j}}d(x,y)+\sum_{j=2}^{\ell}\sum_{x\in
V_{1},y\in V_{j}}d(x,y)$ $\displaystyle\geq$ $\displaystyle\sum_{2\leq
i<j\leq\ell}|V_{i}|\,|V_{j}|\big{(}5(j-i)-4\big{)}+\sum_{j=2}^{\ell}|V_{1}|\,|V_{j}|\big{(}5j-9\big{)}$
$\displaystyle=$ $\displaystyle\theta_{\delta}^{2}\sum_{2\leq
i<j\leq\ell}\big{(}5(j-i)-4\big{)}+\theta_{\delta}\theta_{\Delta}\sum_{j=2}^{\ell}\big{(}5j-9\big{)}.$

Straightforward calculations show that $\sum_{2\leq
i<j\leq\ell}\big{(}5(j-i)-4\big{)}=\frac{1}{6}(5\ell^{3}-27\ell^{2}+46\ell-24)\geq\frac{1}{6}(5\ell^{3}-27\ell^{2})$
and
$\sum_{j=2}^{\ell}\big{(}5j-9\big{)}=\frac{1}{2}(5\ell^{2}-13\ell+8)\geq\frac{1}{2}(5\ell^{2}-13\ell)$.
Substituting these values we obtain

$\displaystyle W(G_{k,\ell,q})$ $\displaystyle>$
$\displaystyle\frac{1}{6}\theta_{\delta}^{2}(5\ell^{3}-27\ell^{2})+\frac{1}{2}\theta_{\delta}\theta_{\Delta}(5\ell^{2}-13\ell)$
$\displaystyle=$
$\displaystyle\frac{5}{6}\big{(}\theta_{\delta}^{2}\ell^{3}+3\theta_{\delta}\theta_{\Delta}\ell^{2}\big{)}-\frac{9}{2}\theta_{\delta}^{2}\ell^{2}-\frac{13}{2}\theta_{\Delta}\theta_{\delta}\ell.$

Since $\ell\theta_{\delta}=M$, we have
$\theta_{\delta}^{2}\ell^{3}+3\theta_{\delta}\theta_{\Delta}\ell^{2}=\frac{M^{3}}{\theta_{\delta}}+3\frac{\theta_{\Delta}M^{2}}{\theta_{\delta}}\geq\frac{M(M-1)(n+2\theta_{\Delta})}{\theta_{\delta}}$.
Also
$\frac{9}{2}\theta_{\delta}^{2}\ell^{2}+\frac{13}{2}\theta_{\Delta}\theta_{\delta}\ell<\frac{13}{2}\theta_{\delta}\ell(\theta_{\delta}\ell+\theta_{\Delta})=\frac{13}{2}M(M+\theta_{\Delta})=\frac{13}{2}(n-\theta_{\Delta}+\theta_{\delta})(n+\theta_{\delta})\leq\frac{13}{2}(n-1)n$.
Dividing the above lower bound on $W(G_{k,\ell,q})$ by ${n\choose 2}$ thus
yields

$\mu(G_{k,\ell,q})>\frac{5}{3}\frac{M(M-1)}{n(n-1)}\frac{n+2\theta_{\Delta}}{\theta_{\delta}}-13,$

as desired.

To see that Theorem 6.6 is not far from best possible, even for very large
maximum degree, assume that $\delta,\Delta\in\naturals$ satisfy the hypothesis
of Theorem 6.8, and that moreover $\Delta=cn$ for some $c\in\naturals$ with
$0<c<\frac{1}{\delta+1}$ (note that by Lemma 1 $c$ cannot be greater than
$\frac{1}{\delta+1}$). Then the leading term in the upper bound in Theorem 6.6
is
$\frac{5}{3}\frac{(1-c\delta)^{2}(1+2c\delta)}{\delta^{2}-2\lfloor\delta/2\rfloor+1}n$
while the leading term in the lower bound in Theorem 6.8 is
$\frac{5}{3}\frac{(1-c(\delta+1)^{2}(1+2c(\delta+1))}{\delta^{2}+\delta-2}n$.
It is easy to see that the ratio of the two coefficients of $n$ approaches $1$
as $\delta$ gets large. So the larger $\delta$, the closer the bound in
Theorem 6.6 to being sharp.

##  7 Open Problem

In this paper we gave three instances in which bounds on the Wiener index or
the average distance for graphs of given order and minimum degree can be
improved significantly if the graph contains a vertex of large degree. The
same question can be asked for bounds in terms of other graph parameters. For
example it was shown by Plesní k (1984) that the cycle is the unique graph
maximising the Wiener index among all $2$-edge-connected or $2$-connected
graphs of given order, and corresponding results for graphs of higher
connectivity were given in Dankelmann et al. (2009). Can these bounds be
improved significantly if the graph has a vertex of large degree?

######  Problem 7.10.

Determine the maximum Wiener index among all $2$-connected graphs of given
order and maximum degree.

## References

  * Beezer et al. (2001) R. A. Beezer, J. F. Riegsecker, and B. Smith.  Using minimum degree to bound average distance.  _Discrete Math._ , 226:365–371, 2001.
  * Bickle and Che (2021) A. Bickle and Z. Che.  Wiener indices of maximal $k$-degenerate graphs.  _Graphs Combin._ , 37:581–589, 2021.
  * Brown (1966) W. G. Brown.  On graphs that do not contain a thomsen graph.  _Canad. Math. Bull._ , 9:281–285, 1966.
  * Casablanca and Dankelmann (2019) R. M. Casablanca and P. Dankelmann.  Distance and eccentric sequences to bound the wiener index hosoya polynomial and the average eccentricity in the strong product of graphs.  _Discrete Appl. Math._ , 263:105–117, 2019.
  * Cela et al. (2011) E. Cela, N. S. Schmuck, S. Wimer, and G. J. Woeginger.  The wiener maximum quadratic assignment problem.  _Discrete Optim._ , 8:411–416, 2011.
  * Dankelmann (2006) P. Dankelmann.  Average distance, minimum degree, and size.  _Utilitas Math._ , 69:233–243, 2006.
  * Dankelmann (2019) P. Dankelmann.  On average distance in tournaments and eulerian digraphs.  _Discrete Appl. Math._ , 266:38–47, 2019.
  * Dankelmann and Entringer (2000) P. Dankelmann and R. C. Entringer.  Average distance, minimum degree and spanning trees.  _J. Graph Theory_ , 33:1–13, 2000.
  * Dankelmann and Osaye (2020) P. Dankelmann and F. J. Osaye.  Average eccentricity, minimum degree and maximum degree in graphs.  _J. Combin. Optim._ , 40:697–712, 2020.
  * Dankelmann et al. (2005) P. Dankelmann, G. Dlamini, and H. C. Swart.  Upper bounds on distance measures in $k_{3,3}$-free graphs.  _Utilitas Mathematica_ , 67:205–222, 2005.
  * Dankelmann et al. (2009) P. Dankelmann, S. Mukwembi, and H. Swart.  Average distance and vertex connectivity.  _J. Graph Theory_ , 62:157–177, 2009.
  * Erdös and Rényi (1962) P. Erdös and A. Rényi.  On a problem in the theory of graphs.  _Publ. Math. Inst. Hungar. Acad. Sci._ , 7:215–235, 1962\.
  * Erdös et al. (1988) P. Erdös, J. Pach, and J. Spencer.  On the mean distance between points of a graph.  _Congr. Numer._ , 64:121–124, 1988.
  * Erdös et al. (1989) P. Erdös, J. Pach, R. Pollack, and Z. Tuza.  Radius, diameter, and minimum degree.  _J. Combin. Theory Ser. B_ , 47:73–79, 1989.
  * Fajtlowicz and Waller (1987) S. Fajtlowicz and W. Waller.  On two conjectures of graffiti.  _Congr. Numer._ , 60:187–197, 1987.
  * Fischermann et al. (2002) M. Fischermann, A. Hoffmann, D. Rautenbach, L. A. Székely, and L. Volkmann.  Wiener index versus maximum degree in trees.  _Discrete Appl. Math._ , 122:127–137, 2002.
  * Furtula (2013) B. Furtula.  Odd-vertex-degree trees maximizing wiener index.  _Kragujevac J. Math._ , 37:129–134, 2013.
  * Klavz̆ar and Gutman (1997) S. Klavz̆ar and I. Gutman.  Wiener number of vertex-weighted graphs and a chemical application.  _Discrete Appl. Math._ , 80:73–81, 1997.
  * Klavz̆ar and Nadjafi-Arani (2014) S. Klavz̆ar and M. J. Nadjafi-Arani.  Wiener index in weighted graphs via unification of $\theta^{*}$-classes.  _Europ. J. Combin._ , 36:71–76, 2014.
  * Knor et al. (2016a) M. Knor, R. S̆krekovski, and A. Tepeh.  Orientations of graphs with maximum wiener index.  _Discrete Math._ , 211:121–129, 2016a.
  * Knor et al. (2016b) M. Knor, R. S̆krekovski, and A. Tepeh.  Some remarks on wiener index of oriented graphs.  _Appl. Math. Computation_ , 273:631–636, 2016b.
  * Kouider and Winkler (1997) M. Kouider and P. Winkler.  Mean distance and minimum degree.  _J. Graph Theory_ , 25:95–99, 1997.
  * Lin (2013) H. Lin.  Extremal wiener index of trees with all degrees odd.  _MATCH Commun. Math. Comput. Chem._ , 70:287 – 292, 2013\.
  * Mukwembi (2014) S. Mukwembi.  Average distance, independence number, and spanning trees.  _J. Graph Theory_ , 76:194–199, 2014.
  * Plesní k (1984) J. Plesní k.  On the sum of all distances in a graph or digraph.  _J. Graph Theory_ , 8:1–24, 1984.
  * Schmuck et al. (2012) N. S. Schmuck, S. G. Wagner, and H. Wang.  Greedy trees, caterpillars, and wiener-type graph invariants.  _MATCH Commun. Math. Comput. Chem._ , 68:273 – 292, 2012\.
  * Stevanović (2008) D. Stevanović.  Maximizing wiener index of graphs with fixed maximum degree.  _MATCH Commun. Math. Comput. Chem._ , 60:71–83, 2008.
  * Wang (2008) H. Wang.  The extremal values of the wiener index of a tree with given degree sequence.  _Discrete Appl. Math._ , 156:2647–2654, 2008.