# Rechargeable black hole battery

Zhan-Feng Mai<EMAIL_ADDRESS>Center for Joint Quantum Studies and
Department of Physics, School of Science, Tianjin University, Yaguan Road 135,
Jinnan District, 300350 Tianjin, P. R. China  Kavli Institute for Astronomy
and Astrophysics, Peking University, Beijing 100871, China  Run-Qiu Yang
<EMAIL_ADDRESS>Center for Joint Quantum Studies and Department of Physics,
School of Science, Tianjin University, Yaguan Road 135, Jinnan District,
300350 Tianjin, P. R. China

###### Abstract

This paper proposes a classical physical process to use a Schwarzschild black
hole as a rechargeable battery. In its one cycle the black hole does not loss
energy but can at most transform 25% of input mass into available electric
energy in a controllable and slow way. We build the theory about the dynamics
of black hole in cavity to study the discharging process. Under “quasi-static
approximation”, we study various properties of this battery, including the
internal resistance, efficiency of discharging, maximum output power, cycle
life and totally available energy. Differing from that usual Penrose process
or superradiance can extract appreciable energy only from extremely rotational
or charged black hole, the black hole here is non-rotational and only needs
very tiny amounts of charge but in its life it can supply available electric
energy much larger than its initial mass.

##  I Introduction

Sustainable energy will play a major role in the future of humanity. To find
cleaner, higher power and larger capacity “battery” (the “battery” in this
paper refers to all devices or systems that can generate electric energy) will
be an important way to solve the energy crisis. A basic property of a battery
is that it can convert non-electric energy into electric energy in a slow and
controllable way to supply the appliances. There are several common mechanisms
of battery, such as using the chemical energy, solar energy, wind or water
energy, nuclear energy and so on. The black hole, being predicted by
Einstein’s general relativity, is one of the most fantastic object in our
universe, describing an extreme region from which the gravity is so strong
that no signal or classical matter can escape. Taking the fact that the black
hole has extremely strong gravitational force, an interesting question arises:
considering at least theoretically, could we use the gravitational force of
black holes to generate electric energy, i.e. make use of black holes as
batteries?

Though the black hole’s strong gravity forbids that the classical matters
escape from it into outside, fortunately, the energy can be extracted from the
black hole through quantum or classical processes. The famous Hawking
radiation is one quantum way that the black hole losses energy Hawking (1972,
1974). For a larger black hole such effect is too weak to be used. For a small
enough black hole, the Hawking radiation can be strong. However, in this case,
the black hole will evaporate in a very short time and the energy releasing is
too drastic and rapid to be used as a controllable supply. An other of the
famous processes for energy extraction is the Penrose process, stating that a
classical particle can extract rotation energy from Kerr black hole Penrose
and Floyd (1971); Chandrasekhar and Chandrasekhar (1998). Furthermore, it also
turned out that there exist an effective Penrose Process arising between the
Reissner-Nordström (RN) black hole and a charged particle, showing that the
energy and charge of RN black hole can be extracted by charge particles
Denardo and Ruffini (1973). In addition, another classical process being able
to extract energy from black holes is _superradiance_ Brito  _et al._ (2015),
which can also extract energy from rotational or charged black holes.

By Penrose process or superradiance, the charged black hole can be used as a
kind of battery. To extract the electric energy of same order as the black
hole mass, the black hole must be almost extreme, i.e. contains a large
amounts of charge. However, the naturally formed black holes, which come from
the primordial black hole, the large mass star or the other astrophysical
processes, though may carry large amounts angular momentum, will be neutral.
The observations via gravitational wave Abbott and el. al (2016); Abbott and
et. al (2017) also verified this point. This seems to show that the naturally
formed black hole is not suitable for being used as a battery even from
theoretical viewpoint. Particularly, the Schwarzschild black hole is the final
stable state of black hole in classical physics and so there is seemingly no
hope to use it as a battery to supply appliances by classical processes.

This paper aims to illustrate an basic idea to construct a black hole battery
by using Schwarzschild black hole and discuss its associated properties. We
propose a method to recharge the Schwarzschild black hole by very tiny amounts
of charge. When the radius of initial black hole is large enough, we show that
strong gravitational force can transform at most 25% input mass into electric
energy. This theoretically provides a very effective way to transform mass
into electric power. Confining the recharged black hole in a cavity and under
the quasi-static approximation, we show that such system can play the role of
a usual battery to supply appliances. This battery has nonzero internal
resistance. We show that the Joule heat produced in discharging process just
satisfies the requirement of thermodynamical laws of black holes. We study the
discharging efficiency, maximum output power, cycle life and totally available
energy. It is surprising that our black hole battery in its life can even
supply available energy much larger than its initial mass. Here we emphasize
that the battery does not really extract energy from its interior black hole
after a cycle. Instead, strong gravitational force of black hole plays a role
of transforming input mass into electric energy, which is just as similar as a
chemical battery transforming chemical energy into electric energy.

##  II Add fuel for battery

Let us first introduce how to add “fuel” (recharging process) for a
Schwarzschild black hole. In following discussion, we mainly use the natural
units system $G=c=\hbar=k_{B}=4\pi\varepsilon_{0}=1$.

Figure 1: The charged sphere falls into black hole spontaneously since the
gravitational force is stronger than Coulomb repulsion.

Consider a static spherically symmetric black hole has mass $M$ and charge $Q$
with $|Q|/M\ll 1$, which is confined inside a cavity. We assume that the
radius $r_{c}$ of cavity is much larger than the horizon radius $r_{+}$ of the
black hole. The black hole cannot be too small since the Hawking radiation
will lead that a tiny black hole evaporates completely in a very short time.
If we require that effect of Hawking radiation is negligible in a time scale
of age of our universe, the minimal mass of initial black hole should be much
larger than $10^{11}$kg. We prepare a large amounts of small spheres, every
one of which contains the same mass $m$ and charge $q$ with

$|q|\gg m,~{}~{}\text{or in SI unit }|q|/m\gg 10^{-10}\mathrm{C/kg}$ (1)

If we inject a such sphere into the cavity (see Fig. 1) under following
restriction

$\frac{Q}{M}q\leq m,$ (2)

then gravitational force will always larger than electric repulsion and these
spheres will spontaneously fall into black hole. See appendix A for how to
obtain it from general relativity. It is interesting that the Newton’s laws
combining with Coulomb’s law can also give us a same result. By this process,
the neutral black hole is recharged. Note that this recharging process does
not consume additional energy since the falling of charged spheres is
spontaneous.

On the other hand, when the electric field $E$ inside the cavity is strong
enough, the Schwinger effect may play an important role Schwinger (1951). In
this case the electron-antielectron are separated from vacuum and the charged
black hole will absorbe one of them, which prevents the black hole from being
recharged further. In flat spacetime, the critical electric field that
Schwinger effect becomes important is $E_{s}=m_{e}^{2}/e\approx 10^{18}$V/m.
Here $e$ is elementary charge and $m_{e}$ is the mass of electron. Detailed
discussion on the Schwinger effect in curved spacetime will be lengthy and
complicated, one can refer to Refs. Garriga (1994); Kim (2016); Cai  _et al._
(2020) and references therein. We note the Schwinger effect will happen at a
scale of electron Broglie wavelength $\lambda_{e}\approx 10^{-12}$m. In the
case that the black hole horizon radius $r_{+}\gg\lambda_{e}$ (this will be
the case considered in this paper), the equivalent principle then implies that
gravitational effect can be ignored when we consider the physics below the
length scale $\lambda_{e}$. For the case that there is a spherically symmetric
charged black hole, we can estimate the upper bound on its total charge by
using the critical electric field of flat spacetime

$\frac{|Q|}{r_{+}^{2}}\approx\frac{|Q|}{4M^{2}}\lesssim E_{s}\,.$ (3)

Here $Q/r_{+}^{2}$ is the electric field measured by local Lorentz frame and
we used assumption $|Q|\ll M$ to obtain $r_{+}\approx 2M$. If inequality (3)
is broken, the black hole can absorb opposite charge from vacuum and the
battery cannot be charged anymore.

When any one of conditions (2) and (3) is broken, the recharged process will
stop. Assume that an initially neutral black hole has mass $M_{0}$ and can at
most swallow $n_{r}$ such charged spheres. The finally charge and mass of
fully recharged black hole then read $Q_{r}=n_{r}q$ and $M=M_{0}+n_{r}m$. If
the inequality (2) is first broken, which we call “Coulomb domain”, the
charged sphere cannot fall into black hole spontaneously since Coulomb
repulsion will be stronger than gravitational attraction. In this case we have
$n_{r}=M_{0}m/q^{2}$. If the inequality (3) is first broken, which we call
“Schwinger domain”, the Schwinger effect prevents the black hole from being
recharged and we have $n_{r}=4E_{s}M_{0}^{2}/|q|$. They can be combined into

$n_{r}=\min\left\\{\frac{M_{0}m}{q^{2}},~{}~{}\frac{4E_{s}M_{0}^{2}}{|q|}\right\\}\,.$
(4)

or in SI units

$n_{r}=\min\left\\{\frac{M_{0}m/\mathrm{kg}^{2}}{(q/\mathrm{C})^{2}}\times
10^{-20},~{}~{}\frac{(M_{0}/\mathrm{kg})^{2}}{|q/\mathrm{C}|}\times
10^{-46}\right\\}\,.$ (5)

The “Coulomb domain” will happen when $M_{0}$ is large enough; while the
“Schwinger domain” will happen for small-sized black holes.

From Eqs. (4) and (1) we see that the $Q_{r}$ and increased mass $\Delta M$ of
fully recharged black hole satisfies

$|Q_{r}|=n_{r}|q|\leq\frac{M_{0}m}{q^{2}}|q|=\frac{m}{|q|}M_{0}\ll M_{0}$ (6)

and

$\Delta M=n_{r}m\leq\frac{m^{2}}{q^{2}}M_{0}\ll M_{0}\,.$ (7)

The horizon radius becomes

$r_{+}=M+\sqrt{M^{2}-Q_{r}^{2}}\approx
2M_{0}+2n_{r}m-\frac{n_{r}^{2}q^{2}}{2M_{0}}\,.$ (8)

The Hawking temperature reads $T\approx 1/(8\pi M_{0})$. The increased energy
$\Delta M$ contains two parts, the first one causes the increment of entropy
Bekenstein (1973, 1974); Hawking (1972); Bardeen  _et al._ (1973); Hawking and
Ellis (1973), which stands the thermal dissipation $T\Delta S\approx\Delta
r_{+}/2$. This is the unavailable energy. The other one

$\mathcal{E}=\Delta M-T\Delta
S\approx\frac{n_{r}^{2}q^{2}}{4M_{0}}=\min\left\\{\frac{n_{r}m}{4},M_{0}^{3}E_{s}^{2}\right\\}$
(9)

is available energy, stored as the static electric potential energy.
Furthermore, the efficiency for the recharging process is
$\eta_{r}=\mathcal{E}/(n_{r}m)\leq 25\%$. When we add “fuel” for a large
enough black hole, the recharging process will be terminated at “Coulomb
domain”. In this case the black hole can at most transform 25% input mass into
available energy of static electric field.

##  III Dynamics of black hole in cavity

###  III.1 On-shell Action and Ward Identities

To exhibit our process of discharging, we first need to build the theory about
dynamics of black hole in a cavity. We begin with the Einstein-Maxwell theory,
which minimally coupled a free massless complex scalar field. The complex
scalar field carries charge $\sigma$. In this paper, we will always assume
that the quantum effects of both black holes and matters are negligible. The
total action of our theory is written as

$S=S_{\rm bulk}+S_{\rm surf}$ (10)

where

$\displaystyle S_{\rm
bulk}:=\frac{1}{16\pi}\int_{M}\text{d}^{4}x\sqrt{-g}\left(R-F^{2}-|D_{\mu}\Psi|^{2}\right)\,,$
(11) $\displaystyle S_{\rm surf}:=-\frac{1}{8\pi}\int_{\partial
M}\text{d}^{3}x\sqrt{-h}(K-K_{0})\,.$ (12)

In the bulk action,
$F_{\mu\nu}\equiv\partial_{\mu}A_{\nu}-\partial_{\nu}A_{\mu}$ stands for the
field strength of the Maxwell field, as well as $D_{\mu}:=\nabla_{\mu}-i\sigma
A_{\mu}$. The surface action includes the Gibbons-Hawking term and the counter
term respectively, where $h_{ij}$ and $K$ denote the induce metric the
associated intrinsic curvature scalar. We here choose
$K_{0}=K|_{g_{\mu\nu}=\eta_{\mu\nu}}$ to eliminate the infinity of flat
spacetime. Performing variation with respect to $g^{\mu\nu}$, $A_{\mu}$ and
$\Psi^{{\dagger}}$, the equations of motion read

$\displaystyle G_{\mu\nu}=8\pi T_{\mu\nu},~{}\nabla^{\mu}F_{\mu\nu}=-4\pi
J_{\nu}^{\Psi},~{}D^{\mu}D_{\mu}\Psi=0\,,$ (13)

where $G_{\mu\nu}=R_{\mu\nu}-\frac{1}{2}g_{\mu\nu}R$ denotes the Einstein
tensor. The bulk energy momentum tensor $T_{\mu\nu}$ and the bulk current
$J^{\Psi}_{\mu}$ read

$\displaystyle
T_{\mu\nu}:=\frac{1}{4\pi}\left(F_{\mu\sigma}{F_{\nu}{}^{\sigma}}-\frac{1}{4}g_{\mu\nu}F_{\rho\sigma}F^{\rho\sigma}\right)$
(14)
$\displaystyle+\frac{1}{16\pi}\left(D_{\mu}\Psi(D_{\nu}\Psi)^{\dagger}+D_{\nu}\Psi(D_{\mu}\Psi)^{\dagger}-g_{\mu\nu}\left(|D_{\rho}\Psi|^{2}\right)\right)\,,$
(15) (16) $\displaystyle
J^{\Psi}_{\mu}:=-\frac{\sigma}{4\pi}\Im(\Psi^{\dagger}D_{\mu}\Psi)\,.$ (17)

One widely used quasi-local definition of energy is the Brown-York energy
momentum tensor Brown and York (1993); Brown  _et al._ (2002); Szabados (2004)
from the on-shell action

${\cal T}_{ij}(x)\equiv\frac{-2}{\sqrt{-h}}\frac{\delta S_{\rm on-
shell}}{\delta h^{ij}(x)}=[K_{ij}]-h_{ij}[K]\,,$ (18)

Here $h_{ij}$ and $K_{ij}$ are induced metric and extrinsic curvature of cut-
off boundary, $[K_{ij}]=K_{ij}-K_{0,ij}$ and $[K]=K-K_{0}$. The $K_{0,ij}$ is
the extrinsic curvature when the boundary embedded in flat spacetime. This can
be regarded as the energy momentum tensor of the black hole confined in the
box. Since the black hole is allowed to exchange energy through the boundary,
the Brown-York energy momentum tensor ${\cal T}_{ij}$ is not conserved. The
dynamics of the Brown-York energy momentum tensor are ruled by the following
“Ward Identity”, arising from the diffeomorphic invariance of cut-off
boundary.

Specifically, let $\xi^{i}$ to be arbitrary vector field which is tangent to
cut-boundary, this vector field then can generate an infinitesimal
diffeomorphic transformation $x^{i}\rightarrow x^{i}+\varepsilon\xi^{i}$ for
boundary. The diffeomorphic invariance of the on-shell action requires that.

$\displaystyle{\cal L}_{\xi}S_{\rm on-shell}=\int_{r_{c}}$
$\displaystyle\text{d}^{3}x\sqrt{-h}\left({\cal T}_{ij}{\cal
L}_{\xi}h^{ij}+J^{i}(x){\cal L}_{\xi}A_{i}\right.$ (20)
$\displaystyle\left.+{\cal O}(x){\cal L}_{\xi}\Psi^{\dagger}+{\cal
O^{\dagger}}(x){\cal L}_{\xi}\Psi\right)=0\,,$

where ${\cal L}_{\xi}$ denotes the Lie derivative along with $\xi^{i}$ and

$\displaystyle O(x)\equiv\frac{1}{\sqrt{-h}}\frac{\delta S_{\rm on-
shell}}{\delta\Psi^{\dagger}(x)}\,,$ (21) $\displaystyle
J^{i}(x)\equiv\frac{-1}{\sqrt{-h}}\frac{\delta S_{\rm on-shell}}{\delta
A_{i}(x)}\,.$ (22)

Here we call $O(x)$ and $J^{i}(x)$ to be the expectation value of the response
for the source of the complex scalar and the 3-electromagnetic current
respectively, following the usual definitions of holographic duality in
asymptotically anti-de Sitter spacetime Maldacena (1998); Gubser  _et al._
(1998); Witten (1998a, b). Note a similar deduction has also been used to
study superradiance of asymptotically anti-de Sitter black holes Ishii  _et
al._ (2022).

After integrating by parts, the “Ward Identity” for the Brown-York energy
momentum tensor can be derived from the Eq. (20)

$\bar{\nabla}^{j}{\cal
T}_{ij}=-2\Re(O\bar{\nabla}_{i}\Psi^{\dagger})+\bar{\nabla}_{j}J^{j}A_{i}+J^{j}F_{ij}\,.$
(23)

where $\bar{\nabla}_{i}$ denotes the covariant derivative operator for the
induced metric. Additionally, our theory has not only the diffeomorphic
invariance but also the gauge symmetry. The gauge symmetry requires that the
on-shell action $S_{\rm on-shell}$ is invariant under the following gauge
transformation,

$A_{i}\to
A_{i}+\partial_{i}\lambda\,,\quad\Psi\to\text{e}^{i\sigma\lambda}\Psi\,.$ (24)

Specially, for infinitesimal $\lambda$, the gauge invariance implies the
second “Ward Identity” for the current $J^{i}$

$\bar{\nabla}_{i}J^{i}=2\sigma\Im\left(O\Psi^{\dagger}\right)\,.$ (25)

We now consider the physical interpretations on these two “Ward Identities”.
When the complex scalar field vanishes, Eq. (25) becomes
$\bar{\nabla}_{i}J^{i}=0$. This just reflects the charge conservation interior
the box due to the fact that cut-off boundary is insulated with black hole. We
then denote

${\cal P}_{\rm Q}\equiv 2\sigma\Im\left(\Psi^{\dagger}\braket{\cal
O}\right)\,.$ (26)

According to Eq. (25), we interpret ${\cal P}_{\rm Q}$ as the “ charge current
density” via the boundary of the box.

To understand the physical meaning of quantities appearing in the right-side
of Eq. (23), let us denote that $\chi^{i}=\left(\frac{\partial}{\partial
t}\right)^{i}$ is a timelike vector which is tangent to boundary. Define the
energy current $J_{\rm e}^{i}\equiv{\cal T}^{i}{}_{j}\chi^{j}$ and electric
field $E_{i}=\chi^{j}F_{ji}$ at the cut-off boundary, the first “Ward Identity
”, Eq. (23) gives

$\bar{\nabla}_{j}J^{j}_{\rm e}={\cal
T}^{ij}\bar{\nabla}_{i}\chi_{j}-2\Re(O\partial_{t}\Psi^{\dagger})+\mathcal{P}_{Q}A_{t}+J^{i}E_{i}\,.$
(27)

The terms appearing in right-side of Eq. (27) can be explained as follows: The
$J^{i}E_{i}$ stands for the electric power caused by the interaction between
electric field $E_{i}$ and current $J^{i}$ on the boundary; the
$\mathcal{P}_{Q}A_{t}$ stands for the energy increasing caused by the charge
increasing since $A_{t}$ stands for the chemical potential of charge and
$\mathcal{P}_{Q}$ stands for the increasing rate of charge injected into box
via boundary; $-2\Re(O\partial_{t}\Psi^{\dagger})$ stands for the generalized
work caused by complex scalar field. To understand the term ${\cal
T}^{ij}\bar{\nabla}_{i}\chi_{j}$, we decompose the energy momentum tensor and
$\bar{\nabla}_{i}\chi_{j}$ into

${\cal
T}_{ij}=\mathcal{T}h_{ij}+\pi_{ij},~{}~{}\bar{\nabla}_{i}\chi_{j}=\theta
h_{ij}+\sigma_{ij}+\omega_{ij}\,.$ (28)

Here $\pi_{ij}$ stands for the shear stress of cut-off boundary and
$\mathcal{T}$ stands for the trace of $\mathcal{T}_{ij}$. The
$\theta,\sigma_{ij}$ and $\omega_{ij}$ are the trace, the symmetric traceless
and skew-symmetric parts of $\bar{\nabla}_{i}\chi_{j}$, respectively, which
stand for the the expansion, the shear tensor and rotation tensor of time
evolution vector $\chi^{i}$ respectively. We then see that the first term of
the right-side on Eq. (27) reads

${\cal
T}^{ij}\bar{\nabla}_{i}\chi_{j}=\mathcal{T}\theta+\pi_{ij}\sigma^{ij}\,.$ (29)

Here $\mathcal{T}\theta$ stands for the work caused the variation of area of
the boundary and $\pi_{ij}\sigma^{ij}$ stands for the work caused by the shear
stress of boundary. The cut-off boundary can be thought of as an elastic
membrane and Eq. (29) then stands for the work cased by the shape-deformation
of cut-off boundary. Similar to the Eq. (25), we then denote

$\displaystyle{\cal P}_{\rm e}\equiv\bar{\nabla}_{j}J^{j}_{\rm e}$ (30)

and interpret it as the energy flux density via the boundary of the box, i.e.
the power surface density at the boundary, caused by various works of matters
and the deformation of boundary. Specifically, for positive ${\cal P}_{\rm e}$
and ${\cal P}_{\rm Q}$, the box absorbs energy and charge, while for negative
${\cal P}_{\rm e}$ and ${\cal P}_{\rm Q}$, the box loses energy and charge.

###  III.2 Complex scalar in frequency domain

As the first step to study this topic, we now treat the complex scalar as
perturbation and neglect the backreaction of scalar field on spacetime
geometry. This in fact is “quasi-static approximation” and can be applied when
discharging current is small enough. In frequency domain, we consider the
s-wave mode approximation and adopt the Dirichlet boundary condition at the
boundary of the cavity for the scalar field

$\Psi=\text{e}^{-i\omega t}{\cal R}(r)/r\,,\quad{\cal
R}|_{r=r_{c}}=X_{0},~{}~{}\omega\geq 0\,.$ (31)

We further leave $\omega$ and $X_{0}$ as two parameters that we can control.
In frequency domain Broughton and Bryan (2018) and spherically symmetric case,
the equation for the complex scalar field will thus reduce into following from

$\frac{\text{d}^{2}{\cal R}}{\text{d}y^{2}}+U(y,\omega){\cal R}=0\,,$ (32)

Here $y$ is the tortoise coordinate and $U(y,\omega)$ is the effective
potential which depends on bulk metric and the frequency $\omega$. Near
horizon the asymptotical behavior of $U(y,\omega)$ gives universal behavior
$U|_{y\to-\infty}=(\omega-\omega_{h})^{2}$, in which

$\omega_{h}\equiv\sigma\mu_{h}\,,\quad\mu_{h}\equiv Q/r_{+}$ (33)

is the electric potential on the horizon. Since the black hole horizon is a
one-way membrane, we impose the infalling boundary condition of radial
function, namely

${\cal R}(y)=X_{0}{\cal
T}_{h}\text{e}^{-i(\omega-\omega_{h})y},~{}~{}y\rightarrow-\infty\,,$ (34)

in which the transmission amplitude ${\cal T}_{h}$ depends on the parameters
related to our black hole battery as well as the frequency $\omega$ and charge
$\sigma$. In addition, recall the Eq. (21), it is easy to observe that ${O}$
is still a periodic function of time, sharing the same frequency with $\Psi$
in frequency domain. We therefore set

$O=Z_{0}\text{e}^{-i\omega t}/r_{c}\,.$ (35)

Recall the Eq. (31), here we have introduced three coefficients, ${\cal
T}_{h},X_{0}$ and $Z_{0}$, corresponding to the external source and its
respond for the complex scalar, but they are not independent. They are further
connected by the following conserved Wroskain determinant associated with
${\cal R}$ and its complex conjugate,

$\left.{\cal R}^{\dagger}\frac{\text{d}{\cal R}}{\text{d}y}-{\cal
R}\frac{\text{d}{\cal R}^{\dagger}}{\text{d}y}\right|_{r=r_{h}}=\left.{\cal
R}^{\dagger}\frac{\text{d}{\cal R}}{\text{d}y}-{\cal R}\frac{\text{d}{\cal
R}^{\dagger}}{\text{d}y}\right|_{r=r_{c}}\,.$ (36)

giving

$2|X_{0}|^{2}|{\cal
T}_{h}|^{2}(\omega-\omega_{h})=i(X_{0}Z_{0}^{\dagger}-X_{0}^{\dagger}Z_{0})\,.$
(37)

The result can be further simplified if we impose $r_{c}\gg r_{+}$. In this
case the induced metric of cavity is approximated by the metric of a sphere in
flat spacetime and gauge potential at the cavity approximately vanishes. Thus,
the two “Ward Identities" of the boundary, the Eq. (23) and Eq. (26), will
reduce to

$\displaystyle{\cal P}_{\rm
e}=\frac{2\sigma\omega}{r_{c}^{2}}\left(\frac{\omega}{\sigma}-\mu_{h}\right)|X_{0}|^{2}|{\cal
T}_{h}|^{2}\,,$ (38) (39) $\displaystyle{\cal P}_{\rm
Q}=\frac{2\sigma^{2}}{r_{c}^{2}}\left(\frac{\omega}{\sigma}-\mu_{h}\right)|X_{0}|^{2}|{\cal
T}_{h}|^{2}\,.$

This recovers energy flux density and charge current density computed from the
theory of superradiance Brito  _et al._ (2015).

##  IV discharge process

###  IV.1 Effective circuit

We now consider the discharge process. As we have built the theory about
dynamics of black hole in cavity, we can use these results to deal the
discharging process. As the result, the energy flux and charge current of the
cavity are given by Eq. (38). In this approximation the discharging process in
indeed makes use of superradance. Since the $4\pi r_{c}^{2}{\cal P}_{\rm e}$
and $4\pi r_{c}^{2}{\cal P}_{\rm Q}$ stand for the energy and charge
increasing per second inside the cavity, it is thus nature to define the
electric current $I$ and power $P_{d}$ in an effective circuit (See Fig. 2) as

$I=-4\pi r_{c}^{2}{\cal P}_{\rm Q},~{}~{}P_{d}=-4\pi r_{c}^{2}{\cal P}_{\rm
e}\,.$ (40)

Furthermore, we can define the terminal voltage $U_{d}=\omega/\sigma$ and the
electromotive force $U_{\rm bh}=\mu_{h}$. The Eq. (38) can therefore be
written as the Ohm’s Law

$P_{d}=U_{d}I\,,\quad(U_{\rm bh}-U_{d})=IR\,,$ (41)

where the effective internal resistance $R$ of the battery reads

$R\equiv\frac{1}{8\pi\sigma^{2}|{\cal T}_{h}|^{2}|X_{0}|^{2}}\,.$ (42)

Due to the existence of internal resistance, the Joule heat will be created,
which stands for the unavailable work from the battery and will cause the the
increment of entropy. Thus, the discharging is quasi-static but irreversible
process.

Figure 2: The cavity and its interior black hole can work as an usual battery
to supply appliances.

Since the system is quasi-static, the first law of the thermodynamics for the
RN black hole shows

$T\frac{\text{d}S}{\text{d}t}=\frac{\text{d}M}{\text{d}t}-\mu_{h}\frac{\text{d}Q}{\text{d}t}=-P_{d}+\mu_{h}I\,,$
(43)

where $T$ and $S$ denote the Hawking temperature and entropy of the RN black
hole respectively. We thus have

$T\frac{\text{d}S}{\text{d}t}=8\pi\sigma^{2}\left(\frac{\omega}{\sigma}-\mu_{h}\right)^{2}|X_{0}|^{2}|{\cal
T}_{h}|^{2}\,.$ (44)

We see that, in discharging process, the entropy of our black hole battery is
always increasing, following the requirement of Hawking’s area theorem of
black hole horizon. Furthermore, more importantly, from Eqs. (40), (42) and
(44), one will easily find $T\text{d}S=I^{2}R\text{d}t$. This shows that the
increment of entropy exactly corresponds to the heat dissipation produced from
the effective internal resistance of our battery.

Let us now estimate the maximal power of this battery. Since the relaxation
time scale of the system can be estimated by the time that the signal travels
from strong-gravitational-field region (the region near but not very close to
horizon) to the boundary, which gives us the time scale $\mathcal{O}(r_{c})$.
Our quasi-static approximation requires $r_{c}P_{d}\ll M_{0}$. Recover into SI
units, this corresponds the power
$P_{d}\ll\frac{M_{0}/\mathrm{kg}}{r_{c}/\mathrm{m}}\times 10^{25}$W. The
“quasi-static approximation” thus still allows very huge energy power in
practice.

###  IV.2 Efficiency of power supply

As a device of energy supply, the efficiency and power are main parameters to
characterize its performance. Due to the nonzero the effective internal
resistance, the maximal efficiency of discharging will happen when the current
$I\rightarrow 0$. In this case, the thermal dispersion caused by internal
resistance is negligible and our battery can at most transform 25% input mass
into available electric energy. Noting the fact that the an atom bomb only
releases 0.1% energy of its mass. The maximal efficiency of the battery is 250
times higher than that of the atomic bomb. In addition, from Eqs. (40) and
(38) we see that the power is determined by $X_{0}$, which is the boundary
condition of scalar field and can be controlled artificially. Thus, we can
control the battery to release such huge energy in a controllable and slow
way.

An other interesting question, and maybe more more practical concern, is the
maximum power and its corresponding efficiency Curzon and Ahlborn (1975); Van
den Broeck (2005); Esposito  _et al._ (2009). In order to simplify the
discussion, we will apply an additional approximation named “high frequency
approximation”: $\omega M\gg 1$. Then transmission amplitude can be
approximated by $|{\cal T}_{h}|^{2}\approx 1$. This will mean that the
effective resistance becomes constant, namely $R_{0}\equiv R|_{\omega M\gg
1}\approx 1/(8\pi\sigma^{2}|X_{0}|^{2})$. It is from Eq. (38) easy to observe
that there exist an instantaneous maximal output power when the discharging
voltage is half of the electromotive force at every moment $t$, i.e.
$\omega=\mu_{h}/(2\sigma)$. To match the requirement of “high frequency
approximation”, we need

$\frac{\mu_{h}M}{2\sigma}\approx\frac{Q}{4\sigma}\gg 1\,,$ (45)

which is naturally satisfied before the battery is power-off. Since the
parameter $\omega$ is the one that we control according to the boundary
condition, we can tune $\omega$ suitably so that the battery keeps maximal
output power.

The instantaneous maximal output power, as well as the electrical current, are
given as

$P_{d}=\frac{Q^{2}}{16M^{2}R_{0}}\,,\quad I=\frac{Q}{4MR_{0}}\,,$ (46)

which satisfies $P_{d}=I^{2}R_{0}$, i.e. the appliance and internal resistance
have same power. We then can conclude that if our black hole battery works
always at maximal power, only half of stored electrical energy, i.e.
$\mathcal{E}/2$, can be converted into useful work and the battery can
transform 12.5% input mass into available energy. Strictly speaking, when the
the battery is almost power-off, the total charge of black hole $Q\rightarrow
0$. This breaks the bound (45). However, such breaking will only appear in a
very short time scale and so can be neglected.

###  IV.3 Cycle life and totally available energy at maximum power supply

For a neutral black hole confined in a cavity, we can use above mentioned
method to recharge it fully and then discharge it completely. Such process can
be repeated many times and so this battery is rechargeable battery. The “cycle
life”, namely how many times our black hole battery undergoes the mentioned
recharging—discharging cycle processes, and the totally available energy
during its life are two important properties of battery.

After a single recharging—discharging cycle, even though the black hole
battery goes from Schwarzschild black hole to Schwarzschild black hole again,
the entropy increase. The Hawking-Bekenstein entropy formula shows that the
Schwarzschild radius of our black hole battery will always increase after
every such cycle. Consequently, when the radius is near the boundary $r_{c}$,
our black hole battery become unavailable.

Here we consider the case that the exterior black hole is large enough so the
recharging process will stop at “Coulomb domain”. We first obtain the
increment of the Schwarzschild radius for the recharging process $\Delta
r_{+}=(n_{r}^{2}q^{2}/4M_{0}^{2})r_{+}=(m^{2}/4q^{2})r_{+}$ from Eqs. (8) and
(4). To estimate maximal cycle life, we use the minimal power to discharge,
i.e. $I\rightarrow 0$, so that the entropy increment in discharging process is
negligible. Therefore,

$r_{+,n}=\left(1+\frac{m^{2}}{4q^{2}}\right)r_{+,n-1}\,.$ (47)

Here $r_{+,n}$ stands for the black hole radius after $n$ times
recharge—discharge cycle process. It implies that

$r_{+,n}=2M_{0}\left(1+\frac{m^{2}}{4q^{2}}\right)^{n}\,,$ (48)

where we have imposed $r_{+,0}=2M_{0}$ as the initial Schwarzschild radius of
our black hole battery. Furthermore, when $r_{+,N}=r_{c}/\alpha$ with
truncation $\alpha\gtrsim 1$, our horizon is close to the boundary and the
black hole battery’s life comes to the end. The maximal number of the
recharge—discharge cycle process then reads

$N_{\text{max}}\approx\frac{\ln(r_{c}/\alpha)-\ln
2M_{0}}{\ln(1+m^{2}/4q^{2})}\approx\frac{4q^{2}}{m^{2}}\ln\left(\frac{r_{c}}{2M_{0}\alpha}\right)\,.$
(49)

We then obtain an estimation on the maximal total available energy of its
whole life $E_{\rm total,max}\sim N_{\text{max}}\mathcal{E}$. Since
$\mathcal{E}=n_{r}m/4$ and $n_{r}=M_{0}m/q^{2}$ at “Coulomb domain”, we then
have

$E_{\rm total,max}\sim M_{0}\ln\left(\frac{r_{c}}{2M_{0}\alpha}\right)\gg
M_{0}\,.$ (50)

Differing from energy extractions by the Penrose process and superradiance,
the black hole battery during its life can even supply the energy much larger
than its initial mass.

##  V Conclusion

In this paper we argue theoretically that we can use a Schwarzschild black
hole as a rechargeable battery. We propose a way to add “fuel” for this
battery (recharging process) and show that it at most can transform 25% input
mass into electric energy. We show that the recharging and discharging
processes are always irreversible processes, as required by the second law of
black hole physics. To explain our discharging process, we build the theory
about the dynamics of black hole in a cavity. Under the “quasi-static
approximation”, we then further identify the effective internal resistance in
discharging process and show that the Joule heat produced by the effective
resistance is just as same as the amounts required by the laws of black hole
thermodynamics. We study the discharging efficiency, maximum output power,
cycle life and totally available energy. Our black hole battery in its life
can even supply the energy much larger than its initial mass. Differing from
the Penroes process and superradiance, the battery in a complete cycle does
not really extract the energy from black hole inside cavity. Instead, the
black hole plays role of transforming the input mass into electric energy.
Whether or not it is possible in the future to make a black hole work as a
battery discussed in this paper is still an open question. The answer to this
question lies on technological development of the future and is difficult to
predict. The analyses here are very idealized and many details need to be
further supplemented and improved in the future. Though it seems highly
unlikely to realize such battery currently, this basic idea is seemingly an
attractive future proposal towards the crisis of energy.

###### Acknowledgements.

This work is supported by the National Natural Science Foundation of China
under Grant No. 12005155.

##  Appendix A The Condition of mass-charge ratio for dropped charged
Particles

We consider a classical charged sphere with mass $m$ and charge $q$ moving
along the geodesic in the RN black hole background. The action for this sphere
in spherical coordinate $x^{\mu}=(t,r,\theta,\varphi)$ is

$S=\int\text{d}\tau L\,,\quad
L=\frac{1}{2\lambda}g_{\mu\nu}\dot{x}^{\mu}\dot{x}^{\nu}-\frac{\lambda}{2}m^{2}-q\dot{x}^{\mu}A_{\mu}$
(51)

where $\tau$ denotes the affine coefficient and
$\dot{x}^{\mu}\equiv\frac{\text{d}x^{\mu}}{\text{d}\tau}$. $\lambda$ is a
auxiliary field, performing variation respect to which gives the normalization
of 4-velocity that

$g_{\mu\nu}\dot{x}^{\mu}\dot{x}^{\nu}=-1\,.$ (52)

In the background of RN black hole with mass $M$ and charge $Q$, namely

$\text{d}s^{2}=-f\text{d}t^{2}+\frac{\text{d}r^{2}}{f}+r^{2}\text{d}\Omega^{2}_{2}\,,\quad
A_{t}=\frac{Q}{r}\,$ (53)

and $f=1-2M/r+Q^{2}/r^{2}$, if we consider a timelike killing vector
$\chi^{\mu}=(\partial/\partial t)^{\mu}$, the charged particle’s action will
be invariant under the infinitesimal transformation $x^{\mu}\to
x^{\mu}+\epsilon\chi^{\mu}\,,\quad\epsilon\ll 1$, namely

${\cal L}_{\chi}S=-\int\text{d}\tau
q\dot{x}^{\mu}(\chi^{\nu}\partial_{\nu}A_{\mu}+A_{\nu}\partial_{\mu}\chi^{\nu})=0\,,$
(54)

where we have used the Killing equation $\partial_{(\mu}\chi_{\nu)}=0$, as
well as the fact that ${\cal L}_{\chi}g_{\mu\nu}=0$ since the static RN black
hole is not dependent on $t$. It will give the following conserved energy of
the massive charged particle,

$E\equiv\left(1-\frac{2M}{r}+\frac{Q^{2}}{r^{2}}\right)\frac{\text{d}t}{\text{d}\tau}+\frac{qQ}{mr}\,.$
(55)

Since in the recharging process we have $qQ\geq 0$, we see $E>0$. Furthermore,
for simplicity, we consider the initially static particle without angular
momenta, lying on the plane $\theta=\pi/2$. Recall the normalization of
4-velocity. we obtain the radial worldline of this particle as

$\left(\frac{\text{d}r}{\text{d}\tau}\right)^{2}=E^{2}-V_{\rm eff}\,,$ (56)

where the effective potential $V_{\rm eff}$ is

$V_{\rm
eff}=1-\frac{2M}{r}+\frac{2EqQ}{mr}-\left(\frac{q^{2}}{m^{2}}-1\right)\frac{Q^{2}}{r^{2}}\,.$
(57)

In asymptotic flat region, if the particle is relaxed freely at infinity then
we have $E=1$. If it falls into the RN black hole, namely the total
interaction, including gravitational and electrical one, applied to charged
particles are attractive, it is required that

$V_{\rm eff}|_{r\to-\infty}\approx 1+\frac{\alpha}{r}+{\cal
O}\left(\frac{1}{r^{2}}\right)\,,\quad\alpha<0\,.$ (58)

This indicates that

$\frac{m}{q}\geq\frac{Q}{M}\,.$ (59)

Under our requirement $|q|/m\gg 1$, we see that condition (59) then insures

$\left(\frac{\text{d}r}{\text{d}\tau}\right)^{2}=\frac{2M-2Qq/m}{r}+\left(\frac{q^{2}}{m^{2}}-1\right)\frac{Q^{2}}{r^{2}}>0$
(60)

This means that $\text{d}r/\text{d}\tau<0$ outside horizon. Eq. (55) shows

$\frac{\text{d}t}{\text{d}\tau}=\left(1-\frac{Qq}{mr}\right)/f\geq\left(1-\frac{M}{r}\right)/f>\frac{1}{2f}\,,$
(61)

so we find $\text{d}r/\text{d}t\leq 0$ outside black hole. Thus, the particle
will fall from infinity into the horizon without backtracking.

Intriguingly, in context of Newtonian mechanic, this condition also can be
given that the gravitational attraction applied to the charged particles is
larger than the electrical repulsion, leading to these particles falling into
black hole.

## References

  * Hawking (1972) S. W. Hawking, “Black holes in general relativity,” Communications in Mathematical Physics 25, 152–166 (1972).
  * Hawking (1974) S. W. Hawking, “Black hole explosions?” Nature 248, 30 (1974).
  * Penrose and Floyd (1971) Roger Penrose and RM Floyd, “Extraction of rotational energy from a black hole,” Nature Physical Science 229, 177–179 (1971).
  * Chandrasekhar and Chandrasekhar (1998) S. Chandrasekhar and S. Chandrasekhar,  _The Mathematical Theory of Black Holes_ , International series of monographs on physics (Clarendon Press, 1998).
  * Denardo and Ruffini (1973) G Denardo and R Ruffini, “On the energetics of reissner nordström geometries,” Physics Letters B 45, 259–262 (1973).
  * Brito  _et al._ (2015) Richard Brito, Vitor Cardoso, and Paolo Pani, “Superradiance: New Frontiers in Black Hole Physics,” Lect. Notes Phys. 906, pp.1–237 (2015), arXiv:1501.06570 [gr-qc] .
  * Abbott and el. al (2016) B. P. Abbott and el. al (LIGO Scientific Collaboration and Virgo Collaboration), “Observation of gravitational waves from a binary black hole merger,” Phys. Rev. Lett. 116, 061102 (2016).
  * Abbott and et. al (2017) B. P. Abbott and et. al (LIGO Scientific and Virgo Collaboration), “Gw170104: Observation of a 50-solar-mass binary black hole coalescence at redshift 0.2,” Phys. Rev. Lett. 118, 221101 (2017).
  * Schwinger (1951) Julian Schwinger, “On gauge invariance and vacuum polarization,” Phys. Rev. 82, 664–679 (1951).
  * Garriga (1994) Jaume Garriga, “Pair production by an electric field in (1+1)-dimensional de sitter space,” Phys. Rev. D 49, 6343–6346 (1994).
  * Kim (2016) Sang Pyo Kim, “Schwinger Effect, Hawking Radiation, and Unruh Effect,” Int. J. Mod. Phys. D 25, 1645005 (2016), arXiv:1602.05336 [hep-th] .
  * Cai  _et al._ (2020) Rong-Gen Cai, Chiang-Mei Chen, Sang Pyo Kim, and Jia-Rui Sun, “Schwinger effect in near-extremal charged black holes in high dimensions,” Phys. Rev. D 101, 105015 (2020), arXiv:2004.00735 [hep-th] .
  * Bekenstein (1973) Jacob D. Bekenstein, “Black holes and entropy,” Phys. Rev. D 7, 2333–2346 (1973).
  * Bekenstein (1974) Jacob D. Bekenstein, “Generalized second law of thermodynamics in black-hole physics,” Phys. Rev. D 9, 3292–3300 (1974).
  * Bardeen  _et al._ (1973) J. M. Bardeen, B. Carter, and S. W. Hawking, “The four laws of black hole mechanics,” Communications in Mathematical Physics 31, 161–170 (1973).
  * Hawking and Ellis (1973) S. W. Hawking and G. F. R. Ellis,  _The Large Scale Structure of Space-Time_ (Cambridge University Press, New York, 1973).
  * Brown and York (1993) J. David Brown and James W. York, “Quasilocal energy and conserved charges derived from the gravitational action,” Phys. Rev. D 47, 1407–1419 (1993).
  * Brown  _et al._ (2002) J.D Brown, S.R Lau, and J.W York, “Action and energy of the gravitational field,” Annals of Physics 297, 175–218 (2002).
  * Szabados (2004) László B. Szabados, “Quasi-local energy-momentum and angular momentum in GR: A review article,” Living Reviews in Relativity 7 (2004), 10.12942/lrr-2004-4.
  * Maldacena (1998) Juan Martin Maldacena, “The Large N limit of superconformal field theories and supergravity,” Adv. Theor. Math. Phys. 2, 231–252 (1998), arXiv:hep-th/9711200 .
  * Gubser  _et al._ (1998) S. S. Gubser, Igor R. Klebanov, and Alexander M. Polyakov, “Gauge theory correlators from noncritical string theory,” Phys. Lett. B 428, 105–114 (1998), arXiv:hep-th/9802109 .
  * Witten (1998a) Edward Witten, “Anti-de Sitter space and holography,” Adv. Theor. Math. Phys. 2, 253–291 (1998a), arXiv:hep-th/9802150 .
  * Witten (1998b) Edward Witten, “Anti-de Sitter space, thermal phase transition, and confinement in gauge theories,” Adv. Theor. Math. Phys. 2, 505–532 (1998b), arXiv:hep-th/9803131 .
  * Ishii  _et al._ (2022) Takaaki Ishii, Youka Kaku, and Keiju Murata, “Energy extraction from AdS black holes via superradiance,” (2022), arXiv:2207.03123 [hep-th] .
  * Broughton and Bryan (2018) S. Allen Broughton and Kurt Bryan,  _Discrete Fourier Analysis and Wavelets_ , 2nd ed. (Wiley, 2018).
  * Curzon and Ahlborn (1975) F. L. Curzon and B. Ahlborn, “Efficiency of a carnot engine at maximum power output,” American Journal of Physics 43, 22–24 (1975).
  * Van den Broeck (2005) C. Van den Broeck, “Thermodynamic efficiency at maximum power,” Phys. Rev. Lett. 95, 190602 (2005).
  * Esposito  _et al._ (2009) Massimiliano Esposito, Katja Lindenberg, and Christian Van den Broeck, “Universality of efficiency at maximum power,” Phys. Rev. Lett. 102, 130602 (2009).


On the Wiener Index of Orientations of Graphs

Peter Dankelmann111Financial support by the South African National Research
Foundation, grant 118521, is gratefully acknowledged
University of Johannesburg

###### Abstract

The Wiener index of a strong digraph $D$ is defined as the sum of the
distances between all ordered pairs of vertices. This definition has been
extended to digraphs that are not necessarily strong by defining the distance
from a vertex $a$ to a vertex $b$ as $0$ if there is no path from $a$ to $b$
in $D$.

Knor, S̆krekovski and Tepeh [Some remarks on Wiener index of oriented graphs.
Appl. Math. Comput. 273] considered orientations of graphs with maximum Wiener
index. The authors conjectured that for a given tree $T$, an orientation $D$
of $T$ of maximum Wiener index always contains a vertex $v$ such that for
every vertex $u$, there is either a $(u,v)$-path or a $(v,u)$-path in $D$. In
this paper we disprove the conjecture.

We also show that the problem of finding an orientation of maximum Wiener
index of a given graph is NP-complete, thus answering a question by Knor,
S̆krekovski and Tepeh [Orientations of graphs with maximum Wiener index.
Discrete Appl. Math. 211].

We briefly discuss the corresponding problem of finding an orientation of
minimum Wiener index of a given graph, and show that the special case of
deciding if a given graph on $m$ edges has an orientation of Wiener index $m$
can be solved in time quadratic in $n$.

Keywords: Wiener index, average distance, orientation, digraph, NP-complete.

##  1 Introduction

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

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

where $V$ is the vertex set of $G$ and $d_{G}(u,v)$ denotes the distance
between $u$ and $v$, i.e., the length a shortest $(u,v)$-path. The Wiener
index, originally introduced as a tool in chemistry [10], has been studied
extensively in the mathematical and chemical literature and is arguably one of
the most applicable graph invariants.

The definition of Wiener index extends naturally to strong digraphs. If $D$ is
a strong digraph with vertex set $V$, then the Wiener index of $D$ is defined
as

$W(D)=\sum_{(u,v)\in V\times V}d_{D}(u,v),$

where $V\times V$ is the set of all ordered pairs of vertices of $D$. The
Wiener index of a graph (digraph) is closely related to the average distance,
defined as the arithmetic mean of the distances between all unordered
(ordered) pairs of distinct vertices. For recent results on the Wiener index
of strong digraphs see, for example, [4] and [2].

Knor, S̆krekovski and Tepeh [5] extended the definition of the Wiener index to
digraphs that are not necessarily strong by defining the distance $d_{D}(u,v)$
as the length of a shortest $(u,v)$-path if $D$ contains a $(u,v)$-path, and
as $0$ if no $(u,v)$-path exists in $D$. In [7] the same authors gave further
results on the Wiener index, for example they showed that the Wiener index of
a tournaments of order $n$ cannot exceed $\binom{n+1}{3}-1$, which had
previously been proved by Plesník [8] for tournaments that are strong.

The Wiener index of orientations of graphs was investigated first in [1],
where strong orientations of a given graph that minimise the Wiener index were
considered. Applying their more general definition of distance in digraphs,
Knor, S̆krekovski and Tepeh [5, 7] considered (not necessarily strong)
orientations of graphs that maximise or minimise the Wiener index. Among
several other results, they demonstrated that it is not true in general that
an orientation of a given graph maximising the Wiener index is necessarily
strong.

In this paper we resolve two open questions related to orientations of maximum
Wiener index by Knor, S̆krekovski and Tepeh. Considering trees, they
conjectured the following result.

######  Conjecture 1 ([5]).

Let $T$ be a tree. If $D$ is an orientation of $T$ that maximises $W(D)$, then
there exists a vertex $v$ in $D$ such that for every vertex $u$ there exists a
$(u,v)$-path or a $(v,u)$-path in $D$.

We prove that this conjecture is not true in general. We also consider the
question whether finding an orientation of maximum Wiener index of a given
graph is NP-hard, posed in [7], and answer it in the affirmative. Finally, we
briefly discuss the problem of finding an orientation of minimum Wiener index
of a given graph.

We use the following notation. We denote the vertex set of a graph (digraph,
mixed graph) $G$ by $V(G)$, and the edge set or arc set by $E(G)$, leaving out
the argument $G$ if there is no danger of confusion. Generally, $uv$ denotes
an undirected edge, while $\overrightarrow{uv}$ denotes a directed edge which
is directed from $u$ to $v$.

The converse of a digraph $D$ is the digraph obtained from $D$ by reversing
the direction of every arc of $D$.

A Hamiltonian path in a graph $G$ is a path that contains all vertices of $G$.

##  2 A Counter-example to Conjecture 1

Conjecture 1 is supported by results in [5], which show that it is true for
some subclasses of trees. Since it is reasonable to expect that an orientation
of a tree maximising the Wiener index also maximises the number of pairs of
vertices $(u,v)$ between which there exists a path, the following result due
to Henning and Oellermann [3] which gives further support to Conjecture 1.

######  Theorem 1 ([3]).

Let $T$ be a tree, and $D$ an orientation of $T$ that maximises the number of
ordered pairs $(u,v)$ of vertices of $D$ for which there exists a $(u,v)$-path
in $D$. Then $D$ contains a vertex $w$ so that for every vertex $u$ there
exists a $(u,w)$-path or a $(w,u)$-path in $D$.

Nevertheless, we found that Conjecture 1 is not true in general. In this
section we present an infinite family of counter-examples to Conjecture 1.

Let $D$ be an orientation of a tree $T$. Following [5], we say that $D$ is
zig-zag if $T$ contains a path $P$ whose edges change their direction in $D$
at least twice as $P$ is traversed. It was observed in [5] that an orientation
$D$ of a tree is not zig-zag if and only if $D$ has a vertex $w$ so that for
every vertex $u$ of $D$ there exists either a $(u,w)$-path or a $(w,u)$-path.
Conjecture 1 was given in [5] in an equivalent form, stating that for a given
tree $T$, every orientation of $T$ that has maximum Wiener index is not zig-
zag.

We construct a family of counter-examples to Conjecture 1 as follows. Let
$k\in\mathbb{N}$ be a multiple of $3$. Let $T_{k}$ be the tree obtained from a
path of order $k$ with vertices $w_{1},w_{2},\ldots,w_{k}$ by appending
vertices $u_{1},u_{2},\ldots,u_{k^{2}/9}$ to $w_{1}$, appending a path
$x_{1},x_{2},x_{3},x_{4},x_{5}$ to $w_{2}$, and a single vertex $y_{1}$ to
$w_{3}$. A sketch of the tree $T_{k}$ is shown in Figure 1.

$u_{k^{2}/9}$$u_{2}$$u_{1}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$y_{1}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{k}$
Figure 1: The tree $T_{k}$.
$u_{k^{2}/9}$$u_{2}$$u_{1}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$y_{1}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$$w_{k}$
Figure 2: The orientation of $D_{k}$ of $T_{k}$.

Let $D_{k}$ be the orientation of $T_{k}$ shown in Figure 2, i.e., the edges
of the path $w_{1},w_{2},\ldots,w_{k}$ are oriented towards $w_{k}$, each edge
$u_{i}w_{1}$ is oriented towards $w_{1}$, the edges of the path
$w_{2},x_{1},x_{2},\ldots,x_{5}$ are oriented towards $x_{5}$, and the edge
$y_{1}w_{3}$ is oriented towards $w_{3}$. Notice that the edges of the
$(x_{5},y_{1})$-path change their direction twice as the path is traversed,
hence $D_{k}$ is zig-zag.

It will be convenient to consider mixed graphs, which are a common
generalisation of graphs and digraphs. A mixed graph consists of a set of
vertices and a set of edges, where each edge may or may not have a direction.
For vertices $u,v$ of a mixed graph $G$, a $(u,v)$-path is a sequence
$v_{0},v_{1},\ldots,v_{k}$ of vertices with $u=v_{0}$ and $v=v_{k}$ so that
for each $i\in\\{0,1,\ldots,k-1\\}$, the directed edge
$\overrightarrow{v_{i}v_{i+1}}$ or the undirected edge $v_{i}v_{i+1}$ is in
$G$. As usual, the distance from $u$ to $v$ is the minimum number of edges on
a $(u,v)$-path, which we denote by $d_{G}(u,v)$. By a partial orientation of a
mixed graph $G$ we mean a mixed graph obtained from $G$ by orienting some of
the undirected edges of $G$.

In order to compare the Wiener index of a tree and its (partial) orientations,
we introduce the following modification of the Wiener index For a mixed graph
$G$ define

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

For disjoint subsets $A,B\subseteq V$ we use the notation
$W^{max}_{G}(A,B):=\sum_{\ a\in A,b\in B}\max\\{d_{G}(a,b),d_{G}(b,a)\\}$.

######  Lemma 1.

(a) If $T$ is a tree, then

$W^{max}(T)=W(T).$

(b) If $D$ is an orientation of a tree $T$, then

$W^{max}(D)=W(D).$

(c) If $D_{1}$ is a partial orientation of z tree $T$, and $D_{2}$ a partial
orientation of $D_{1}$, then

$W^{max}(D_{2})\leq W^{max}(D_{1})\leq W(T).$

(d) Let $T$ be a tree, $D_{1}$ a partial orientation of $T$, and $D_{2}$ a
partial orientation of $D_{1}$. If $A$ and $B$ are disjoint sets of vertices
of $T$ such that there is no path in $D_{2}$ between a vertex in $A$ and a
vertex in $B$ in either direction, then

$W^{max}(D_{2})\leq W^{max}(D_{1})-W^{max}_{D_{1}}(A,B).$

Proof: We denote the vertex set of $T$ and its (partial) orientations by $V$.
(a) Since $T$ is an undirected graph, we have
$d_{T}(u,v)=d_{T}(v,u)=\max\\{d_{T}(u,v),d_{T}(v,u)\\}$ for any two vertices
$u,v$ of $T$. Summation over all subsets $\\{u,v\\}\subseteq V$ yields that
$W^{max}(T)=W(T)$.
(b) If $u,v\in V$ are two vertices of $T$, then the $(u,v)$-path and the
$(v,u)$-path are unique in $T$. At most one these two paths is also a path in
$D$, thus $d_{D}(u,v)=0$ or $d_{D}(v,u)=0$. Hence
$\max\\{d_{D}(u,v),d_{D}(v,u)\\}=d_{D}(u,v)+d_{D}(v,u)$. Summation over all
subsets $\\{u,v\\}\subseteq V$ yields the statement of (b).
(c) Let $u,v$ be two vertices of $T$. If there is a $(u,v)$-path in $D_{2}$,
then this path is also a $(u,v)$-path in $D_{1}$, and if there is a
$(u,v)$-path in $D_{1}$, then this path is also a $(u,v)$-path in $T$. In all
cases, the $(u,v)$-path is unique if it exists. It follows that
$d_{D_{2}}(u,v)\leq d_{D_{1}}(u,v)\leq d_{T}(u,v)$. Hence, for all $u,v\in V$,

$\max\\{d_{D_{2}}(u,v),d_{D_{2}}(v,u)\\}\leq\max\\{d_{D_{1}}(u,v),d_{D_{1}}(v,u)\\}\leq
d_{T}(u,v).$ (1)

Summation over all subsets $\\{u,v\\}\subseteq V(T)$ yields (c).
(d) Let ${\cal C}$ be the set of all $2$-vertex subsets of $V$ which do not
consist of a vertex of $A$ and a vertex of $B$. Then
$\max\\{d_{D_{2}}(u,v),d_{D_{2}}(v,u)\\}=0$ whenever $\\{u,v\\}\notin{\cal
C}$. Hence, by (1),

$\displaystyle W^{max}(D_{2})$ $\displaystyle=$
$\displaystyle\sum_{\\{u,v\\}\in{\cal
C}}\max\\{d_{D_{2}}(u,v),d_{D_{2}}(v,u)\\}$ $\displaystyle\leq$
$\displaystyle\sum_{\\{u,v\\}\in{\cal
C}}\max\\{d_{D_{1}}(u,v),d_{D_{1}}(v,u)\\}$ $\displaystyle=$ $\displaystyle
W^{max}(D_{1})-W^{max}_{D_{1}}(A,B),$

as desired. $\Box$

######  Theorem 2.

Let $k\in\mathbb{N}$ be a multiple of $3$. Let $D_{k}$ be the orientation of
$T_{k}$ as defined above, and let $D$ be any orientation of $T_{k}$. If $k$ is
sufficiently large, then

$W(D)\leq W(D_{k}),$ (2)

with equality if and only if $D$ equals $D_{k}$ or the converse of $D_{k}$.

Proof: We first determine the Wiener indices of $T_{k}$ and $D_{k}$. Tedious
but straightforward calculations show that

$W(T_{k})=\frac{11}{162}k^{4}+\frac{2}{9}k^{3}+\frac{55}{9}k^{2}+\frac{35}{6}k+61$
(3)

and

$W(D_{k})=\frac{1}{18}k^{4}+\frac{2}{9}k^{3}+\frac{59}{18}k^{2}-\frac{5}{3}k+56.$
(4)

It suffices to prove the theorem for orientations of $T_{k}$ of maximum Wiener
index. Let $D$ be such an orientation of $T_{k}$. Then $W^{max}(D)$ is maximum
among all orientations of $T_{k}$ by Lemma 1(b). We may further assume that
$\overrightarrow{w_{1}w_{2}}\in E(D)$; otherwise we consider the converse of
$D$. We prove that $D=D_{k}$ for sufficiently large values of $k$.

Let $V$ be the common vertex set of $T_{k}$, $D_{k}$ and $D$. We partition $V$
into four sets, $U$, $W$, $X$ and $Y$, where
$U=\\{u_{1},u_{2},\ldots,u_{k^{2}/9}\\}$, $W=\\{w_{1},w_{2},\ldots,w_{k}\\}$,
$X=\\{x_{1},x_{2},x_{3},x_{4},x_{5}\\}$, and $Y=\\{y_{1}\\}$.
Claim 1: $D$ contains a $(w_{1},w_{4})$-path.
Suppose to the contrary that $D$ contains no $(w_{1},w_{4})$-path. Since
$\overrightarrow{w_{1}w_{2}}\in E(D)$, there is also $(w_{4},w_{1})$-path in
$D$. Hence $D$ contains no path between a vertex in $U$ and a vertex in
$W-\\{w_{1},w_{2},w_{3}\\}$ in either direction. Applying Lemma 1(c) to the
two suborientations $T_{k}$ and $D$ of $T_{k}$ we obtain that

$W^{max}(D)\leq W^{max}(T_{k})-W^{max}_{T_{k}}(U,W-\\{w_{1},w_{2},w_{3}\\}).$

An easy calculation shows that
$W^{max}_{T_{k}}(U,W-\\{w_{1},w_{2},w_{3}\\})=\frac{1}{18}k^{4}+\frac{1}{18}k^{3}-\frac{2}{3}k^{2}$.
Since $W^{max}(T_{k})=W(T_{k})$ by Lemma 1(a), we thus obtain from (3) that

$\displaystyle W^{max}(D)$ $\displaystyle\leq$
$\displaystyle\big{(}\frac{11}{162}k^{4}+\frac{2}{9}k^{3}+\frac{55}{9}k^{2}+\frac{35}{6}k+61\big{)}-\big{(}\frac{1}{18}k^{4}+\frac{1}{18}k^{3}-\frac{2}{3}k^{2}\big{)}$
$\displaystyle=$
$\displaystyle\frac{2}{162}k^{4}+\frac{1}{6}k^{3}+\frac{61}{9}k^{2}+\frac{35}{6}k+61.$

Comparing this with the right hand side of (4), it is easy to see that
$W^{max}(D)<W^{max}(D_{k})$ for sufficiently large $k$. This contradiction to
the maximality of $W^{max}(D)$ proves Claim 1.
Claim 2: $D$ contains a $(w_{1},w_{k})$-path.
Suppose to the contrary that $D$ does not contain a $(w_{1},w_{k})$-path. Let
$i$ be the smallest value for which there exists no $(w_{1},w_{i})$-path. By
Claim 1 we have $i\geq 5$. Then $w_{i-1}$ is adjacent from $w_{i-2}$ and
$w_{i}$, and not adjacent to any vertex in $D$. Reversing all arcs along the
path $w_{i-1},w_{i},\ldots,w_{k}$ does not reduce
$\max\\{d_{D}(u,v),d_{D}(v,u)\\}$ for any pair of vertices, but increases
$\max\\{d_{D}(w_{i-2},w_{i}),d_{D}(w_{i},w_{i-2})\\}$, contradicting the
maximality of $W^{max}(D)$. Claim 2 follows.
Claim 3: $\overrightarrow{u_{i}w_{1}}\in E(D)$ for all
$i\in\\{1,2,\ldots,\frac{k^{2}}{9}\\}$.
Suppose to the contrary that $\overrightarrow{w_{1}u_{i}}\in E(D)$ for some
$i$. Reversing the arc $\overrightarrow{w_{1}u_{i}}$ creates paths from
$u_{i}$ to all vertices of $W$, whose total length is
$\sum_{j=1}^{k}d_{T_{k}}(u_{i},w_{j})=\frac{k(k+1)}{2}$, but destroys only
paths from vertices in $\\{w_{1}\\}\cup(U-\\{u_{i}\\})$ to $u_{i}$, whose
total length is not more than $1+2(|U|-1)=\frac{2}{9}k^{2}-1$. Since
$\frac{k(k+1)}{2}>2\frac{k^{2}}{9}-1$, reversing the arc
$\overrightarrow{w_{1}u_{i}}$ increases the Wiener index, a contradiction to
the maximality of $W^{max}(D)$. Claim 3 follows.
Let $D_{k}^{\prime}$ be the partial orientation of $T_{k}$ in which for
$i=1,2,\ldots,k-1$ the edge $w_{i}w_{i+1}$ receives the orientation
$\overrightarrow{w_{i}w_{i+1}}$, and for each $u_{j}\in U$ the edge
$u_{j}w_{1}$ received the orientation $\overrightarrow{u_{j}w_{1}}$, while the
remaining edges have not been oriented. It follows from Claims 2 and 3 that
$D$ is a suborientation of $D_{k}^{\prime}$. A simple calculation shows that

$W^{max}(D_{k}^{\prime})=\frac{1}{18}k^{4}+\frac{2}{9}k^{3}+\frac{56}{9}k^{2}+\frac{35}{6}k+61.$

Claim 4: $D$ contains a $(w_{2},x_{5})$-path.
We first show that $\overrightarrow{w_{2}x_{1}}\in E(D)$. Suppose to the
contrary that $\overrightarrow{x_{1}w_{2}}\in E(D)$. Then $D$ contains no path
between a vertex of $X$ and a vertex of $U$ in either direction. Applying
Lemma 1(d) to $D_{k}^{\prime}$ and $D$ yields

$\displaystyle W^{max}(D)$ $\displaystyle\leq$ $\displaystyle
W^{max}(D_{k}^{\prime})-W^{max}_{D_{k}^{\prime}}(U,X)$ $\displaystyle=$
$\displaystyle\big{(}\frac{1}{18}k^{4}+\frac{2}{9}k^{3}+\frac{56}{9}k^{2}+\frac{35}{6}k+61\big{)}-\frac{25}{9}k^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{18}k^{4}+\frac{2}{9}k^{3}+\frac{31}{9}k^{2}+\frac{35}{6}k+61,$

and so, since
$W^{max}(D_{k})=\frac{1}{18}k^{4}+\frac{2}{9}k^{3}+\frac{59}{18}k^{2}+O(k)$,
it follows that $W^{max}(D)<W^{max}(D_{k})$ for sufficiently large $k$, a
contradiction to the maximality of $W^{max}(D)$. Hence
$\overrightarrow{w_{2}x_{1}}\in E(D)$. Similar arguments as in the proof of
Claim 2 now prove that $D$ contains a path from $w_{2}$ to $x_{5}$. Claim 4
follows.
Let $D_{k}^{\prime\prime}$ be the partial orientation of $D_{k}^{\prime}$ in
which the edges of the $(w_{2},x_{1})$-path are oriented towards $x_{5}$.
It follows from Claims 1 to 4 that $D$ is an orientation of
$D_{k}^{\prime\prime}$.
Claim 5: $D=D_{k}$.
Only the edge $y_{1}w_{3}$ of $D_{k}^{\prime\prime}$ has not received an
orientation. Hence $D_{k}^{\prime\prime}$ has two orientations. $D_{k}$ (in
which $y_{1}w_{3}$ receives the orientation $\overrightarrow{y_{1}w_{3}}$) and
the orientation in which $y_{1}w_{3}$ receives the orientation
$\overrightarrow{w_{3}y_{1}}$, which we denote by
$D_{k}^{\prime\prime\prime}$. Clearly,
$d_{D_{k}}(u,v)=d_{D_{k}^{\prime\prime\prime}}(u,v)$ for all $u,v\in
V-\\{y_{1}\\}$. Hence

$\displaystyle W^{max}(D_{k})-W^{max}(D_{k}^{\prime\prime\prime})$
$\displaystyle=$ $\displaystyle
W^{max}_{D_{k}}(\\{y_{1}\\},V-\\{y_{1}\\})-W^{max}_{D_{k}^{\prime\prime\prime}}(\\{y_{1}\\},V-\\{y_{1}\\})$
$\displaystyle=$
$\displaystyle\sum_{v\in\\{w_{3},w_{4},\ldots,w_{k}\\}}d_{D_{k}}(y_{1},v)-\sum_{v\in
U\cup X\cup\\{w_{1},w_{2},w_{3}\\}}d_{D_{k}^{\prime\prime\prime}}(v,y_{1})$
$\displaystyle=$
$\displaystyle(\frac{1}{2}k^{2}-2k+\frac{3}{2})-(\frac{4}{9}k^{2}-6),$

which is positive for $k$ sufficiently large. Hence
$W^{max}(D_{k})>W^{max}(D_{k}^{\prime\prime\prime})$. Claim 5 and thus the
theorem follows. $\Box$

Since by Theorem 2 the only orientations of $T_{k}$ that maximise the Wiener
index are $D_{k}$ and its converse, and both are zigzag, it follows that
Conjecture 1 is not true in general.

##  3 Complexity of finding an orientation of maximum Wiener index

In this section we consider the problem of finding a (not necessarily strong)
orientation of a given graph that maximises the Wiener index. Knor,
S̆krekovski and Tepe [7] asked whether this problem is NP-hard, and we answer
this question in the affirmative. Specifically, we consider the decision
problem
Wiener-Orientation: Given a graph $G$ and an integer $M$. Does $G$ have a (not
necessarily strong) orientation $D$ with $W(D)\geq M$?
We prove the NP-completeness of Wiener-Orientation by a transformation from
the NP-complete problem Hamiltonian $(a,b)$-Path, defined below.
Hamiltonian $(a,b)$-path: Given a graph $G$ and two vertices $a$ and $b$ of
$G$. Does $G$ have a Hamiltonian path that begins in $a$ and ends in $b$?
In our proof we use the following notation. Let $D$ be a digraph with vertex
set $V$ and let $A$ and $B$ be disjoint subsets of $V$. Then we write
$W_{D}(A,B)$ for $\sum_{a\in A,b\in B}d_{D}(a,b)$, and $W_{D}(A)$ for
$\sum_{(a_{1},a_{2})\in A\times A}d_{D}(a_{1},a_{2})$.

Given a graph $G$ of order $n$ and two vertices $a$ and $b$ of $G$, we define
$G^{a,b}$ to be the graph of order $n^{3}+n+2$ obtained from $G$ by adding
$2n^{3}+2$ new vertices $a_{0},a_{1},\ldots,a_{n^{3}}$ and
$b_{0},b_{1},\ldots,b_{n^{3}}$ and edges $aa_{0}$ and $bb_{0}$, as well as
edges $a_{0}a_{i}$ and $b_{0}b_{i}$ for $i=1,2,\ldots,n^{3}$. A sketch of the
graph $G^{a,b}$ is given in Figure 3.

$a_{n^{3}}$$a_{2}$$a_{1}$$a_{0}$$a$$b_{n^{3}}$$b_{2}$$b_{1}$$b$$b_{0}$$G$
Figure 3: The graph $G^{a,b}$.

######  Lemma 2.

Let $M(n):=n^{7}+3n^{6}+2n^{4}+4n^{3}+n+1$. Then there exists
$N_{0}\in\mathbb{N}$ such that for every graph $G$ of order $n$, where $n\geq
N_{0}$, with vertices $a,b$, the following are equivalent:
(i) $G$ has a Hamiltonian path from $a$ to $b$,
(ii) $G^{a,b}$ has an orientation $D$ with $W(D)\geq M(n)$.

Proof: Denote the sets $\\{a_{0},a_{1},\ldots,a_{n^{3}}\\}$ by $A$ and
$\\{b_{0},_{1},\ldots,b_{n^{3}}\\}$ by $B$, and the vertex set of $G$ by $V$.
To prove the forward implication assume that $G$ has a Hamiltonian path
$P:v_{1},v_{2},\ldots,v_{n}$, where $v_{1}=a$ and $v_{n}=b$. Orient each edge
$v_{i}v_{i+1}$ of $P$ forward, i.e., as $\overrightarrow{v_{i}v_{i+1}}$, and
orient all edges of the form $v_{i}v_{j}$ with $i<j-1$ backward, i.e., as
$\overrightarrow{v_{j}v_{i}}$. In the resulting orientation we have
$d(v_{1},v_{n})=n-1$. Now orient $a_{0}a$ and $bb_{0}$ as
$\overrightarrow{a_{0}a}$ and $\overrightarrow{bb_{0}}$, and orient the edges
$a_{i}a_{0}$ towards $a_{0}$ and the edges $b_{i}b_{0}$ towards $b_{i}$ for
$i=1,2,\ldots,n^{3}$. Denote the resulting digraph by $D$. Then
$d_{D}(a_{i}.b_{j})=n+3$, $d_{D}(a_{0},b_{j})=d_{D}(a_{i},b_{0})=n+2$ and
$d_{D}(a_{0}.b_{0})=n+1$ for all $i,j\in\\{1,2,\ldots,n^{3}\\}$. Hence

$W(D)\geq W_{D}(A,B)=n^{6}(n+3)+2n^{3}(n+2)+n+1=M(n),$

as desired.

For the converse assume that $G$ has order $n$, with $n\geq N_{0}$ (with
$N_{0}$ to be determined later) and that $G^{a,b}$ has an orientation $D$ with
$W(D)\geq M(n)$. We may assume that $\overrightarrow{a_{0}a}\in D$ since
otherwise, if $\overrightarrow{aa_{0}}\in E(D)$ we consider the converse of
$D$. In order to show that $G$ has Hamiltonian path from $a$ to $b$ it
suffices to show that

$d_{D}(a,b)=n-1.$

Suppose not. Then $d_{D}(a,b)\leq n-2$. We obtain a contradiction by showing
that this implies that $W(D)<M(n)$. Since $\overrightarrow{a_{0}a}\in E(D)$,
there is no path from a vertex in $V\cup B$ to a vertex in $A$, so
$W_{D}(V,A)=W_{D}(B,A)=0$. Hence

$W(D)=W_{D}(A\cup B)+W_{D}(V)+W_{D}(A,V)+W_{D}(B,V)+W_{D}(V,B).$ (5)

We first bound $W_{D}(A\cup B)$. Clearly, $W_{D}(A\cup
B)=W_{D}(A)+W_{D}(B)+W_{D}(A,B)$. Let $x$ be the number of out-neighbours of
$a_{0}$ in $A$, and Let $y$ be the number of in-neighbours of $b_{0}$ in $B$.
Then $a_{0}$ has $n^{3}-x$ in-neighbours in $A$, and $b_{0}$ has $n^{3}-x$
out-neighbours in $B$. Then $A$ contains $x(n^{3}-x)$ pairs of vertices at
distance $2$ and $n^{3}$ pairs of vertices at distance $1$, hence
$W_{D}(A)=2x(n^{3}-x)+n^{3}$. Similarly we have $W_{D}(B)=2y(n^{3}-y)+n^{3}$.
Now $d_{D}(a_{0},b_{0})\leq n$ and the distance between the in-neighbours of
$a_{0}$ in $A$ and the out-neighbours of $b_{0}$ in $B$ is at most $n+2$. By a
straighforward calculation we thus get
$W_{D}(A,B)\leq(n^{3}+1-x)(n^{3}+1-y)(n+2)-(2n^{3}-x-y+2)$. In total we thus
obtain

$W_{D}(A\cup B)\leq
2x(n^{3}-x)+2y(n^{3}-y)+(n^{3}+1-x)(n^{3}+1-y)(n+2)+x+y-2,$

It is easy to see that for $0\leq x,y\leq n^{3}$ the right hand side of the
above inequality is maximised if $x=y=0$. Hence

$W_{D}(A\cup B)\leq(n^{3}+1)^{2}(n+2)-2=n^{7}+2n^{6}+O(n^{5}).$ (6)

Each of the remaining terms on the right hand side of (5) is $O(n^{5})$.
Indeed, $W_{D}(V)$ is a sum of $n(n-1)$ terms, each of which is at most $n-1$.
Also $W_{D}(A,V)$ is the sum of $(n^{3}+1)n$ terms, each of which is not more
than $n+1$, so $W_{D}(A,V)=O(n^{5})$. Similarly $W_{D}(B,V)=O(n^{5})$ and
$W_{D}(V,B)=O(n^{5})$. Therefore, (5) implies that

$W(D)\leq n^{7}+2n^{6}+O(n^{5}).$ (7)

Since $M(n)=n^{7}+3n^{6}+O(n^{5})$, there exists $N_{0}\in\mathbb{N}$ such
that for every $n\in\mathbb{N}$ with $n\geq N_{0}$, the right hand side of (7)
is less than $M(n)$. If $n\geq N_{0}$, we thus have

$W(D)<M(n),$

contradicting our assumption that $W(D)\geq M(n)$. The lemma follows. $\Box$

######  Theorem 3.

Wiener-Orientation is NP-complete.

Proof: Our proof is by transformation from Hamiltonian $(a,b)$-path. Let
$N_{0}$ and $M(n)$ be as in Lemma 2.

Given a graph $G$ of order $n$ and vertices $a,b$ of $G$,

If $n<N_{0}$, then we can determine in constant time if $G$ has a Hamiltonian
$(a,b)$-path, for example by considering all sequences of $n$ vertices if they
form an $(a,b)$-path.

If $n\geq N_{0}$, then consider $G^{a,b}$. Clearly, $G^{a,b}$ can be obtained
from $G$ in polynomial time. Using $G^{a,b}$ and $M(n)$ as an instance for
Wiener Orientation, we decide if $G^{a,b}$ has an orientation of Wiener index
at least $M(n)$. By Lemma 2, graph $G$ has a Hammiltonian $(a,b)$-path if and
only if $G^{a,b}$ has an orientation of Wiener index at least $M(n)$. $\Box$

##  4 Orientations of minimum Wiener index

We conclude this paper by briefly discussing the corresponding minimisation
problem, also raised in [7]: Given a graph $G$, find a (not necessarily
strong) orientation of $G$ that minimises the Wiener index. It was shown by
Plesník [8] that this problem becomes NP-complete if we allow only strong
orientations.

We do not know if the problem of finding a (not necessarily strong)
orientations of minimum Wiener index of a given graph is NP-hard. However, it
is easy to see that every orientation of a graph $G$ with $m$ edges has Wiener
index at least $m$, and below we show that it can be decided in polynomial
time if a given graph with $m$ edges has an orientation of Wiener index $m$

A digraph $D$ is transitive if it has the property that whenever there is a
path from a vertex $u$ to a vertex $v$ in $D$, then $D$ contains the edge
$\overrightarrow{uv}$. The following observation is straightforward.

######  Observation 1.

Let $D$ be a digraph with $m$ edges. Then $W(D)\geq m$, with equality if and
only if $D$ is transitive.

For a given graph $G$ of order $n$ and size $m$ it follows thus that every
orientation has Wiener index at least $m$, and that there exists an
orientation with Wiener index $m$ if and only if $G$ has a transitive
orientation. It can be decided in time $O(n^{2})$ (see for example [9]) if a
given graph has a transitive orientation. It follows there exists an algorithm
of time complexity $O(n^{2})$ that decides if $G$ has an orientation of Wiener
index $m$.

## References

  * [1] P. Dankelmann, O.R. Oellermann, J.L. Wu, Minimum average distance of strong orientations of graphs. Discrete Appl. Math. 143 no. 1-3 (2004), 204-212.
  * [2] P. Dankelmann, On average distance in tournaments and Eulerian digraphs. Discrete Appl. Math. 266 (2019), 38-47.
  * [3] M.A. Henning, O.R. Oellermann, The average connectivity of a digraph. Discrete Appl. Math. 140 no. 1-3 (2004), 143-153.
  * [4] Z. Huang, H. Lin, Sizes and transmissions of digraphs with a given clique number. J. Combin. Optim. 31 no. 4 (2016), 1642-1649.
  * [5] M. Knor, R. S̆krekovski, A. Tepeh, Some remarks on Wiener index of oriented graphs. Appl. Math. Comput. 273 (2016), 631-636.
  * [6] M. Knor, R. S̆krekovski, A. Tepeh, Digraphs with large maximum Wiener index. Appl. Math. Comput. 284 (2016), 260-267.
  * [7] M. Knor, R. S̆krekovski, A. Tepeh, Orientations of graphs with maximum Wiener index. Discrete Appl. Math. 211 (2016), 121-129.
  * [8] J. Plesník, On the sum of all distances in a graph or digraph. J. Graph Theory 8 (1984), 1-24.
  * [9] J. Spinrad, Transitive orientation in $O(n^{2})$ time. In: Proceedings of the fifteenth annual ACM symposium on Theory of Computing (1983), 457-466.
  * [10] H. Wiener, Structural determination of paraffin boiling points. J. Amer. Chem. Soc. 69 (1947), 17-20.