# Proximity and Remoteness in Graphs: a survey

Mustapha Aouchichea and Bilal Ahmad Ratherb,111Corresponding author
aPolytechnique Montreal, Montreal, QC, Canada
<EMAIL_ADDRESS>
bDepartment of Mathematical Sciences, College of Science,
United Arab Emirate University, Al Ain 15551, Abu Dhabi, UAE
<EMAIL_ADDRESS>
###### Abstract

The proximity $\displaystyle\pi=\pi(G)$ of a connected graph $\displaystyle G$
is the minimum, over all vertices, of the average distance from a vertex to
all others. Similarly, the maximum is called the remoteness and denoted by
$\displaystyle\rho=\rho(G)$. The concepts of proximity and remoteness, first
defined in 2006, attracted the attention of several researchers in Graph
Theory. Their investigation led to a considerable number of publications. In
this paper, we present a survey of the research work.

Keywords: Distance; Transmission; Proximity; Remoteness; Extremal graphs

AMS subject classification: 05C12, 05C35, 15A18.

##  1 Introduction

Models involving paths, distances and location on graphs are much studied in
operations research and mathematics. Models from operations research (see e.g.
[11, 25]) usually use weighted graphs to describe some well-defined class of
problems or some specific applications. Models from mathematics most often
consider unweighted graphs and relations between graph invariants, i.e.,
numerical quantities whose values do not depend on the labelling of edges or
vertices. In this paper, we present a survey of two graph invariants:
proximity and remoteness, defined as the minimum and maximum of the average
distance from a vertex to all others.

Let $\displaystyle G=(V,E)$ denote a simple and connected graph, with vertex
set $\displaystyle V$ and edge set $\displaystyle E$, containing
$\displaystyle n=|V|$ vertices and $\displaystyle m=|E|$ edges. All the graphs
considered in the present paper are finite, simple and connected.

For a vertex $\displaystyle u\in V$, the set of its neighbors in
$\displaystyle G$ is denoted as

$\displaystyle N_{u}=\\{v\in V:uv\in E\\}.$

The degree of $\displaystyle u$ is the number of its neighbors, i.e.,
$\displaystyle d(u)=d_{u}=|N_{u}|$. The maximum degree $\displaystyle\Delta$
and the minimum degree $\displaystyle\delta$ of $\displaystyle G$ are defined
as

$\displaystyle\Delta=\max_{u\in V}d(u)\qquad\mbox{ and
}\qquad\delta=\min_{u\in V}d(u).$

A graph $\displaystyle G$ is said to be $\displaystyle d$-regular, or regular
of degree $\displaystyle d$, if all of its vertices have degree $\displaystyle
d$.

The distance between two vertices $\displaystyle u$ and $\displaystyle v$ in
$\displaystyle G$, denoted by $\displaystyle d(u,v)$, is the length of a
shortest path between $\displaystyle u$ and $\displaystyle v$. The average
distance between all pairs of vertices in $\displaystyle G$ is denoted by
$\displaystyle\overline{l}$. The eccentricity $\displaystyle e(v)$ of a vertex
$\displaystyle v$ in $\displaystyle G$ is the largest distance from
$\displaystyle v$ to another vertex of $\displaystyle G$. The minimum
eccentricity in $\displaystyle G$, denoted by $\displaystyle r$, is the radius
of $\displaystyle G$. The maximum eccentricity of $\displaystyle G$, denoted
by $\displaystyle D$, is the diameter of $\displaystyle G$. The average
eccentricity of $\displaystyle G$ is denoted $\displaystyle ecc$. That is

$\displaystyle r=\min_{v\in V}e(v),\qquad D=\max_{v\in V}e(v) \qquad\mbox{ and
}\qquad ecc=\frac{1}{n}\sum_{v\in V}e(v).$

The Wiener index $\displaystyle W=W(G)$, introduced in [55], of a connected
graph $\displaystyle G$ is defined to be the sum of all distances in
$\displaystyle G$, i.e.,

$\displaystyle W(G)=\frac{1}{2}\sum_{u,v\in V}d(u,v).$

The transmission $\displaystyle t(v)$ of a vertex $\displaystyle v$ is defined
to be the sum of the distances from $\displaystyle v$ to all other vertices in
$\displaystyle G$, i.e.,

$\displaystyle t(v)=\sum_{u\in V}d(u,v).$

A connected graph $\displaystyle G=(V,E)$ is said to be $\displaystyle
k$–transmission regular if $\displaystyle t(v)=k$ for every vertex
$\displaystyle v\in V$. The transmission regular graphs are exactly the
distance–balanced graphs introduced in [28]. They are also called self–median
graphs in [14]. It is clear that any vertex–transitive graph (a graph
$\displaystyle G$ in which for every two vertices $\displaystyle u$ and
$\displaystyle v$, there exist an automorphism $\displaystyle f$ on
$\displaystyle G$ such that $\displaystyle f(u)=f(v)$) is a transmission
regular graph. The converse is not true in general. Indeed, the graph on
$\displaystyle 9$ vertices illustrated in Figure 1 is $\displaystyle
14$–transmission regular graph but not degree regular and therefore not
vertex–transitive. Actually, the graph in Figure 1 is the smallest
transmission regular but not degree regular (see e.g. [3, 32]). For more
examples of transmission regular but not degree regular graphs see [3, 6, 32,
34, 54].

Figure 1: The transmission regular but not degree regular graph with the
smallest order

The proximity  $\displaystyle\pi=\pi(G)$ of $\displaystyle G$ is the minimum
average distance from a vertex of $\displaystyle G$ to all others. Similarly,
the remoteness $\displaystyle\rho=\rho(G)$ of $\displaystyle G$ is the maximum
average distance from a vertex to all others. The two last concepts were
recently introduced in [1, 2]. They are close to the concept of transmission
$\displaystyle t(v)$ of a vertex $\displaystyle v$. That is, if we denote
$\displaystyle\tilde{t}(v)$ the average distance from a vertex $\displaystyle
v$ to all other vertices in $\displaystyle G$, we have

$\displaystyle\pi=\min_{v\in V}\tilde{t}(v)=\min_{v\in V}\frac{t(v)}{n-1}
\qquad\mbox{ and }\qquad\rho=\max_{v\in V}\tilde{t}(v)=\max_{v\in
V}\frac{t(v)}{n-1}.$

The transmission of a vertex is also known as the distance of a vertex [24]
and the minimum distance (transmission) of a vertex is studied in [46]. A
notion very close to the average distance from a vertex is the vertex
deviation introduced by Zelinka [57] as

$\displaystyle m_{1}(v)=\frac{1}{n}\sum_{u\in V}d(u,v)=\frac{t(v)}{n}.$

The vector composed of the vertex transmissions in a graph was first
introduced by Harary [29] in 1959, under the name the status of a graph, as a
measure of the ”weights” of individuals in social networks. The same vector
was called the distance degree sequence by Bloom, Kennedy and Quintas [12]. It
was used to tackle the problem of graph isomorphism. Randić [47] conjectured
that two graphs are isomorphic if and only if they have the same distance
degree sequence. The conjecture was refuted by several authors such as Slater
[51], Buckley and Harary [13], and Entringer, Jackson and Snyder [24]. The
transmission of a graph was also introduced by Sabidussi [48] in 1966 as a
measure of centrality in social networks. The notion of centrality is widely
used in different branches of sciences (see for example [36] and the
references therein) such as transportation–network theory, communication
network theory, electrical circuits theory, psychology, sociology, geography,
game theory and computer science. Notions closely related to that of the
distance from a vertex are those of a center and a centroid introduced by
Jordan [35] in 1869. For mathematical properties of these two concepts see the
survey, as well as the references therein, [52]. In 1964, Hakimi [27] used for
the first time the sum of distances in solving facility location problems. In
fact, Hakimi [27] considered two problems, subsequently considered in many
works: the first problem was to determine a vertex $\displaystyle u\in V$ so
as to minimize $\displaystyle max_{v\in V}\\{d(u,v):u\in V\\}$, i.e., the
center of a graph; and the second problem is to determine a vertex
$\displaystyle u\in V$ so as to minimize the sum of distances from
$\displaystyle u$, i.e., the centroid. Interpretations of these problems can
be found, for instance, in [26]. In view of the interest of the transmission
vector in different domains of sciences, it is natural to study the properties
of its extremal values themselves, and among the set of graph parameters. The
study of proximity and remoteness, since closely related to respectively the
minimum and maximum values of the transmissions, appears to be convenient,
specially, with other metric invariants, such as the diameter, radius, average
eccentricity and average distance. Indeed, it follows from the definitions
that

$\displaystyle\pi\leq r\leq ecc\leq D,\qquad\pi\leq\overline{l}\leq\rho\leq
D\qquad\mbox{ and }\qquad\overline{l}=\frac{1}{n(n-1)}\sum_{v\in V}t(v).$

In addition to these inequalities, several related ones can be found in the
graph theory literature. Recall that a subset $\displaystyle S$ of vertices of
$\displaystyle G$ is said to be independent if its vertices are pairwise
nonadjacent. The maximum cardinality of such a subset is called the
independence number of $\displaystyle G$ and is denoted by
$\displaystyle\alpha=\alpha(G)$. Then $\displaystyle\overline{l}\leq\alpha$
[15] and $\displaystyle r\leq\alpha$ [23]. Recall, also, that a matching in a
graph is a set of disjoint edges. The maximum possible cardinality of a
matching in a graph $\displaystyle G$ is called the matching number of
$\displaystyle G$ and denoted by $\displaystyle\mu=\mu(G)$. The inequality
$\displaystyle r\leq\mu$ can be found in [23]. It was proved in [4] that
$\displaystyle\rho\leq ecc$. All these inequalities are illustrated in Figure
2, where vertices correspond to invariants $\displaystyle a,b,\ldots$, and
directed arcs to the relations $\displaystyle a\leq b$. Observe that all
relations mentioned are tight as all of them but $\displaystyle r\leq\mu$
become equalities for the complete graph $\displaystyle K_{n}$ (all invariants
but $\displaystyle\mu$ being equal to 1) and $\displaystyle r=\mu=1$ for the
star $\displaystyle S_{n}$.

Figure 2: Relations between the invariants.

Since their introduction in [1, 2], the proximity and the remoteness attracted
the attention of several authors.

##  2 Proximity and Remoteness

As for any graph invariant, the first questions asked about the proximity and
the remoteness are: “what are their minimum and maximum values for given order
$\displaystyle n$?” and “which extremal graphs are associated with these
extremal values for a given order $\displaystyle n$?” Both questions are
answered in the following proposition proved in [4].

######  Proposition 2.1 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with proximity $\displaystyle\pi$ and remoteness $\displaystyle\rho$. Then

$\displaystyle 1\leq\pi\leq\left\\{\begin{array}[]{ccl}\frac{n+1}{4}&&\mbox{
if $\displaystyle n$ is odd}\\\ \\\ \frac{n+1}{4}+\frac{1}{4(n-1)}&&\mbox{ if
$\displaystyle n$ is even}\end{array}\right.$

and

$\displaystyle 1\leq\rho\leq\frac{n}{2}.$

The lower bound on $\displaystyle\pi$ is reached if and only if $\displaystyle
G$ contains a dominating vertex; the upper bound on $\displaystyle\pi$ is
attained if and only if $\displaystyle G$ is either the cycle $\displaystyle
C_{n}$ or the path $\displaystyle P_{n}$; the lower bound on
$\displaystyle\rho$ is reached if and only if $\displaystyle G$ is the
complete graph $\displaystyle K_{n}$; the upper bound on $\displaystyle\rho$
is attained if and only if $\displaystyle G$ is the path $\displaystyle
P_{n}$.

Since the proximity $\displaystyle\pi$ and the remoteness $\displaystyle\rho$
are respectively the minimum and the maximum of the same function on a graph,
it is natural to ask about how large can the difference
$\displaystyle\rho-\pi$ be, or in other words, how large can the spread of the
average distances from vertices be. This problem was solved in [4].

######  Proposition 2.2 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and proximity $\displaystyle\pi$. Then

$\displaystyle\rho-\pi\leq\left\\{\begin{array}[]{lll}\frac{n-1}{4}&&\mbox{if
$\displaystyle n$ is odd, }\\\ \frac{n-1}{4}-\frac{1}{4n-4}&&\mbox{if
$\displaystyle n$ is even. }\end{array}\right.$

Equality holds if and only if $\displaystyle G$ is a graph obtained from a
path $\displaystyle P_{\left\lceil\frac{n}{2}\right\rceil}$ and any connected
graph $\displaystyle H$ on $\displaystyle\left\lfloor n/2\right\rfloor+1$
vertices by a coalescence of an endpoint of the path with any vertex of
$\displaystyle H$.

The problem of find bounds on $\displaystyle\pi$ and $\displaystyle\rho$ for a
graph $\displaystyle G$ with given order $\displaystyle n$ and diameter
$\displaystyle D$ was considered in [4]. Actually, the best possible lower
bound on $\displaystyle\pi(G)$ and the best possible upper bound on
$\displaystyle\rho(G)$ were established. These involve a particular class of
graphs, next described. A double-tailed comet $\displaystyle DTC_{n,p,q}$ (see
Figure 3 for an example, i.e., $\displaystyle DTC_{15,4,4}$), with
$\displaystyle n\geq p+q+1$, $\displaystyle p\geq 2$ and $\displaystyle q\geq
2$ is the tree obtained from a path $\displaystyle u_{0}u_{1}\cdots
u_{p}u_{p+1}\cdots u_{p+q}$ by attaching $\displaystyle n-p-q-1$ pendant edges
to $\displaystyle u_{p}$. It is said to be balanced if $\displaystyle p=q$. It
is easy to see that the diameter of $\displaystyle DTC_{n,p,q}$ is
$\displaystyle D=p+q$ and its maximum degree is
$\displaystyle\Delta=d(u_{p})=n-p-q+1$. Assuming, without loss of generality,
that $\displaystyle p\geq q$, we have

$\displaystyle\displaystyle\pi(DTC_{n,p,q})$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\frac{p(p+1)}{2(n-1)}+\frac{q(q+1)}{2(n-1)}-\frac{p+q}{n-1}+1$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\frac{p(p-1)}{2(n-1)}+\frac{q(q-1)}{2(n-1)}+1$

and

$\displaystyle\rho(DTC_{n,p,q})=\frac{(p+q)(p+q+1)}{2(n-1)}-\frac{p^{2}+pq}{n-1}+p.$

Figure 3: The double-tailed comet $\displaystyle DTC_{15,4,4}$.

######  Proposition 2.3 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n$ vertices with
diameter $\displaystyle D$. Then

$\displaystyle\pi(G)\geq\frac{p(p-1)}{2(n-1)}+\frac{q(q-1)}{2(n-1)}+1$

where $\displaystyle p=\left\lceil D/2\right\rceil$ and $\displaystyle
q=\left\lfloor D/2\right\rfloor$. The bound is best possible as shown by the
double-tailed comet $\displaystyle DTC_{n,p,q}$.

A comet $\displaystyle CO_{n,\Delta}$ is the tree obtained from a star
$\displaystyle S_{\Delta+1}$ and a path $\displaystyle P_{n-\Delta}$ by
coalescence of an endpoint of $\displaystyle P_{n-\Delta}$ with a pendant
vertex of $\displaystyle S_{\Delta+1}$. Easy computations lead to the
following expressions for the diameter and the remoteness of a comet:

$\displaystyle D(CO_{n,\Delta})=n-\Delta+1$

and

$\displaystyle\rho(CO_{n,\Delta})=\frac{(n-\Delta+1)(n+\Delta-2)}{2(n-1)}.$

A kite $\displaystyle KI_{n,\omega}$ is the connected graph obtained from a
clique $\displaystyle K_{\omega}$ and a path $\displaystyle P_{n-\omega}$ by
adding an edge between an endpoint of the path and a vertex from the clique. A
pseudo-kite $\displaystyle PKI_{n,p}$ is any connected graph which is a
spanning subgraph of the kite $\displaystyle KI_{n,p}$ and that contains the
comet $\displaystyle CO_{n,p}$ as a spanning tree. Note that $\displaystyle
CO_{n,p}$, $\displaystyle KI_{n,p}$ and $\displaystyle PKI_{n,p}$ have the
same proximity and the same remoteness.

The first relationship between the pseudo-kites and the notion of remoteness
is given in the following proposition.

######  Proposition 2.4 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with diameter $\displaystyle D$. Then

$\displaystyle\rho(G)\leq\rho(PKI_{n,n-D+1})$

with equality if and only if $\displaystyle G$ is a pseudo-kite $\displaystyle
PKI_{n,n-D+1}$.

Let $\displaystyle G$ be a graph and $\displaystyle\overline{G}$ its
complement. If $\displaystyle I$ is an invariant of $\displaystyle G$, we
denote by $\displaystyle\overline{I}$ the same invariant but in
$\displaystyle\overline{G}$. Nordhaus-Gaddum relations for the graph invariant
$\displaystyle I$ are inequalities of the following form

$\displaystyle L_{1}(n)\leq I+\overline{I}\leq U_{1}(n)\qquad\mbox{ and
}\qquad L_{2}(n)\leq I\cdot\overline{I}\leq U_{2}(n),$

where $\displaystyle L_{1}(n)$ and $\displaystyle L_{2}(n)$ are lower bounding
functions of the order $\displaystyle n$, and $\displaystyle U_{1}(n)$ and
$\displaystyle U_{2}(n)$ upper bounding functions of the order $\displaystyle
n$. Note that sometimes, in addition to the order $\displaystyle n$, other
graph invariants are used in the bounds. This type of relations is so called
after Nordhaus and Gaddum [41] who were the first authors to give such
relations, namely

$2\sqrt{n}\leq\chi+\overline{\chi}\leq n+1\qquad\mbox{ and }\qquad
n\leq\chi\cdot\overline{\chi}\leq\left(\frac{n+1}{2}\right)^{2},$ (1)

where $\displaystyle\chi$ is the chromatic number of a graph. Since then many
graph theorists have been interested in finding such relations for various
graph invariants. See [7] for a survey of Nordhaus–Gaddum type results. For
proximity and remoteness, Nordhaus–Gaddum inequalities were proved in [5].

######  Theorem 2.5 ([5]).

For any connected graph $\displaystyle G$ on $\displaystyle n\geq 5$ vertices
for which $\displaystyle\overline{G}$ is connected

$\displaystyle\frac{2n}{n-1}\leq\pi+\overline{\pi}\leq\left\\{\begin{array}[]{ccl}\frac{n+1}{4}+\frac{n+1}{n-1}&&\mbox{
if $\displaystyle n$ is odd, }\\\
\frac{n}{4}+\frac{n}{4(n-1)}+\frac{n+1}{n-1}&&\mbox{ if $\displaystyle n$ is
even. }\end{array}\right.$

The lower bound is attained if and only if
$\displaystyle\Delta(G)=\Delta(\overline{G})=n-2$. The upper bound is attained
if and only if either $\displaystyle G$ or $\displaystyle\overline{G}$ is the
cycle $\displaystyle C_{n}$.

######  Theorem 2.6 ([5]).

For any connected graph $\displaystyle G$ on $\displaystyle n\geq 5$ vertices
for which $\displaystyle\overline{G}$ is connected

$\displaystyle\frac{n^{2}}{(n-1)^{2}}\leq\pi\cdot\overline{\pi}\leq\left\\{\begin{array}[]{ccl}\frac{(n+1)^{2}}{4(n-1)}&&\mbox{
if $\displaystyle n$ is odd, }\\\
\frac{n(n+1)}{4(n-1)}+\frac{n(n+1)}{4(n-1)^{2}}&&\mbox{ if $\displaystyle n$
is even. }\end{array}\right.$

The lower bound is attained if and only if
$\displaystyle\Delta(G)=\Delta(\overline{G})=n-2$. The upper bound is attained
if and only if either $\displaystyle G$ or $\displaystyle\overline{G}$ is the
cycle $\displaystyle C_{n}$.

Recall that a comet $\displaystyle Co_{n,\Delta}$ is obtained from a star
$\displaystyle S_{\Delta+1}$ by appending a path $\displaystyle
P_{n-\Delta-1}$ to one of its pending vertices. Moreover, a path-complete
graph $\displaystyle PK_{n,m}$ on $\displaystyle n$ vertices and
$\displaystyle m$ edges is the graph obtained from a path $\displaystyle
P_{k}$, $\displaystyle k\geq 1$, and a clique $\displaystyle K_{n-k}$ by
adding at least one edge between one endpoint of the path and the vertices of
$\displaystyle K_{n-k}$, where $\displaystyle(n-k)(n-k-1)/2+k\leq
m\leq(n-k+1)(n-k)/2+k-1$. One can verify that there is exactly one path-
complete graph $\displaystyle PK_{n,m}$ for all $\displaystyle n$ and
$\displaystyle m$ such that $\displaystyle 1\leq n-1\leq m\leq n(n-1)/2$.

######  Theorem 2.7 ([5]).

For any connected graph $\displaystyle G$ on $\displaystyle n\geq 6$ vertices
for which $\displaystyle\overline{G}$ is connected

$\displaystyle 3\leq\rho+\overline{\rho}\leq\frac{n+2}{2}+\frac{2}{n-1}.$

The lower bound is attained if and only if $\displaystyle n\geq 8$,
$\displaystyle G$ is regular and $\displaystyle D=\overline{D}=2$. The upper
bound is attained if and only if $\displaystyle G$ or
$\displaystyle\overline{G}$ is the path $\displaystyle P_{n}$, the comet
$\displaystyle Co_{n,3}$ or the path-complete graph $\displaystyle PK_{n,n}$
when $\displaystyle n\geq 7$, and if and only if $\displaystyle G$ or
$\displaystyle\overline{G}$ is the path $\displaystyle P_{6}$, the comet
$\displaystyle Co_{6,3}$, the path-complete graph $\displaystyle PK_{6,6}$ or
one of the graphs in Fig. 4.

Figure 4: Graphs with $\displaystyle D=3$ that maximize
$\displaystyle\rho+\overline{\rho}$ for $\displaystyle n=6$.

######  Theorem 2.8 ([5]).

For any connected graph $\displaystyle G$ on $\displaystyle n\geq 7$ vertices
for which $\displaystyle\overline{G}$ is connected

$\displaystyle\rho\cdot\overline{\rho}\leq\left\\{\begin{array}[]{lll}\frac{16n+20}{27}+\frac{8}{9(n-1)}+\frac{4}{27(n-1)^{2}}&
\mbox{ if }&n=\,\,0\,\,(mod\,\,3),\\\ \frac{16n+20}{27}+\frac{2}{3(n-1)}&
\mbox{ if }&n=\,\,1\,\,(mod\,\,3),\\\
\frac{16n+20}{27}+\frac{8}{9(n-1)}+\frac{5}{27(n-1)^{2}}& \mbox{ if
}&n=\,\,2\,\,(mod\,\,3).\\\ \end{array}\right.$

The upper bound is the best possible as shown by the comets $\displaystyle
Co_{n,\left\lceil\frac{n}{3}\right\rceil+1}$, and $\displaystyle
Co_{n,\left\lceil\frac{n}{3}\right\rceil}$ if $\displaystyle
n=\,\,1\,\,(mod\,\,3)$.

Note that the bound provided in Theorem 2.8 is not valid for $\displaystyle
n=4,5,6$ (if $\displaystyle n\leq 3$, then $\displaystyle G$ and
$\displaystyle\overline{G}$ cannot be connected simultaneously). For the path
$\displaystyle P_{4}$ (resp. the comets $\displaystyle Co_{5,3}$ and
$\displaystyle Co_{6,4}$), $\displaystyle\rho\cdot\overline{\rho}=4$ (resp.
9/2 and 24/5) while the corresponding value provided by Theorem 2.8 is
$\displaystyle 10/3$ (resp. 63/16 and 112/25).

Czabarka et al. [16] obtained results on proximatity in triangulations and
quadrangulations, that is graphs with maximal planer graphs and graphs with
maximal bipartite planer graphs, respectiely.

######  Theorem 2.9 ([16]).

Let $\displaystyle G$ be a planar graph of order $\displaystyle n$ and
$\displaystyle v$ a central vertex of $\displaystyle G$.

  * (i)

If $\displaystyle G$ is a triangulation, then

$\displaystyle\pi\leq\frac{n+19}{12}+\frac{25}{3(n-1)}.$

  * (ii)

If $\displaystyle G$ is a $\displaystyle 4$-connected triangulation, then

$\displaystyle\pi\leq\frac{n+35}{16}+\frac{91}{4(n-1)}.$

  * (iii)

If $\displaystyle G$ is a $\displaystyle 5$-connected triangulation, then

$\displaystyle\pi\leq\frac{n+57}{20}+\frac{393}{10(n-1)}.$

  * (iv)

If $\displaystyle G$ is a quadrangulation, then

$\displaystyle\pi\leq\frac{n+11}{8}+\frac{9}{2(n-1)}.$

  * (v)

If $\displaystyle G$ is a $\displaystyle 3$-connected quadrangulation, then

$\displaystyle\pi\leq\frac{n+25}{12}+\frac{169}{12(n-1)}.$

Pei et al. [45] gave following intresting results relating proximity, average
eccentricity and domination, results earlier conjuctured in [1]. The
domination number $\displaystyle\gamma(G)$ is the minimum cardinality of a
dominating set of G.

Recall that $\displaystyle\gamma(G)\leq\left\lfloor\frac{n}{2}\right\rfloor.$
In fact, the graphs with domination number
$\displaystyle\left\lfloor\frac{n}{2}\right\rfloor$ have been determined in
the following result.

Figure 5: Graphs in family $\displaystyle\mathcal{A}$

Figure 6: Graphs in family $\displaystyle\mathcal{B}$

######  Lemma 2.10 ([42]).

A connected graph $\displaystyle G$ of order $\displaystyle n$ satisfies
$\displaystyle\gamma(G)=\left\lfloor\frac{n}{2}\right\rfloor$ if and only if
$\displaystyle G\in\bigcup_{i=1}^{6}\mathcal{G}_{i}$, where
$\displaystyle\mathcal{G}_{i},~{}i=1,\dots,6,$ is the set defined in the
following. Let $\displaystyle H$ be any graph with vertex set
$\displaystyle\\{v_{1},\dots,v_{k}\\}$. Denote by $\displaystyle f(H)$ the
graph obtained from $\displaystyle H$ by adding new vertices $\displaystyle
u_{1},\dots,u_{k}$ and the edges $\displaystyle v_{i}u_{i},~{}i=1,\dots,k.$
Define

$\displaystyle\mathcal{G}_{1}=\\{C_{4}\\}\cup\\{G|G=f(H)~{}\text{for some
connected graph}~{}H\\}.$

Let $\displaystyle\mathcal{F}=\mathcal{A}\cup\mathcal{B}$ and
$\displaystyle\mathcal{G}_{2}=\mathcal{F}-\\{C_{4}\\},$ where
$\displaystyle\mathcal{A}=\\{C_{4},G(7,i)|i=1,\dots,6\\}$ and
$\displaystyle\mathcal{B}=\\{K3,G(5,i)|i=1,\dots,4\\},$ as shown in Fig. 5 and
Fig. 6, respectively. For any graph $\displaystyle H$, let
$\displaystyle\phi(H)$ be the set of connected graphs, each of which can be
formed from $\displaystyle f(H)$ by adding a new vertex $\displaystyle x$ and
edges joining $\displaystyle x$ to one or more vertices of $\displaystyle H$.
Then define $\displaystyle\mathcal{G}_{3}=\\{G|G=\phi(H)~{}\text{for some
graph}~{}H\\}.$ Let $\displaystyle G\in\mathcal{G}_{3}$ and $\displaystyle y$
be a vertex of a copy of $\displaystyle C_{4}$. Denote by
$\displaystyle\theta(G)$ the graph obtained by joining $\displaystyle G$ to
$\displaystyle C_{4}$ with the single edge $\displaystyle xy,$ where
$\displaystyle x$ is the new vertex added in forming G. Then define

$\displaystyle\mathcal{G}_{4}=\\{G|G=\theta(H)~{}\text{for some graph
H}~{}\in\mathcal{G}_{3}\\}.$

Let $\displaystyle u,v,w$ be the vertex sequence of a path $\displaystyle
P_{3}.$ For any graph $\displaystyle H,$ let $\displaystyle\mathcal{P}(H)$ be
the set of connected graphs which may be formed from $\displaystyle f(H)$ by
joining each of $\displaystyle u$ and $\displaystyle w$ to one or more
vertices of M Then define

$\displaystyle\mathcal{G}_{5}=\\{G|G=\mathcal{P}(H)~{}\text{for some
graph}~{}H\\}.$

For a graph $\displaystyle X\in\mathcal{B}$, let $\displaystyle U\subset V(X)$
be a set of vertices such that no fewer than $\displaystyle\gamma(X)$ vertices
of $\displaystyle X$ dominate $\displaystyle V(X)\setminus U.$ Let
$\displaystyle\mathcal{R}(H,X)$ be the set of connected graphs which may be
formed from $\displaystyle f(H)$ by joining each vertex of $\displaystyle U$
to one or more vertices of $\displaystyle H$ for some set $\displaystyle U$ as
defined above and any graph $\displaystyle H.$ Then define

$\displaystyle\mathcal{G}_{6}=\\{G|G\in\mathcal{R}(H,X)~{}\text{for
some}~{}X\in\mathcal{B}~{}\text{and some}~{}H\\}.$

######  Lemma 2.11 ([45]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ with
$\displaystyle\gamma(G)\geq 2,\Delta(G)\leq n-2$ and
$\displaystyle\delta(G)=1.$ Then

$\displaystyle ecc\geq 2+\frac{\gamma(G)}{n}.$

######  Lemma 2.12 ([45]).

Let $\displaystyle G$ be a connected graph with $\displaystyle\Delta(G)\leq
n-2$ and $\displaystyle\delta(G)=2.$ Then $\displaystyle\gamma(G)=2$ or
$\displaystyle ecc\geq 2+\frac{2}{n}.$

######  Lemma 2.13 ([45]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 2$.
If $\displaystyle\Delta(G)=n-1,$ then $\displaystyle\frac{\gamma(G)}{ecc}\leq
1$ with equality if and only if $\displaystyle G\cong K_{n}.$

######  Lemma 2.14 ([45]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n$ vertices,
where $\displaystyle 2\leq n\leq 5.$ Then

$\displaystyle\frac{\gamma(G)}{ecc}\leq 1,$

with equality if and only if $\displaystyle G\in\\{P_{2},C_{3},K_{4},C_{4}\\}$
when $\displaystyle n\leq 4$, and $\displaystyle
G\in{K_{5},G(5,1),G(5,2),G(5,3),G(5,4)}\subseteq\mathcal{B}$ when
$\displaystyle n=5,$ see Fig. 6

######  Theorem 2.15 ([45]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 2.$
Then

$\displaystyle\frac{\gamma(G)}{ecc}\begin{cases}1&\text{if}~{}n\leq 5,\\\
\frac{n.\left\lfloor\frac{n}{2}\right\rfloor}{\left\lfloor\frac{5n}{2}\right\rfloor}&\text{if}~{}n\geq
6,\end{cases}$

with equality if and only if $\displaystyle
G\in\\{P_{2},C_{3},K_{4},C_{4},K_{5},G(5,1),G(5,2),G(5,3),G(5,4)\\}$ when
$\displaystyle n\leq 5$, or $\displaystyle
G\in\\{K_{\left\lceil\frac{n}{2}\right\rceil,\left\lfloor\frac{n}{2}\right\rfloor},G(7,1),G(7,2),G^{\prime},G^{\prime\prime}\\}$
when $\displaystyle n\geq 6,$ where $\displaystyle
G^{\prime},G^{\prime\prime}$ are defined in [44].

The first observation in [45] is that for a vertex $\displaystyle v$ in a
conected graph $\displaystyle G$, the proximity is

$\displaystyle\pi(v)\geq\frac{2n-2-d(v)}{n-1},$

with equality if and only if $\displaystyle e(v)\leq 2.$

we define a subset of $\displaystyle\mathcal{G}$. Namely,
$\displaystyle\mathcal{G}^{\ast}=\cup_{i\in\\{1,2,3,5,6\\}}\mathcal{G}_{i}^{\ast},$
where $\displaystyle\mathcal{G}_{i}^{\ast}$ is shown as follows,
$\displaystyle i=1,2,3,5,6.$ We continue with the meaning of the notations
$\displaystyle x,u,v,w$ in the definition of $\displaystyle\mathcal{G}_{3}$
and $\displaystyle\mathcal{G}_{5}$, where $\displaystyle x$ is the vertex
added in forming graph $\displaystyle G\in\mathcal{G}_{3},u,v,w$ is the vertex
sequence of a path $\displaystyle P_{3}$ mentioned in the constructionof
$\displaystyle G_{5}.$ Let $\displaystyle H^{\ast}$ be any connected graph
with vertex set $\displaystyle\\{v_{1},\dots,v_{k}\\}$ and
$\displaystyle\triangle(H^{\ast})=k-1.$ Assume that $\displaystyle
d_{H^{\ast}}(v_{i_{0}})=\triangle(H^{\ast})$ for some $\displaystyle
i_{0}\in\\{1,\dots,k\\},$ that is
$\displaystyle{v_{i_{0}}v_{j}|j=1,\dots,i_{0}-1,i_{0}+1,\dot{,}k}\subseteq
E(H^{\ast}).$ Let

$\displaystyle\displaystyle\mathcal{G}_{1}^{\ast}$
$\displaystyle\displaystyle=\\{G|G=f(H^{\ast})~{}\text{for some connected
graph}H^{\ast}\\},$ $\displaystyle\displaystyle\mathcal{G}_{2}^{\ast}$
$\displaystyle\displaystyle=\\{G(5,2),G(5,3),G(5,4),G(7,2),G(7,5),G(7,6)\\},$
$\displaystyle\displaystyle\mathcal{G}_{3}^{\ast}$
$\displaystyle\displaystyle=\\{G|G=\phi(H^{\ast})~{}\text{and}~{}v_{i_{0}}x\in
E(G)\\},$ $\displaystyle\displaystyle\mathcal{G}_{5}^{\ast}$
$\displaystyle\displaystyle=\\{G|G=\mathcal{P}(H^{\ast}),v_{i_{0}}u\in
E(G)~{}\text{and}~{}v_{i_{0}}w\in E(G)\\}$ and
$\displaystyle\displaystyle\mathcal{G}_{6}^{\ast}$
$\displaystyle\displaystyle=\mathcal{G}_{6}^{1}\cup\mathcal{G}_{6}^{1}\cup\mathcal{G}_{6}^{(3,2)}\cup\mathcal{G}_{6}^{(3,3)}\cup\mathcal{G}_{6}^{(3,4)},$
where $\displaystyle\displaystyle\mathcal{G}_{6}^{1}$
$\displaystyle\displaystyle=\\{G|G=\mathcal{R}(K3,H^{\ast})~{}\text{with}~{}|U|=2,~{}\text{and}~{}v_{i_{0}}s\in
E(G)~{}\text{for each vertex}~{}s\in U\\}.$
$\displaystyle\displaystyle\mathcal{G}_{6}^{2}$
$\displaystyle\displaystyle=\\{G|G\in\mathcal{G}_{6}~{}\text{with}~{}X=K_{3},~{}\text{and}~{}sv_{i}\in
E(G)~{}\text{for some vertex}~{}s\in U~{}\text{and}~{}i=1,\dots,k\\}.$

For $\displaystyle i=2,3,4,$
$\displaystyle\mathcal{G}_{6}^{(3,i)}=\\{G|G\in\mathcal{G}_{6}~{}\text{with}~{}X=G(5,i),~{}\text{and}~{}sv_{j}\in
E(G)~{}\text{for}~{}j=1,\dots,k,~{}\text{some vertex}s\in
U~{}\text{with}~{}d_{G}(5,i)(s)=3\\}.$

######  Lemma 2.16 ([45]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 5$
with $\displaystyle\gamma(G)=\left\lfloor\frac{n}{2}\right\rfloor$. Then

$\displaystyle\pi\geq\begin{cases}\frac{3}{2}-\frac{1}{2(n-1)},&n~{}\text{is
even}\\\ \frac{3}{2}-\frac{1}{n-1},&n~{}\text{is odd}\end{cases}$

with equality if and only if $\displaystyle G\in\mathcal{G}^{\ast}.$

######  Theorem 2.17 ([45]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 2$.
Then

$\displaystyle\gamma(G)-\pi\leq\begin{cases}\frac{n-3}{2}+\frac{1}{2(n-1)},&\text{if
$\displaystyle n$ is even}\\\ \frac{n-4}{2}-\frac{1}{n-1},&\text{if
$\displaystyle n$ is odd}\end{cases}$

with equality if and only if $\displaystyle
G\in\mathcal{G}^{\ast}\cup\\{P_{2},P_{3},C_{3},P_{4},C_{4}\\}.$

Recently Pie [43] obtained the following results for the domination number and
the remoteness of a graph.

######  Lemma 2.18 ([43]).

Let $\displaystyle G$ be a connected graph with $\displaystyle n\leq 6$
vertices with $\displaystyle\gamma(G)=\left\lfloor\frac{n}{2}\right\rfloor-1.$
Then

$\displaystyle\gamma(G)-\rho(G)<\begin{cases}\frac{n-5}{2}+\frac{3}{2n-2},&n~{}\text{is
even}\\\ \frac{n-6}{2}+\frac{2}{n-1},&n~{}\text{is odd and}~{}n\geq 9\\\
\frac{n-3}{4},&n=7.\end{cases}$

######  Lemma 2.19 ([43]).

Suppose that $\displaystyle G$ be a connected graph of order $\displaystyle n$
with $\displaystyle 1\leq\gamma(G)=\left\lfloor\frac{n}{2}\right\rfloor-2.$
Then

$\displaystyle\gamma(G)-\rho(G)<\begin{cases}\frac{n-5}{2}+\frac{3}{2n-2},&n~{}\text{is
even}\\\ \frac{n-6}{2}+\frac{2}{n-1},&n~{}\text{is odd and}~{}n\geq 9\\\
\frac{n-3}{4},&n~{}\text{is odd and}~{}n\leq 7.\end{cases}$

######  Lemma 2.20 ([43]).

If $\displaystyle G$ is a connected graph with order $\displaystyle n(\geq 2)$
and $\displaystyle\gamma(G)=\left\lfloor\frac{n}{2}\right\rfloor,$ then

$\displaystyle\gamma(G)-\rho(G)\leq\begin{cases}\frac{2}{3},&n=4\\\
\frac{n-5}{2}+\frac{3}{2n-2},&n~{}\text{is even and}~{}n\neq 4\\\
\frac{n-3}{4},&n~{}\text{is odd and}~{}n\leq 7\\\
\frac{n-6}{2}+\frac{2}{n-1},&n~{}\text{is odd and}~{}n\geq 9,\\\ \end{cases}$

with equality if and only if $\displaystyle
G\in\\{C_{4},K_{\frac{n}{2},\frac{n}{2}}~{}|~{}n~{}\text{is even and}~{}n\neq
4\\}\cup(\mathcal{G}_{2}-\\{G^{5}_{7})\\})\cup\\{K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor},G^{\prime},G^{\prime\prime}$
$\displaystyle|~{}n~{}\text{is odd and}~{}n\geq 9\\},$ where $\displaystyle
G^{\prime},G^{\prime\prime}$ are defined in [44].

######  Lemma 2.21 ([43]).

If $\displaystyle G$ is a connected graph with $\displaystyle n\leq 7$
vertices and $\displaystyle\gamma(G)=\left\lfloor\frac{n}{2}\right\rfloor-1,$
then $\displaystyle n\geq 4$ and

$\displaystyle\gamma(G)-\rho(G)\leq\begin{cases}\frac{4}{5},&n=6\\\ 0&4\leq
n\leq 5\end{cases}$

with equality if and only if G is $\displaystyle 4$-regular when
$\displaystyle n=6$, and $\displaystyle G\cong K_{n}$ when $\displaystyle
4\leq n\leq 5.$

Dankelmann, Jonck and Mafunda [20], obtained boubds for $\displaystyle\pi$ and
$\displaystyle\rho$ in triangle-free and $\displaystyle C_{4}$-free graphs in
terms of order and minimum degree.

Given positive integers $\displaystyle n,\delta$ with $\displaystyle\delta\geq
3.$ Let $\displaystyle A=(1,1,\delta-1,\delta-1,1,1,\delta-1,\delta-1,\dots)$
be the infinite sequence repeating the
$\displaystyle(1,1,\delta-1,\delta-1)$-pattern indefinitely. Define the finite
sequence $\displaystyle X_{n,\delta}$ by

$\displaystyle
X_{n,\delta}=(1,\delta,\delta-1,a_{1},a_{2},\dots,a_{l(A,n-4\delta)},\delta,r_{n,\delta}),$

where $\displaystyle r_{n,\delta}=n-3\delta-\sum_{i=1}^{l(A,n-4\delta)}a_{i}.$

The sequential sum of graphs $\displaystyle G=G_{1}+G_{2}+\dots+G_{n}$ to be
the sequential join such that the vertex set $\displaystyle V(G)=V(G_{1})\cup
V(G_{2})\cup\dots\cup V(G_{n})$ and the edge set $\displaystyle
E(G)=E(G_{1})\cup E(G_{2})\cup\dots\cup E(G_{n})\bigcup_{i=1}^{n-1}\\{uv|u\in
V(G_{i}),v\in V(G_{i+1})\\}.$

For a finite sequence $\displaystyle X=(x_{0},x_{1},\dots,x_{d})$ of positive
integers we define the graph $\displaystyle G(X)$ by

$\displaystyle
G(X)=\overline{K}_{x_{0}}+\overline{K}_{x_{1}}+\dots+\overline{K}_{x_{d}}$

######  Theorem 2.22 ([20]).

Let $\displaystyle G$ be a connected, triangle free graph of order
$\displaystyle n$ and minimum degree $\displaystyle\delta$, where
$\displaystyle\delta\geq 3$ and $\displaystyle n\geq 6\delta.$ Then

$\displaystyle\rho\leq\rho(G(X_{n,\delta})).$

######  Corollary 2.23 ([20]).

If $\displaystyle G$ is a connected triangle-free graph of order
$\displaystyle n$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle\rho\leq
2\left\lceil\frac{n-3\delta}{2\delta}\right\rceil+2-\frac{\delta}{n-1},$

and this bound is sharp.

######  Theorem 2.24 ([20]).

If $\displaystyle G$ is a connected, triangle-free graph of order
$\displaystyle n$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle\pi\leq\frac{n}{2\delta}+2-\frac{5}{2\delta}-\frac{21\delta^{2}-8\delta-3}{2\delta(n-1)}.$

######  Theorem 2.25 ([20]).

If $\displaystyle G$ is a connected, $\displaystyle C_{4}$-free graph of order
$\displaystyle n$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle\rho\leq\frac{5}{2}\left\lfloor\frac{n}{\delta^{2}-2\left\lfloor\frac{\delta}{2}\right\rfloor+1}\right\rfloor+2.$

The next theorem shows that for many values of $\displaystyle\delta$ the bound
on remoteness is close to being best possible in the sense that the ratio of
the coefficients of $\displaystyle n$ in the bound and approach $\displaystyle
1$ as $\displaystyle\delta$ gets large.

######  Theorem 2.26 ([20]).

Let $\displaystyle\delta\geq 3$ be an integer such that
$\displaystyle\delta=q-1$ for some prime power $\displaystyle q$. Then there
exists an infinite number of $\displaystyle C_{4}$-free graphs $\displaystyle
G$ of minimum degree at least $\displaystyle\delta$ with

$\displaystyle\displaystyle\rho$
$\displaystyle\displaystyle=\frac{5}{2}\frac{n}{\delta^{2}+3\delta+2}+O(1),$
$\displaystyle\displaystyle\pi$
$\displaystyle\displaystyle=\frac{5}{4}\frac{n}{\delta^{2}+3\delta+2}+O(1),$

where $\displaystyle n$ is the order of $\displaystyle G.$

######  Theorem 2.27 ([20]).

If $\displaystyle G$ is a connected $\displaystyle C_{4}$-free graph of order
$\displaystyle n$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle\pi\leq\frac{5}{4}\left\lfloor\frac{n}{\delta^{2}-2\left\lfloor\frac{\delta}{2}\right\rfloor+1}\right\rfloor+\frac{147}{32}.$

Dankelmann and Mafunda [21] gave results about difference between
$\displaystyle\pi$ and distance parameters in triangle-free and $\displaystyle
C_{4}$-free graphs.

######  Theorem 2.28 ([21]).

If $\displaystyle G$ is a connected, triangle-free graph of order
$\displaystyle n\geq 7$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle\rho-\pi\leq\frac{n+1}{2\delta}+4.$

######  Theorem 2.29 ([21]).

If $\displaystyle G$ is a connected, $\displaystyle C_{4}$-free graph of order
$\displaystyle n\geq 6$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle\rho-\pi\leq\frac{5(n+1)}{4\left(\delta^{2}-2\left\lfloor\frac{\delta}{2}\right\rfloor+1\right)}+\frac{101}{20}.$

######  Theorem 2.30 ([22]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n,$ minimum
degree $\displaystyle\delta$ and maximum degree $\displaystyle\triangle$.
If $\displaystyle\triangle>\frac{n}{2}-1,$ then

$\displaystyle\pi\leq\frac{3(n-\triangle)^{2}}{2(n-1)(\delta+1)}+\frac{13}{2}.$

If $\displaystyle\triangle\leq\frac{n}{2}-1,$ then

$\displaystyle\pi\leq\frac{3(n^{2}-2\triangle^{2})}{4(n-1)(\delta+1)}+\frac{35}{4}.$

######  Theorem 2.31 ([22]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$, minimum
degree $\displaystyle\delta$ and maximum degree $\displaystyle\triangle$. Then
there exists a spanning tree $\displaystyle T$ of $\displaystyle G$ with

$\displaystyle\rho(T)\leq\frac{3(n^{2}-\triangle^{2})}{2(n-1)(\delta+1)}+7.$

Since $\displaystyle\rho(G)\leq\rho(T)$ for every spanning tree of a conncetd
graph $\displaystyle G,$ the following result follows from Theorem 2.31.

######  Corollary 2.32 ([22]).

If $\displaystyle G$ is a connected graph of order $\displaystyle n$, minimum
degree $\displaystyle\delta$ and maximum degree $\displaystyle\triangle$, then

$\displaystyle\rho\leq\frac{3(n^{2}-\triangle^{2})}{2(n-1)(\delta+1)}+7.$

A thesis about the proximity and the remoteness of graphs written by Mallu in
2022 can be seen [38], jointly supervised by Dankelmann and Mafunda.

##  3 Proximity and Remoteness Compared to Metric Invariants

Aouchiche and Hansen in 2011 compared proximity and remoteness with the metric
invariants of a graph [4].

######  Proposition 3.1 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with diameter $\displaystyle D$ and proximity $\displaystyle\pi$. Then

$\displaystyle D-\pi\leq\left\\{\begin{array}[]{ll}\frac{3n-5}{4}&\quad\mbox{
if $\displaystyle n$ is odd, }\\\ \frac{3n-5}{4}-\frac{1}{4n-4}&\quad\mbox{ if
$\displaystyle n$ is even, }\end{array}\right.$

with equality if and only if $\displaystyle G$ is a path $\displaystyle
P_{n}$.

######  Proposition 3.2 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and diameter $\displaystyle D$. Then

$\displaystyle D-\rho\leq\frac{n-2}{2},$

with equality if and only if $\displaystyle G$ is the path $\displaystyle
P_{n}$.

######  Proposition 3.3 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with radius $\displaystyle r$ and proximity $\displaystyle\pi$. Then

$\displaystyle
r-\pi\leq\left\\{\begin{array}[]{ll}\frac{n-1}{4}-\frac{1}{4(n-1)}&\mbox{if
$\displaystyle n$ is even, }\\\ \frac{n-1}{4}-\frac{1}{n-1}&\mbox{ if
$\displaystyle n$ is odd. }\end{array}\right.$

The bound is best possible as shown by the graph composed of a cycle with an
additional edge forming a triangle or two additional crossed edges on four
successive vertices of the cycle if $\displaystyle n$ is odd, and by the path
$\displaystyle P_{n}$ or the cycle $\displaystyle C_{n}$ if $\displaystyle n$
is even.

######  Proposition 3.4 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and radius $\displaystyle r$. Then

$\displaystyle\rho-r\leq\left\\{\begin{array}[]{lll}\frac{n+1}{8}+\frac{1}{8(n-1)}&&\mbox{
if }n=0\,\,(mod\,\, 4),\\\ \frac{n+1}{8}&&\mbox{ if }n=1\,\,(mod\,\, 4),\\\
\frac{n+1}{8}-\frac{3}{8(n-1)}&&\mbox{ if }n=2\,\,(mod\,\, 4),\\\
\frac{n+1}{8}&&\mbox{ if }n=3\,\,(mod\,\, 4).\\\ \end{array}\right.$

The bound is attained if and only if $\displaystyle G$ is a pseudo-kite
$\displaystyle PKI_{n,n-2r^{*}+1}$ where

$\displaystyle r^{*}=\left\\{\begin{array}[]{lll}\frac{n}{4}&&\mbox{ if
}n=0\,\,(mod\,\, 4),\\\ \frac{n-1}{4}&&\mbox{ if }n =1\,\,(mod\,\, 4),\\\
\frac{n-2}{4}\mbox{ or }\frac{n+2}{4}&&\mbox{ if }n=2\,\,(mod\,\, 4),\\\
\frac{n+1}{4}&&\mbox{ if }n=3\,\,(mod\,\, 4).\\\ \end{array}\right.$

######  Proposition 3.5 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and average eccentricity $\displaystyle
ecc$. Then

$\displaystyle\rho\leq ecc$

with equality in both cases if and only if $\displaystyle G$ is a complete
graph $\displaystyle K_{n}$.

Ma, Wu and Zhang [40] gave the following lemmas and proved a conjecture that
consists of an upper bound on $\displaystyle ecc-\pi$ together with the
corresponding extremal graphs.

A vertex $\displaystyle v\in V$ is called a centroidal vertex if
$\displaystyle\pi(v)=\pi(G)$, and the set of all centroidal vertices is the
centroid (sometimes known as median or barycenter) of $\displaystyle G.$

For an edge $\displaystyle e\in E(G)$ and a vertex $\displaystyle u\in V(G)$,
we denote by $\displaystyle(G-e)_{u}$ the component of $\displaystyle G-e$
containing $\displaystyle u$, and let $\displaystyle V_{u}(e)=V((G-e)_{u})$
and $\displaystyle n_{u}(e)=|V_{u}(e)|$. Clearly, for any edge $\displaystyle
e=uv\in E(G),~{}n_{u}(e)+n_{v}(e)=|V(G)|$. The following lemmas are given in
[40].

######  Lemma 3.6 ([40]).

Let $\displaystyle G$ be a tree of order $\displaystyle n$. For any edge
$\displaystyle e=uv\in E(G),$

$\displaystyle \pi(u)+\frac{1}{n-1}n_{u}(e)=\pi(v)+\frac{1}{n-1}n_{v}(e).$

######  Lemma 3.7 ([40]).

The following holds for a tree $\displaystyle G$ of order $\displaystyle n$

  * (i)

If $\displaystyle x$ is a centroidal vertex of $\displaystyle G$, then

$\displaystyle ecc(x)\leq\left\lfloor\frac{n}{2}\right\rfloor,$

with equality if and only if there exists a path of length
$\displaystyle\left\lfloor\frac{n}{2}\right\rfloor$ in $\displaystyle G$,which
joins $\displaystyle x$ to a pendent vertex of $\displaystyle G$ with the
property that the degree of every internal vertex of it is equal to two in
$\displaystyle G$.

  * (ii)

If there is a path $\displaystyle P$ of length
$\displaystyle\left\lfloor\frac{n}{2}\right\rfloor$ in $\displaystyle G$,
which joins a vertex $\displaystyle y$ and a pendent vertex of $\displaystyle
G$ with the property that the degree of every internal vertex of it is equal
to two in $\displaystyle G$, then $\displaystyle y$ is a centroidal vertex of
$\displaystyle G$.

######  Lemma 3.8 ([40]).

Let G be a tree of order $\displaystyle n\geq 3$. Let $\displaystyle
v_{0}v_{1}\dots v_{d}$ be a longest path in $\displaystyle G$. Set
$\displaystyle V_{0}=\\{v\in V(G)|d(v,v_{0})\geq
d(v,v_{d})\\},~{}V_{d}=\\{v\in V(G)|d(v,v_{d})\geq d(v,v_{0})\\}$. Without
loss of generality, let $\displaystyle|V_{0}|\geq|V_{d}|$. If $\displaystyle
G$ is not a path, then the following holds:

  * (1)

there is a pendent vertex $\displaystyle v^{\ast}\in V_{0}$ distinct from
$\displaystyle v_{d}$,

  * (2)

$\displaystyle ecc(G)-ecc(G^{\prime})\geq\frac{1}{2}$, where $\displaystyle
G^{\prime}$ is the tree obtained from $\displaystyle G$ by deleting the edge
incident with $\displaystyle v^{\ast}$ and joining $\displaystyle v^{\ast}$
and $\displaystyle v_{0}$,

  * (3)

$\displaystyle\pi(G)-\pi(G^{\prime})<\frac{1}{2}$, where $\displaystyle
G^{\prime}$ is the tree as defined in (2).

Lemmas 3.6, 3.7 and 3.8 help in establishing the following result and verifies
a conjecture of [4].

######  Theorem 3.9 ([40]).

For a connected graph $\displaystyle G$ on $\displaystyle n\geq 3$ vertices,

$\displaystyle
ecc-\pi\leq\left\\{\begin{array}[]{lll}\frac{(3n+1)(n-1)}{4n}-\frac{n+1}{4}&&\mbox{
if $\displaystyle n$ is odd,}\\\ \frac{n-1}{2}-\frac{n}{4(n-1)}&&\mbox{ if
$\displaystyle n$ is even,}\end{array}\right.$

with equality if and only if $\displaystyle G$ is the path $\displaystyle
P_{n}$.

Sedlar [50] studied three AutoGraphiX conjectures involving proximity and
remoteness. She solved the conjecture by using the following graph
transformation for trees. Let $\displaystyle G$ be a tree. Then graph
transformtaion transforms $\displaystyle G$ into $\displaystyle G^{\prime}$,
where $\displaystyle G^{\prime}$ is either

  * 1)

Path $\displaystyle P_{n}$,

  * 2)

a tree consisting of four paths if equal length with a common end point,

  * 2)

a tree consisting of three paths of almost equal length with a common end
point.

Next, the following results prove that among those graphs the difference
$\displaystyle\overline{\ell}-\pi$ is maximum for the last.

######  Lemma 3.10 ([50]).

The difference $\displaystyle\overline{\ell}-\pi$ is greater for a tree
$\displaystyle G$ on $\displaystyle n\geq 4 $ vertices consisting of three
paths of almost equal length with a common end point than for path
$\displaystyle P_{n}$.

######  Lemma 3.11 ([50]).

The difference $\displaystyle\overline{\ell}-\pi$ is greater for the tree
$\displaystyle G$ on $\displaystyle n\geq 9$ vertices, where $\displaystyle
n=1$mod$\displaystyle(4)$, consisting of three paths of almost equal length
with a common end point than for the tree $\displaystyle G^{\prime}$ on
$\displaystyle n$ vertices consisting of four paths of equal length, where
$\displaystyle G^{\prime}$ is tree obtained from $\displaystyle G$ by some
transformation.

######  Lemma 3.12 ([50]).

Let $\displaystyle G$ be a tree on $\displaystyle n\geq 6$ vertices with at
least four leafs (a vertex of degree $\displaystyle 1$ in a tree).Then there
is a tree $\displaystyle G^{\prime}$ on $\displaystyle n$ vertices with three
leafs for which the difference $\displaystyle\overline{\ell}-\pi$ is greater
or equal than for $\displaystyle G$.

######  Lemma 3.13 ([50]).

Among trees with three leafs, the difference
$\displaystyle\overline{\ell}-\pi$ is maximal for the tree $\displaystyle G$
on $\displaystyle n$ vertices consisting of three paths of almost equal length
with a common end vertex.

Lemmas 3.10, 3.11, 3.12 and 3.13 can be summarized into the following theorem.

######  Theorem 3.14 ([50]).

Among all trees on $\displaystyle n\geq 4~{}(n,\neq 5)$ vertices with average
distance $\displaystyle\overline{\ell}$ and proximity $\displaystyle\pi$, the
difference $\displaystyle\overline{\ell}-\pi$ is maximal for a tree
$\displaystyle G$ composed of three paths of almost equal lengths with a
common end vertex.

From Theorem 3.14, the following result follows and settles a conjecture
involving proximity and remoteness.

######  Theorem 3.15 ([50]).

Among all connected graphs $\displaystyle G$ on $\displaystyle n\geq 3$
vertices with average distance $\displaystyle\overline{\ell}$ and proximity
$\displaystyle\pi$, the difference $\displaystyle\overline{\ell}-\pi$ is
maximum for a graph $\displaystyle G$ composed of three paths of almost equal
lengths with a common end point.

Sedlar [50] also proved partial results related to another conjecture: while
the conjecture is stated for all connected graphs, the results are proved for
trees only.

######  Lemma 3.16 ([50]).

Let $\displaystyle G$ be a tree on $\displaystyle n$ vertices with diameter
$\displaystyle D$ and let $\displaystyle P=v_{0}v_{1}\dots v_{D}$ be a
diametric path in $\displaystyle G$. If there is $\displaystyle
j\leq\frac{D}{2}$ such that the degree of $\displaystyle v_{k}$ is at most
$\displaystyle 2$ for $\displaystyle k\geq j+1$, then the difference
$\displaystyle ecc-\rho$ is greater or equal for the path $\displaystyle
P_{n}$ than for $\displaystyle G.$

######  Theorem 3.17 ([50]).

Among all trees on $\displaystyle n\geq 3$ vertices, the difference
$\displaystyle ecc-\rho$ is maximum for the path $\displaystyle P_{n}$.

The following sequence of results are given by Sedlar [50], which relates
remotness $\displaystyle\rho$ wity radius $\displaystyle r.$

######  Lemma 3.18 ([50]).

Let $\displaystyle G$ be a tree on $\displaystyle n$ vertices. There is a
caterpillar tree $\displaystyle G^{\prime}$ on $\displaystyle n$ vertices for
which the difference $\displaystyle\rho-r$ is less or equal than for
$\displaystyle G$.

######  Lemma 3.19 ([50]).

Let $\displaystyle G\neq P_{n}$ be a caterpillar tree on $\displaystyle n$
vertices with diameter $\displaystyle D$,remoteness $\displaystyle\rho$ and
only one centroidal vertex. Let $\displaystyle P=v_{0}v_{1}\dots v_{D}$ be the
diametric path in $\displaystyle G$ such that $\displaystyle v_{j}\in P$ is
the only centroidal vertex in $\displaystyle G$ and every of the vertices
$\displaystyle v_{j+1},\dots,v_{D}$ is of the degree at most $\displaystyle
2$. Then there is a caterpillar tree $\displaystyle G^{\prime}$ on
$\displaystyle n$ vertices of the diameter $\displaystyle D+1$ and the
remoteness at most $\displaystyle\rho+\frac{1}{2}.$

######  Lemma 3.20 ([50]).

Let $\displaystyle G\neq P_{n}$ be a caterpillar tree on $\displaystyle n$
vertices with diameter $\displaystyle D$, remoteness and exactly two
centroidal vertices. Let $\displaystyle P=v_{0}v_{1}\dots v_{D}$ be a
diametric path in $\displaystyle G$ such that $\displaystyle v_{j},v_{j+1}\in
P$ are centroidal vertices and every of the vertices $\displaystyle
v_{j+1},\dots,v_{D}$ is of degree at most $\displaystyle 2$. Then there is a
caterpillar tree $\displaystyle G^{\prime}$ on $\displaystyle n$ vertices of
the diameter $\displaystyle D+1$ and the remoteness at most
$\displaystyle\rho+\frac{1}{2}.$

######  Lemma 3.21 ([50]).

Let $\displaystyle G\neq P_{n}$ be a caterpillar tree on $\displaystyle n$
vertices with diameter $\displaystyle D$, remoteness $\displaystyle\rho$ and
exactly two centroidal vertices of different degrees. Let $\displaystyle
P=v_{0}v_{1}\dots v_{D}$ be a diametric path in $\displaystyle G$ such that
$\displaystyle v_{j},v_{j+1}\in P$ are centroidal vertices and every of the
vertices $\displaystyle v_{0},\dots,v_{j-1},v_{j+2},\dots,v_{D}$ is of degree
at most $\displaystyle 2$. Then there is a caterpillar tree $\displaystyle
G^{\prime}$ on $\displaystyle n$ vertices of the diameter $\displaystyle D+1$
and the remoteness at most $\displaystyle\rho+\frac{1}{2} $.

######  Lemma 3.22 ([50]).

Let $\displaystyle G\neq P_{n}$ be a caterpillar tree on $\displaystyle n$
vertices with diameter $\displaystyle D$, remoteness $\displaystyle\rho$ and
exactly two centroidal vertices of equal degrees. Let $\displaystyle
P=v_{0}v_{1}\dots v_{D}$ be a diametric path in $\displaystyle G$ such that
$\displaystyle v_{j},v_{j+1}\in P$ are centroidal vertices and every of the
vertices $\displaystyle v_{0},\dots,v_{j-1},v_{j+2},\dots,v_{D}$ is of degree
at most $\displaystyle 2$. Then the difference $\displaystyle\rho-r$ is less
or equal for path $\displaystyle P_{n}$ than for $\displaystyle G.$

######  Lemma 3.23 ([50]).

Let $\displaystyle G$ be a caterpillar tree on $\displaystyle n$ vertices. If
$\displaystyle n$ is odd, then the difference $\displaystyle\rho-r$ is less or
equal for path $\displaystyle P_{n}$ then for $\displaystyle G$. If
$\displaystyle n$ is even, then the difference $\displaystyle\rho-r$ is less
or equal for path $\displaystyle P_{n}-1$ with a leaf appended to a central
vertex than for G.

Lemmas 3.18, 3.19, 3.20, 3.21, 3.22 and 3.23 can be summarized in the
following result, which gives minimal trees for $\displaystyle\rho-r.$

######  Theorem 3.24 ([50]).

Let $\displaystyle G$ be a tree on $\displaystyle n$ vertices. If
$\displaystyle n$ is odd, then the difference $\displaystyle\rho-r$ is less or
equal for path $\displaystyle P_{n}$ then for $\displaystyle G$. If
$\displaystyle n$ is even, then the difference $\displaystyle\rho-r$ is less
or equal for path $\displaystyle P_{n-1}$ with a leaf appended to a central
vertex than for $\displaystyle G$.

Let $\displaystyle G$ be a connected graph. A vertex $\displaystyle u\in V(G)$
is called a peripheral vertex if $\displaystyle\sigma(u)=\rho(G)$. For a
vertex $\displaystyle u\in V(G),$ let $\displaystyle V_{i}(u)=\\{v\in
V(G)|d(u,v)=i\\}$ and $\displaystyle n_{i}(u)=|V_{i}(u)|$ for each
$\displaystyle i\in\\{1,2,\dots,d\\},$where $\displaystyle d=e_{G}(u).$ In
what follows, $\displaystyle V_{i}(u)$ is simply denoted by $\displaystyle
V_{i}$ for a peripheral vertex $\displaystyle u$ of $\displaystyle G.$ Wu and
Zhang [56] proved some lemmas and two theorems, first conjectured in [4].

######  Lemma 3.25 ([56]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 3.$
Let $\displaystyle u$ be a peripheral vertex of $\displaystyle G$ and let
$\displaystyle d=e_{G}(u).$ Let $\displaystyle G^{\prime}$ be the graph
obtained from $\displaystyle G$ by joining each pair of all nonadjacent
vertices $\displaystyle x,y$ of $\displaystyle G,$ where $\displaystyle x,y\in
V_{j}\cup V_{j+1}$ for some $\displaystyle j\in\\{1,2,\dots,d-1\\}$. We have

$\displaystyle\rho(G^{\prime})-\overline{\ell}(G^{\prime})\geq\rho(G)-\overline{\ell}(G),$

with equality if and only if $\displaystyle G^{\prime}=G.$

######  Lemma 3.26 ([56]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 3$.
Let $\displaystyle u$ be a peripheral vertex of $\displaystyle G$ and
$\displaystyle e_{G}(v)=d.$ Assume that $\displaystyle G[V_{j}\cup V_{j+1}]$
is a clique for each $\displaystyle j\in\\{0,1,\dots,d-1\\}$. Let
$\displaystyle G^{\prime}$ be the graph with $\displaystyle
V(G^{\prime})=V(G)$ and $\displaystyle E(G^{\prime})=E(G)\cup[xy:x\in
V_{d},y\in V_{d}.$ If $\displaystyle
d>\left\lfloor\frac{n+1}{2}\right\rfloor,$ then

$\displaystyle\rho(G^{\prime})-\overline{\ell}(G^{\prime})\leq\rho(G)-\overline{\ell}(G),$

with equality if and only if $\displaystyle n$ is even and $\displaystyle
d=\frac{n}{2}+11.$

######  Lemma 3.27 ([56]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 3$.
Let $\displaystyle u$ be a peripheral vertex of $\displaystyle G$ and
$\displaystyle e_{G}(v)=d.$ Assume that $\displaystyle G[V_{j}\cup V_{j+1}]$
is a clique for each $\displaystyle j\in\\{0,1,\dots,d-1\\}$. Let
$\displaystyle i$ be the smallest integer in $\displaystyle\\{1,2,\dots,d\\}$
such that $\displaystyle n_{i}(u)\geq 2.$ Let $\displaystyle
V_{i-1}(u)=\\{u_{i-1}\\}$ and $\displaystyle v$ a vertex in $\displaystyle
V_{i}(u)$. Denote by $\displaystyle G^{\prime}$ the graph with $\displaystyle
V(G^{\prime})=V(G)$ and $\displaystyle
E(G^{\prime})=E(G)\setminus(\\{u_{i-1}y:y\in V_{i}\setminus\\{v\\}\\}\cup A),$
where $\displaystyle A=\\{vx:x\in V_{i+1}\\},$ if $\displaystyle i\leq d-1$,
and $\displaystyle A=\emptyset$ otherwise. If $\displaystyle
d<\left\lfloor\frac{n+1}{2}\right\rfloor$, then

$\displaystyle\rho(G^{\prime})-\overline{\ell}(G^{\prime})>\rho(G)-\overline{\ell}(G).$

######  Lemma 3.28 ([56]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 3.$
Let $\displaystyle u$ be a peripheral vertex of $\displaystyle G$ and
$\displaystyle e_{G}(v)=d.$ Assume that $\displaystyle G[V_{j}\cup V_{j+1}]$
is a clique for each $\displaystyle j\in\\{0,1,\dots,d-1\\}$ and that
$\displaystyle n_{i}(u)\geq 2$ for some $\displaystyle
i\in\\{1,2,\dots,d-1\\}$. Further, assume that $\displaystyle i$ is the
minimum subject to the above condition. Let $\displaystyle v$ be a vertex in
$\displaystyle V_{i}(u)$ and $\displaystyle V_{i-1}=\\{u_{i-1}\\}$. Let
$\displaystyle G^{\prime}$ be the graph with $\displaystyle
V(G^{\prime})=V(G)$ and $\displaystyle E(G^{\prime})=E(G)\cup
A\setminus\\{vu_{i-1}\\},$ where $\displaystyle A=\\{vy:y\in V_{i+2}\\}$ if
$\displaystyle i\leq d-2$, and $\displaystyle A=\emptyset$ otherwise. If
$\displaystyle d=\left\lfloor\frac{n+1}{2}\right\rfloor,$ then

$\displaystyle\rho(G^{\prime})-\overline{\ell}(G^{\prime})>\rho(G)-\overline{\ell}(G).$

A Soltés or path-complete graph [53] is the graph obtained from a clique and a
path by adding at least one edge between an endpoint of the path and the
clique. The Soltés graphs are known to maximize the average distance
$\displaystyle\overline{\ell}$ when the number of vertices and of edges are
fixed [53].

Lemmas 3.25, 3.26, 3.27 and 3.28 lead the following result.

######  Theorem 3.29 ([56]).

Among all connected graphs $\displaystyle G$ on $\displaystyle n\geq 3$
vertices with average distance $\displaystyle\overline{\ell}$ and remoteness
$\displaystyle\rho$, the Soltés graphs with diameter
$\displaystyle\lfloor(n+1)/2\rfloor$ maximize the difference
$\displaystyle\rho-\overline{\ell}$.

Theorem 3.29 can be equivalently states as

######  Theorem 3.30 ([56]).

Among all connected graphs $\displaystyle G$ on $\displaystyle n\geq 3$
vertices with average distance $\displaystyle\overline{\ell}$ and remoteness
$\displaystyle\rho$, the maximum value of $\displaystyle\rho-\overline{\ell}$
is attained by the Soltés graphs with diameter $\displaystyle D$, where

$\displaystyle\begin{cases}D=\frac{n+1}{2},&\text{if $\displaystyle n$ is
odd}\\\ D\in\\{\frac{n}{2},\frac{n}{2}+1\\}&\text{if $\displaystyle n$ is
even}.\end{cases}$

Wu and Zhang [56] proved the following lemma, which helped them in proving
Theorem 3.32, first conjectured in [4].

######  Corollary 3.31 ([56]).

Let $\displaystyle G$ be connected graph with order $\displaystyle n\geq 5$.
If $\displaystyle n$ is odd and $\displaystyle r=\frac{n-1}{2}$. Then
$\displaystyle\rho\geq\dfrac{n+1}{4}$, with equality if and only if
$\displaystyle G$ is the cycle $\displaystyle C_{n}$ or the graph composed of
the cycle $\displaystyle C_{n}$ together with two crossed edges on four
successive vertices of the cycle.

######  Theorem 3.32 ([56]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and radius $\displaystyle r$. Then

$\displaystyle\rho-r\geq\left\\{\begin{array}[]{lll}\frac{3-n}{4}&&\mbox{ if
$\displaystyle n$ is odd }\\\ \frac{n^{2}}{4n-4}-\frac{n}{2}&&\mbox{ if
$\displaystyle n$ is even.}\end{array}\right.$

The inequality is best possible as shown by the cycle $\displaystyle C_{n}$ if
$\displaystyle n$ is even and by the graph composed of the cycle
$\displaystyle C_{n}$ together with two crossed edges on four successive
vertices of the cycle.

Figure 7: Graphs $\displaystyle C_{n}^{1},C_{n}^{2}$ and $\displaystyle
C_{n}^{1}$ (n is odd)

Hau, Chen and Das [31] obtained the folllowing result, earlier conjurectured
in [4].

######  Theorem 3.33 ([31]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and radius $\displaystyle r$. If
$\displaystyle n$ is odd, then $\displaystyle\rho-r\geq\frac{3-n}{4}$ with
equality if and only if $\displaystyle G\cong Cn$ or $\displaystyle
C_{n}^{i},~{}i=1,2,3$ (see Fig. 7), and if $\displaystyle n$ is even, then
$\displaystyle\rho-r\geq\frac{2n-n^{2}}{4(n-1)}$ with equality if and only if
$\displaystyle G\cong Cn.$

Dankelmann related proximity and remoteness with minimum degree and gave
several intresting results [18].

######  Theorem 3.34 ([18]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ and
minimum degree $\displaystyle\delta$, where $\displaystyle\delta\geq 2$. Then
there exists a spanning tree $\displaystyle T$ of $\displaystyle G$ with

$\displaystyle\pi(T)\leq\frac{3n}{4(\delta+1)}+3$

and

$\displaystyle\rho(T)\leq\frac{3n}{2(\delta+1)}+\frac{7}{2}.$

The following is an immediate consequence of Theorem 3.34

######  Corollary 3.35 ([18]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ and
minimum degree $\displaystyle\delta$, where $\displaystyle\delta\geq 2$. Then

$\displaystyle\pi(T)\leq\frac{3n}{4(\delta+1)}+3$

and

$\displaystyle\rho(T)\leq\frac{3n}{2(\delta+1)}+\frac{7}{2}.$

Next, we have result given upper bound for $\displaystyle\rho-\pi$ in terms of
order $\displaystyle n$ and minimum degree $\displaystyle\delta.$

######  Theorem 3.36 ([18]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ and
minimum degree $\displaystyle\delta$, where $\displaystyle\delta\geq 2$. Then

$\displaystyle\rho-\pi\leq\frac{3}{4(\delta+1)}+3.$

Dankelmann [19] obtained some new bounds on proximity and remoteness.

######  Theorem 3.37 ([19]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ and
minimum degree $\displaystyle\delta$, where $\displaystyle n\geq 20$ and
$\displaystyle\delta\geq 2$. Then

$\displaystyle D-\pi\leq\frac{9n}{4(\delta+1)}+\frac{3\delta}{4}.$

Next result gives sharp bound for remoteness in terms of diameter and order od
graph

######  Proposition 3.38 ([19]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ and
diameter $\displaystyle D$. Then

$\displaystyle\rho\geq\frac{nd}{2(n-1)},$

and this bound is sharp for all $\displaystyle n$ and $\displaystyle D$ with
$\displaystyle n\geq D+1\geq 33$ for which $\displaystyle nD$ is even.

######  Corollary 3.39 ([19]).

Let $\displaystyle G$ be a connected graph of diameter $\displaystyle D.$ Then

$\displaystyle\rho>\frac{D}{2},$

and the coefficient $\displaystyle\frac{1}{2}$ is best possible.

######  Theorem 3.40 ([19]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ and
minimum degree $\displaystyle\delta$, where
$\displaystyle\delta<\frac{n}{4}-1.$ Then

$\displaystyle r-\pi\leq\frac{3n}{4(\delta+1)}+\frac{8\delta+5}{4(\delta+1)},$

and this bound is best possible, apart from an additive constant.

######  Corollary 3.41 ([19]).

Let $\displaystyle G$ be a connected graph. Then

$\displaystyle\rho>\frac{r}{2}.$

The girth $\displaystyle g$ of a graph $\displaystyle G$ is the length of its
smallest cycle.
A lollipop  $\displaystyle L_{n,g}$ is the graph obtained from a cycle
$\displaystyle C_{g}$ and a path $\displaystyle P_{n-g}$ by adding an edge
between an endpoint of $\displaystyle P_{n-g}$ and a vertex of the cycle
$\displaystyle C_{g}$. The lollipop $\displaystyle L_{11,7}$ is illustrated in
Figure 9. For a lollipop $\displaystyle L_{n,g}$, we have

$\displaystyle\rho(L_{n,g})=\left\\{\begin{array}[]{ccc}\frac{n}{2}-\frac{g(g-2)}{4(n-1)}&&\mbox{
if $\displaystyle g$ is even }\\\ \frac{n}{2}-\frac{g(g-2)+1}{4(n-1)}&&\mbox{
if $\displaystyle g$ is odd. }\end{array}\right.$

A turnip $\displaystyle T_{n,g}$, with $\displaystyle n\geq g\geq 3$, is the
graph obtained from a cycle $\displaystyle C_{g}$ by attaching $\displaystyle
n-p$ pending edges to one vertex from the cycle. The turnip $\displaystyle
T_{10,5}$ is illustarated in Figure 9. If $\displaystyle g=n$, the turnip
$\displaystyle T_{n,g}=T_{n,n}$ is the cycle $\displaystyle C_{n}$. For a
turnip $\displaystyle T_{n,g}$, we have

$\displaystyle\pi(T_{n,g})=\left\\{\begin{array}[]{ccl}\frac{g^{2}-4g+4n-1}{4(n-1)}&&\mbox{
if $\displaystyle g$ is odd}\\\ \frac{g^{2}-4g+4n}{4(n-1)}&&\mbox{ if
$\displaystyle g$ is even.}\end{array}\right.$

Figure 8: The lollipop $\displaystyle L_{11,7}$.

Figure 9: The turnip $\displaystyle T_{10,5}$.

######  Lemma 3.42 ([10]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with girth $\displaystyle g$.
$\displaystyle(i)$ If $\displaystyle g=3$, then $\displaystyle\pi\geq 1$ with
equality if and only if $\displaystyle G$ contains a dominating vertex.
$\displaystyle(ii)$ If $\displaystyle g=4$, then $\displaystyle\pi\geq
n/(n-1)$ with equality if and only if $\displaystyle G$ contains the turnip
$\displaystyle T_{n,4}$ as a spanning subgraph and is a spanning subgraph of
the complete bipartite graph $\displaystyle K_{n-2,2}$.
$\displaystyle(iii)$ If $\displaystyle g\geq 5$, then
$\displaystyle\pi\geq\pi(T_{n,g})$ with equality if and only if $\displaystyle
G$ is the turnip $\displaystyle T_{n,g}$.

######  Theorem 3.43 ([10]).

For any connected graph $\displaystyle G$ on $\displaystyle n\geq 3$ vertices
with a finite girth $\displaystyle g$ and proximity $\displaystyle\pi$, we
have

$\left.\begin{array}[]{lr}\mbox{if $\displaystyle n$ is odd,
}&\frac{1-3n}{4}\\\ \mbox{if $\displaystyle n$ is even,
}&\frac{4n-3n^{2}}{4n-4}\end{array}\right\\}\leq\pi-g\leq\left\\{\begin{array}[]{ll}\frac{n-11}{4}-\frac{1}{n-1}&\mbox{if
$\displaystyle n$ is odd, }\\\ \frac{n-11}{4}-\frac{3}{4(n-1)}&\mbox{if
$\displaystyle n$ is even; }\end{array}\right.$ (2)
$4\leq\pi+g\leq\left\\{\begin{array}[]{lr}\frac{5n+1}{4}&\mbox{if
$\displaystyle n$ is odd, }\\\ \frac{5n^{2}-4n}{4(n-1)}&\mbox{if
$\displaystyle n$ is even; }\end{array}\right.$ (3)
$\frac{1}{2\left\lfloor\sqrt{n}\right\rfloor+1}+\frac{\left\lfloor\sqrt{n}\right\rfloor(\left\lfloor\sqrt{n}\right\rfloor-1)}{(2\left\lfloor\sqrt{n}\right\rfloor+1)(n-1)}\leq\frac{\pi}{g}\leq\left\\{\begin{array}[]{ll}\frac{n^{2}-4}{12n-12}&\mbox{if
$\displaystyle n$ is even, }\\\ \frac{n+1}{12}-\frac{1}{3n-3}&\mbox{if
$\displaystyle n$ is odd; }\end{array}\right.$ (4) $3\leq\pi\cdot
g\leq\left\\{\begin{array}[]{lr}\frac{n^{2}+n}{4}&\mbox{if $\displaystyle n$
is odd, }\\\ \frac{n^{3}}{4(n-1)}&\mbox{if $\displaystyle n$ is even;
}\end{array}\right.$ (5)

The lower bound in (2) and the upper bounds in (3) and (5) are reached if and
only if $\displaystyle G$ is the cycle $\displaystyle C_{n}$. The upper bounds
in (2) and (4) are reached if and only if $\displaystyle G$ is the lollipop
$\displaystyle L_{n,3}$. The lower bounds in (3) and (5) are reached if and
only if $\displaystyle G$ contains a dominating vertex. The lower bound in (4)
is reached if and only if $\displaystyle G$ is the turnip $\displaystyle
T_{n,s}$, where $\displaystyle s=2\left\lfloor\sqrt{n}\right\rfloor+1$ when
$\displaystyle\sqrt{n}$ is not an integer, and if and only if $\displaystyle
G$ is any one of the turnips $\displaystyle T_{n,2\sqrt{n}-1}$, $\displaystyle
T_{n,2\sqrt{n}}$ or $\displaystyle T_{n,2\sqrt{n}+1}$ when
$\displaystyle\sqrt{n}$ is an integer.

######  Lemma 3.44 ([10]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 4$ vertices
with girth $\displaystyle g\leq n-1$ and remoteness $\displaystyle\rho$. Then

$\displaystyle\rho\leq\rho(L_{n,g})$

with equality if and only if $\displaystyle G$ is the lollipop $\displaystyle
L_{n,g}$.

######  Theorem 3.45 ([10]).

For any connected graph $\displaystyle G$ on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and girth $\displaystyle g$, we have

$\left.\begin{array}[]{lr}\mbox{if $\displaystyle n$ is even,
}&\frac{4n-3n^{2}}{4n-4}\\\ \mbox{if $\displaystyle n$ is odd,
}&\frac{1-3n}{4}\end{array}\right\\}\leq\rho-g\leq\frac{(n+1)(n-2)}{2n-2}-3;$
(6) $4\leq\rho+g\leq\left\\{\begin{array}[]{ll}\frac{5n^{2}-4n}{4n-4}&\mbox{if
$\displaystyle n$ is even, }\\\ \frac{5n+1}{4}&\mbox{if $\displaystyle n$ is
odd; }\end{array}\right.$ (7) $\frac{\rho}{g}\leq\frac{(n+1)(n-2)}{6n-6};$ (8)
$3\leq\rho\cdot g\leq\rho(L_{n,g^{*}})\cdot g^{*}$ (9)

where $\displaystyle g^{*}$ is the girth for which
$\displaystyle\rho(L_{n,g_{i}})\cdot g_{i}$, $\displaystyle i=1,\ldots,4$, is
maximum with $\displaystyle
g_{1}=\left\lfloor\frac{2+\sqrt{6n^{2}-6n+4}}{3}\right\rfloor$, $\displaystyle
g_{2}=\left\lceil\frac{2+\sqrt{6n^{2}-6n+4}}{3}\right\rceil$, $\displaystyle
g_{3}=\left\lfloor\frac{2+\sqrt{6n^{2}-6n+7}}{3}\right\rfloor$ and
$\displaystyle g_{4}=\left\lceil\frac{2+\sqrt{6n^{2}-6n+7}}{3}\right\rceil$.
The lower bound in (6) and the upper bound in (7) are reached if and only if
$\displaystyle G$ is the cycle $\displaystyle C_{n}$. The upper bounds in (6)
and (8) are reached if and only if $\displaystyle G$ is the lollipop
$\displaystyle L_{n,3}$. The lower bounds in (7) and (9) are reached if and
only if $\displaystyle G$ is the complete graph $\displaystyle K_{n}$. The
upper bound in (9) is reached if and only if $\displaystyle G$ is the lollipop
$\displaystyle L_{n,g^{*}}$.

The lower bound on $\displaystyle\rho/g$, first conjectured using AGX [1], was
proved in [30].

######  Theorem 3.46 ([30]).

For any connected graph $\displaystyle G$ on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and girth $\displaystyle g$,

$\displaystyle\frac{\rho}{g}\geq\left\\{\begin{array}[]{ll}\frac{n}{4n-4}&\mbox{if
$\displaystyle n$ is even, }\\\ \frac{n+1}{4n}&\mbox{if $\displaystyle n$ is
odd. }\end{array}\right.$

with equality if and only if $\displaystyle G$ is a cycle $\displaystyle
C_{n}$.

######  Theorem 3.47 ([30]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 2$ vertices
with proximity $\displaystyle\pi$ and average distance
$\displaystyle\overline{\ell}$. Then

$\displaystyle\frac{\pi}{\overline{\ell}}\geq\frac{n}{2(n-1)},$

with equality if and only if $\displaystyle G$ is isomorphic to the star
$\displaystyle S_{n}$.

The following is an immediate consequence of Theorem 3.47.

######  Corollary 3.48 ([30]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 2$ vertices
with proximity $\displaystyle\pi$, average degree $\displaystyle\overline{d}$
and average distance $\displaystyle\overline{\ell}$. Then

$\displaystyle\pi.\overline{d}\geq\overline{\ell},$

with equality if and only if $\displaystyle G$ is isomorphic to the star
$\displaystyle S_{n}$.

Dankelmann and Mafunda [21] gave results relating $\displaystyle\pi$ with
diameter and radius of triangle-free and $\displaystyle C_{4}$-free graphs.

######  Theorem 3.49 ([21]).

If $\displaystyle G$ is a connected, triangle-free graph of order
$\displaystyle n\geq 8$, minimum degree $\displaystyle\delta\geq 3$ and
diameter $\displaystyle D$, then

$\displaystyle\pi\geq\frac{\delta(D-4)(D-1)}{8(n-1)}.$

######  Corollary 3.50 ([21]).

If $\displaystyle G$ is a connected, triangle-free graph of order
$\displaystyle n\geq 8$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle D-\pi\leq\frac{3(n-1)}{2\delta}+\frac{5}{2}.$

This bound is sharp apart from an additive constant.

######  Theorem 3.51 ([21]).

If $\displaystyle G$ is a connected, triangle-free graph of order
$\displaystyle n\geq 6$, minimum degree $\displaystyle\delta\geq 3$ and radius
$\displaystyle r\geq 1$, then

$\displaystyle\pi\geq\frac{\delta}{2(n-1)}\left(r^{2}-7r+\frac{47}{8}\right).$

######  Corollary 3.52 ([21]).

If $\displaystyle G$ is a connected, triangle-free graph of order
$\displaystyle n\geq 6$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle r-\pi\leq\frac{n-1}{2\delta}+\frac{11}{2}.$

This bound is sharp apart from an additive constant.

######  Theorem 3.53 ([21]).

If $\displaystyle G$ is a connected, $\displaystyle C_{4}$-free graph of order
$\displaystyle n\geq 16$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle\pi\geq\frac{\delta^{2}-2\left\lfloor\frac{\delta}{2}\right\rfloor+1}{5(n-1)}\left(r^{2}-8r+\frac{127}{8}\right).$

######  Corollary 3.54 ([21]).

If $\displaystyle G$ is a connected, $\displaystyle C_{4}$-free graph of order
$\displaystyle n\geq 16$ and minimum degree $\displaystyle\delta\geq 3$, then

$\displaystyle
r-\pi\leq\frac{5(n-1)}{4\left(\delta^{2}-2\left\lfloor\frac{\delta}{2}\right\rfloor+1\right)}+4.$

Czabarka et al. [17] gave the upper bounds on $\displaystyle\pi$ in
triangulations and quadrangulations.

The plane graph $\displaystyle G$ is a triangulation (resp. quadrangulation)
if every face is a triangle (resp. 4-cycle).

######  Proposition 3.55 ([17]).

  * (a)

Let $\displaystyle G$ be a $\displaystyle 5$-connected triangulation of order
$\displaystyle n$. Then

$\displaystyle\rho\leq\frac{n+4}{10}+\epsilon_{n},$

where $\displaystyle\epsilon_{n}=-\frac{3}{5(n-1)}$ if $\displaystyle n\equiv
0$ (mod $\displaystyle 5$), $\displaystyle\epsilon_{n}=-\dfrac{1}{n-1}$ if
$\displaystyle n\equiv 1$ (mod $\displaystyle 5$),
$\displaystyle\epsilon_{n}=\dfrac{2}{5(n-1)}$ if $\displaystyle n\equiv 2$
(mod $\displaystyle 5$), and $\displaystyle\epsilon_{n}=-\frac{2}{5(n-1)}$ if
$\displaystyle n\equiv 3,4$ (mod $\displaystyle 5$).

  * (b)

If $\displaystyle G$ is a $\displaystyle 3$-connected quadrangulation of order
$\displaystyle n$, then

$\displaystyle\rho\leq\frac{n+2}{6}+\epsilon_{n},$

where $\displaystyle\epsilon_{n}=-\frac{5}{3(n-1)}$ if $\displaystyle n\equiv
0$ (mod $\displaystyle 3$), $\displaystyle\epsilon_{n}=-\frac{1}{n-1}$ if
$\displaystyle n\equiv 1$ (mod $\displaystyle 3$), and
$\displaystyle\epsilon_{n}=\dfrac{1}{3(n-1)}$ if $\displaystyle n\equiv 2$(mod
$\displaystyle 3$).

##  4 Proximity and Remoteness Compared to other Invariants

Aouchiche and Hasen [4] related remoteness with the independence number and
presented the following results.

######  Proposition 4.1 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 8$ vertices
with remoteness $\displaystyle\rho$ and independence number
$\displaystyle\alpha$. Then

$\displaystyle\rho-\alpha\geq 3-n-\frac{1}{n-1}$

and

$\displaystyle\rho-\alpha\leq\left\\{\begin{array}[]{lcl}\frac{n-3}{8}-\frac{3}{8(n-1)}&&\mbox{
if } n=0\,\,(mod\,\,4),\\\ \frac{n-3}{8}&&\mbox{ if } n=1\,\,(mod\,\,2),\\\
\frac{n-3}{8}+\frac{1}{8(n-1)}&&\mbox{ if }
n=2\,\,(mod\,\,4).\end{array}\right.$

The lower bound is attained if and only if $\displaystyle G$ is the star
$\displaystyle S_{n}$. The bound is best possible as shown by the kites
$\displaystyle KI_{n,n_{0}}$ where $\displaystyle n_{0}=(n+n\,\,(mod\,\,
4))/2$.

######  Proposition 4.2 ([4]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ with
remoteness $\displaystyle\rho$ and matching number $\displaystyle\mu$. Then

$\displaystyle\rho-\mu\leq\left\\{\begin{array}[]{lll}\frac{n+1}{8}+\frac{1}{8(n-1)}&&\mbox{
if }n=0\,\,(mod\,\, 4),\\\ \frac{n+1}{8}&&\mbox{ if }n=1\,\,(mod\,\, 4),\\\
\frac{n+1}{8}-\frac{3}{8(n-1)}&&\mbox{ if }n=2\,\,(mod\,\, 4),\\\
\frac{n+1}{8}&&\mbox{ if }n=3\,\,(mod\,\, 4),\\\ \end{array}\right.$

with equality if and only if $\displaystyle G$ is the comet $\displaystyle
CO_{n,n-D^{*}+1}$ where $\displaystyle
D^{*}=2\left\lfloor\frac{n+2}{4}\right\rfloor$.

The (vertex) connectivity $\displaystyle\nu$ of a connected graph
$\displaystyle G$ is the minimum number of vertices whose removal disconnects
$\displaystyle G$ or reduces it to a single vertex. The algebraic connectivity
$\displaystyle a$ of a graph $\displaystyle G$ is the second smallest
eigenvalue of its Laplacian $\displaystyle L=Diag-A$, where $\displaystyle
Diag$ is the diagonal square matrix indexed by the vertices of $\displaystyle
G$ whose diagonal entries are the degrees in $\displaystyle G$, and
$\displaystyle A$ is the adjacency matrix of $\displaystyle G$.

######  Theorem 4.3 ([49]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 2$ vertices
with vertex connectivity $\displaystyle\nu$, algebraic connectivity
$\displaystyle a$ and remoteness $\displaystyle\rho$. Then

$\displaystyle\nu\cdot\rho\leq n-1$

with equality if and only if $\displaystyle G$ is the complete graph
$\displaystyle K_{n}$; and

$\displaystyle a\cdot\rho\leq n$

with equality if and only if $\displaystyle G$ is the complete graph
$\displaystyle K_{n}$. Moreover, if $\displaystyle G$ is not complete, then

$\displaystyle a\cdot\rho\leq n-1-\frac{1}{n-1}$

with equality if and only if $\displaystyle G\cong K_{n}-M$, where
$\displaystyle M$ is any non empty set of disjoint edges.

######  Theorem 4.4 ([30]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with remoteness $\displaystyle\rho$ and maximum degree
$\displaystyle\triangle$. If
$\displaystyle\triangle\geq\left\lceil\frac{n}{4}\right\rceil+1,$ then

$\displaystyle\rho+\triangle\geq\begin{cases}\frac{n+9}{4}&\text{if
$\displaystyle n$ is odd},\\\ 2+\frac{n^{2}}{4n-4}&\text{if $\displaystyle n$
is even},\end{cases}$

with equality if and only if $\displaystyle G\cong C_{3}$ or $\displaystyle
G\cong C_{4}.$

######  Theorem 4.5 ([30]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n$ vertices,
$\displaystyle m$ edges with proximity $\displaystyle\pi$ and average degree
$\displaystyle\overline{d}$. If $\displaystyle m\leq\frac{2(n-1)^{2}}{n},$
then

$\displaystyle\pi.\overline{d}\leq n-1.$

######  Theorem 4.6 ([30]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with clique number $\displaystyle\omega$ and remoteness $\displaystyle\rho$.
Then

$\displaystyle\rho\leq\frac{n^{2}-\omega^{2}-n+3\omega-2}{2(n-1)},$

with equality if and only if $\displaystyle G\cong Ki_{n,\omega}.$

######  Theorem 4.7 ([30]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with clique number $\displaystyle\omega$, remoteness $\displaystyle\rho$ and
proximity $\displaystyle\pi$. Then

$\displaystyle\rho+\pi\leq\begin{cases}\frac{3n^{2}-2\omega^{2}-2n+6\omega-5}{4(n-1)}&\text{if
$\displaystyle n$ is odd},\\\
\frac{3n^{2}-2\omega^{2}-2n+6\omega-4}{4(n-1)}&\text{if $\displaystyle n$ is
odd},\end{cases}$

with equality if and only if $\displaystyle G\cong P_{n}.$

The next result gives an upper bound on $\displaystyle\rho-\pi$ in terms of
$\displaystyle n$ and $\displaystyle\omega.$

######  Theorem 4.8 ([30]).

Let $\displaystyle G$ be a connected graph on $\displaystyle n\geq 3$ vertices
with clique number $\displaystyle\omega$, remoteness $\displaystyle\rho$ and
proximity $\displaystyle\pi$. Then

$\displaystyle\rho-\pi\leq\frac{(n-\omega)(n+\omega-3)}{2(n-1)},$

with equality if and only if $\displaystyle G\cong Ki_{n,n-1}.$

######  Theorem 4.9 ([30]).

Let $\displaystyle G$ be a connected bipartite graph with each partite set of
cardinality $\displaystyle n\geq 2$. If the average distance

$\displaystyle\overline{\ell}\leq\frac{3}{2}+\frac{n-2}{2n(2n-1)},$

then $\displaystyle G$ is Hamiltonion.

######  Corollary 4.10 ([30]).

Let $\displaystyle G$ be a connected bipartite graph with each partite set of
cardinality $\displaystyle n\geq 2$. If

$\displaystyle\rho\leq\frac{3}{2}+\frac{n-2}{2n(2n-1)},$

then $\displaystyle G$ is Hamiltonion.

The distance eigenvalues of a connected graph, denoted by
$\displaystyle\partial_{1},\partial_{2},\ldots,\partial_{n}$, are those of its
distance matrix, and are indexed such that
$\displaystyle\partial_{1}\geq\partial_{2}\geq\ldots\geq\partial_{n}$. For a
survey on distance spectra of graphs see [8]. Next, we have results relating
proximity $\displaystyle\pi$ and remoteness $\displaystyle\rho$ with the
distance eigenvalues of graphs.

######  Theorem 4.11 ([9]).

Let $\displaystyle G$ be a graph on $\displaystyle n\geq 4$ vertices with
largest distance eigenvalue $\displaystyle\partial_{1}$, proximity
$\displaystyle\pi$ and remoteness $\displaystyle\rho$. Then

$\displaystyle\pi\leq\overline{\ell}\leq\frac{\partial_{1}}{n-1}\leq\rho$

with equalities if and only if $\displaystyle G$ is a transmission regular
graph.

######  Corollary 4.12 ([9]).

Let $\displaystyle G$ be a graph on $\displaystyle n\geq 2$ vertices with
largest distance eigenvalue $\displaystyle\partial_{1}$ and proximity
$\displaystyle\pi$. Then

$\displaystyle\partial_{1}-\pi\geq n-2$

with equalities if and only if $\displaystyle G$ is the complete graph
$\displaystyle K_{n}$.

######  Corollary 4.13 ([9]).

Let $\displaystyle G$ be a graph on $\displaystyle n\geq 4$ vertices with
second largest distance eigenvalue $\displaystyle\partial_{2}$ and remoteness
$\displaystyle\rho$. Then

$\displaystyle\rho+\partial_{2}\geq 0$

with equality if and only if $\displaystyle G$ is the complete graph
$\displaystyle K_{n}$.

The bound in the above corollary is best possible among the bounds of the form
$\displaystyle\rho+\partial_{k}\geq 0$, with a fixed integer $\displaystyle
k$, over the class of all connected graphs. Indeed, if we consider the
complete bipartite graphs $\displaystyle K_{\left\lfloor
n/2\right\rfloor,\left\lceil n/2\right\rceil}$, on $\displaystyle n\geq 3$, by
direct calculation we get

$\displaystyle\rho(K_{\left\lfloor n/2\right\rfloor,\left\lceil
n/2\right\rceil})+\partial_{3}(K_{\left\lfloor n/2\right\rfloor,\left\lceil
n/2\right\rceil})=\left\\{\begin{array}[]{lcl}-\frac{1}{2}&&\mbox{ if
$\displaystyle n$ is odd,}\\\ \\\ -\frac{1}{2}-\frac{1}{2(n-1)}&&\mbox{ if
$\displaystyle n$ is even,}\\\ \end{array}\right.$

which is negative for $\displaystyle n\geq 3$.

######  Proposition 4.14 ([9]).

Let $\displaystyle T$ be a tree on $\displaystyle n\geq 4$ vertices with
remoteness $\displaystyle\rho$, diameter $\displaystyle D$ and distance
spectrum
$\displaystyle\partial_{1}\geq\partial_{2}\geq\cdots\geq\partial_{n}$. Then

$\displaystyle\rho+\partial_{\left\lfloor\frac{D}{2}\right\rfloor}>0.$

######  Corollary 4.15 ([9]).

Let $\displaystyle G$ be a graph on $\displaystyle n\geq 4$ vertices with
second largest distance eigenvalue $\displaystyle\partial_{2}$ and proximity
$\displaystyle\pi$. Then

$\displaystyle\pi+\partial_{n}\leq 0$

with equality if and only if $\displaystyle G$ is the complete graph
$\displaystyle K_{n}$.

######  Theorem 4.16 ([9]).

Let $\displaystyle G$ be a graph on $\displaystyle n\geq 4$ vertices with
largest distance eigenvalue $\displaystyle\partial_{1}$ and remoteness
$\displaystyle\rho$. Then

$\displaystyle\partial_{1}-\rho\geq n-2$

with equalities if and only if $\displaystyle G$ is the complete graph
$\displaystyle K_{n}$.

######  Proposition 4.17 ([9]).

Let $\displaystyle G$ be a graph on $\displaystyle n\geq 4$ vertices with
least distance eigenvalue $\displaystyle\partial_{n}$ and remoteness
$\displaystyle\rho$. Then

$\displaystyle\partial_{n}+\rho\leq 0$

with equallity if and only if $\displaystyle G$ is $\displaystyle K_{n}$.

######  Theorem 4.18 ([9]).

Let $\displaystyle G$ be a graph on $\displaystyle n\geq 4$ vertices with
second largest distance eigenvalue $\displaystyle\partial_{2}$ and proximity
$\displaystyle\pi$. Then

$\displaystyle\pi+\partial_{2}\geq 0$

with equality if and only if $\displaystyle G$ is the complete graph
$\displaystyle K_{n}$.

######  Proposition 4.19 ([9]).

Let $\displaystyle T$ be a graph on $\displaystyle n\geq 4$ vertices with
proximity $\displaystyle\pi$, diameter $\displaystyle D$ and distance spectrum
$\displaystyle\partial_{1}\geq\partial_{2}\geq\cdots\geq\partial_{n}$. Then

$\displaystyle\pi+\partial_{\left\lfloor\frac{D}{2}\right\rfloor}>0.$

Lin, Das and Wu [37] proved two theorems, earlier as conjectures in [9].
Following lemmas and results were given.

######  Lemma 4.20 ([37]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ with
diameter $\displaystyle D$ and remoteness $\displaystyle\rho$. Then

$\displaystyle\rho\geq\frac{D}{2}.$

######  Theorem 4.21 ([37]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 4$
with diameter $\displaystyle D$, remoteness $\displaystyle\rho$ and distance
eigenvalues $\displaystyle\partial_{1}\geq\dots\geq\partial_{n}.$ Then we have
the following statements.

  * (i)

If $\displaystyle D=2,$ then

$\displaystyle\rho+\partial_{3}\geq\frac{\left\lceil\frac{n}{2}\right\rceil-2}{n-1}-1,$

with equality holding if and only if $\displaystyle G\cong K_{n_{1},n_{2}}.$

  * (ii)

If $\displaystyle D\geq 3$, then

$\displaystyle\rho+\partial_{3}>\frac{d}{2}-1.2.$

######  Theorem 4.22 ([37]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 4$
with diameter $\displaystyle D$, remoteness $\displaystyle\rho$ and distance
spectrum $\displaystyle\partial_{1}\geq\dots\geq\partial_{n}.$ Then

$\displaystyle\rho+\partial_{\left\lfloor\frac{7D}{8}\right\rfloor}>0.$

Besides above results, more results regarding remoteness and distance
eigenvalues were given in [37].

Denote by $\displaystyle H_{n-D}(n>D)$ a graph of order $\displaystyle n-D$
such that $\displaystyle V(H_{n-d})=V(\overline{K}_{n-d})$ and $\displaystyle
E(H_{n-D})\supseteq E(\overline{K}_{n-D}),$ where
$\displaystyle\overline{K}_{n-D}$ is a null graph of order $\displaystyle
n-D.$ Let $\displaystyle H_{n,D}$ be a graph of order $\displaystyle n$ with
diameter $\displaystyle D$ obtained by joining $\displaystyle n-D$ edges
between one end of the path $\displaystyle P_{D}$ with each vertex of
$\displaystyle H_{n-D}.$

######  Lemma 4.23 ([37]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ with
diameter $\displaystyle D$ and remoteness $\displaystyle\rho$. Then

$\displaystyle\rho\leq D-\frac{D^{2}-D}{2(n-1)},$

with equality holding if and only if $\displaystyle G\cong H_{n,D}.$

######  Theorem 4.24 ([37]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ with
diameter $\displaystyle D$ and remoteness $\displaystyle\rho$. Then

$\displaystyle\rho+\partial_{n}\leq-\frac{D^{2}-D}{2(n-1)},$

with equality holding if and only if $\displaystyle G\cong K_{n}.$

######  Lemma 4.25 ([37]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n$ with
diameter $\displaystyle D\geq 3.$ Then

$\displaystyle\partial_{1}>n-2+D.$

######  Theorem 4.26 ([37]).

Let $\displaystyle G\ncong K_{n}$ be a connected graph of order $\displaystyle
n$ and remoteness $\displaystyle\rho$. Then

$\displaystyle\partial_{1}-\rho\geq\frac{n-1+\sqrt{(n-1)^{2}+8}}{2}-\frac{n}{n-1},$

with equality holding if and only if $\displaystyle G\cong K_{n}-e,$ where
$\displaystyle e$ is an edge of $\displaystyle G.$

Jia and Song [33] obtained various results related to remoteness and distance,
distance (signless) Laplacian eigenvalues of graphs.

######  Theorem 4.27 ([33]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 4$
with remoteness $\displaystyle\rho$. Thenn

$\displaystyle n\leq\rho+\partial_{1}\leq\rho(P_{n})+\partial_{1}(P_{n}),$

with the left equality holding if and only if $\displaystyle G\cong K_{n}$ and
the right equality holding if and onlyif $\displaystyle G\cong P_{n}.$

######  Theorem 4.28 ([33]).

Let $\displaystyle G\ncong K_{n}$ be a connected graph of order $\displaystyle
n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\rho+\partial_{1}\geq\frac{n}{n-1}+\frac{n-1+\sqrt{(n-1)^{2}+8}}{2},$

with equality holding if and only if $\displaystyle G\cong K_{n}-e.$

######  Theorem 4.29 ([33]).

Let $\displaystyle G\ncong(K_{n},K_{n}-e)$ be a connected graph of order
$\displaystyle n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\rho+\partial_{1}\geq\frac{n}{n-1}+\frac{n-1+\sqrt{(n-1)^{2}+16}}{2},$

with equality holding if and only if $\displaystyle G\cong K_{n}-2e,$ where
$\displaystyle 2e$ are two matching edges.

######  Theorem 4.30 ([33]).

Let $\displaystyle G$ be a complete bipartite graph of order $\displaystyle
n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\rho+\partial_{2}\geq n-\frac{1}{n-1}-\sqrt{n^{2}-3n+3},$

with equality holding if and only if $\displaystyle G$ is star.

For connected graphs Jia and Song [33] proposed the following conjecture.

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

Let $\displaystyle G\ncong(K_{n},K_{n}-e)$ be a connected graph of order
$\displaystyle n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\rho+\partial_{2}\geq\frac{n}{n-1}+\frac{n-1-\sqrt{(n-1)^{2}+8}}{2},$

with equality holding if and only if $\displaystyle G\cong K_{n}-2e,$ where
$\displaystyle 2e$ are two matching edges.

######  Theorem 4.31 ([33]).

Let $\displaystyle G\ncong K_{n}$ be a connected graph of order $\displaystyle
n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\rho-\partial_{n}\geq 2,$

with equality holding if and only if $\displaystyle G\cong K_{n}.$

######  Theorem 4.32 ([33]).

Let $\displaystyle G\ncong K_{n}$ be a connected graph of order $\displaystyle
n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\rho-\partial_{n}\geq 3+\frac{1}{n-1},$

with equality holding if and only if $\displaystyle G\cong K_{n}-me,$ where
$\displaystyle me$ denotes $\displaystyle m$ matching edges.

The distance Laplacian eigenvalues of a connected graph, denoted by
$\displaystyle\partial_{1}^{L},\partial_{2}^{L},\ldots,\partial_{n}^{L}$, are
those of its distance Laplacian matrix, and are indexed such that
$\displaystyle\partial_{1}^{L}\geq\partial_{2}^{L}\geq\ldots\geq\partial_{n}^{L}$.

######  Theorem 4.33 ([33]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 4$
with remoteness $\displaystyle\rho$. Then

$\displaystyle
n+1\leq\rho+\partial_{1}^{L}\leq\rho(P_{n})+\partial_{1}^{L}(P_{n}),$

with the left equality holding if and only if $\displaystyle G\cong K_{n}$ and
the right equality holding if and only if $\displaystyle G\cong P_{n}.$

######  Theorem 4.34 ([33]).

Let $\displaystyle G\ncong K_{n}$ be a connected graph of order $\displaystyle
n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\rho+\partial_{1}^{L}\geq n+\frac{1}{n-1}+3,$

with equality holding if and only if $\displaystyle G\cong K_{n}-me,$ where
$\displaystyle me$ denotes $\displaystyle m$ matchings.

######  Theorem 4.35 ([33]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 4$
with remoteness $\displaystyle\rho$. Then

$\displaystyle\partial_{1}^{L}-\rho\geq n-1,$

with equality holding if and only if $\displaystyle G\cong K_{n}.$

######  Theorem 4.36 ([33]).

Let $\displaystyle G\ncong K_{n}$ be a connected graph of order $\displaystyle
n\geq 5$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\partial_{1}^{L}-\rho\geq n+1-\frac{1}{n-1},$

with equality holding if and only if $\displaystyle G\cong K_{n}-me,$ where
$\displaystyle 1\leq m\leq\left\lfloor\frac{n}{2}\right\rfloor.$

The distance signless Laplacian eigenvalues of a connected graph, denoted by
$\displaystyle\partial_{1}^{Q},\partial_{2}^{Q},\ldots,\partial_{n}^{Q}$, are
those of its distance signless Laplacian matrix, and are indexed such that
$\displaystyle\partial_{1}^{Q}\geq\partial_{2}^{Q}\geq\ldots\geq\partial_{n}^{Q}$.

######  Theorem 4.37 ([33]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 4$
with remoteness $\displaystyle\rho$. Then

$\displaystyle 2n\leq 2\rho+\partial_{1}^{Q}\leq
2\rho(P_{n})+\partial_{1}^{Q}(P_{n}),$

with the left equality holding if and only if $\displaystyle G\cong K_{n}$ and
the right equality holding if and only if $\displaystyle G\cong P_{n}.$

######  Theorem 4.38 ([33]).

Let $\displaystyle G\ncong K_{n}$ be a connected graph of order $\displaystyle
n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle
2\rho+\partial_{1}^{Q}\geq\frac{3n-2+\sqrt{(n-2)^{2}+16}}{2}+\frac{2n}{n-1},$

with equality holding if and only if $\displaystyle G\cong K_{n}-e.$

######  Theorem 4.39 ([33]).

Let $\displaystyle G\ncong(K_{n},K_{n}-e)$ be a connected graph of order
$\displaystyle n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle
2\rho+\partial_{1}^{Q}\geq\frac{3n-2+\sqrt{(n-2)^{2}+32}}{2}+\frac{2n}{n-1},$

with equality holding if and only if $\displaystyle G\cong K_{n}-2e,$ where
$\displaystyle 2e$ are two matching edges.

######  Theorem 4.40 ([33]).

Let $\displaystyle G$ be a connected graph of order $\displaystyle n\geq 4$
with remoteness $\displaystyle\rho.$ Then

$\displaystyle\partial_{1}^{Q}-2\rho\geq 2n-4,$

with equality holding if and only if $\displaystyle G\cong K_{n}.$

######  Theorem 4.41 ([33]).

Let $\displaystyle G\ncong K_{n}$ be a connected graph of order $\displaystyle
n\geq 4$ with remoteness $\displaystyle\rho$. Then

$\displaystyle\partial_{1}^{Q}-2\rho\geq\frac{3n-2+\sqrt{(n-2)^{2}+16}}{2}-\frac{2n}{n-1},$

with equality holding if and only if $\displaystyle G\cong K_{n}-e$.

Mojallal and Hansen [39] obtained relation between proximity and the third
largest distance eigenvalue of a graph, some results earlier conjuctured in
[9].

Figure 10: The tree $\displaystyle T_{1}$ and the graph $\displaystyle G_{1}$

######  Lemma 4.42 ([39]).

Let $\displaystyle T_{1}$ be the tree of order $\displaystyle n$ given in Fig
10. Then

$\displaystyle\pi(T_{1})+\partial_{3}(T_{1})>0.$

######  Lemma 4.43 ([39]).

Let $\displaystyle G_{1}$ be the graph of order $\displaystyle n$ given in Fig
10. Then

$\displaystyle\pi((G_{1}))+\partial_{3}(G_{1})>0.$

######  Lemma 4.44 ([39]).

Let $\displaystyle G$ be a graph of order $\displaystyle n$ with the diameter
$\displaystyle D=3$ and let $\displaystyle i_{1}$ and $\displaystyle i_{4}$ be
two vertices of $\displaystyle G$ with distance $\displaystyle 3$. If
$\displaystyle d_{G}(i_{1})\geq 2$ and $\displaystyle d_{G}(i_{4})\geq 2.$
Then

$\displaystyle\pi+\partial_{3}>0.$

######  Lemma 4.45 ([39]).

Let $\displaystyle G$ be a graph of order $\displaystyle n$ with the diameter
$\displaystyle D=3$ and let $\displaystyle i_{1}$ and $\displaystyle i_{4}$ be
two vertices of $\displaystyle G$ with distance $\displaystyle 3$. If
$\displaystyle d_{G}(i_{1})=1$ or $\displaystyle d_{G}(i_{4})=1.$ Then

$\displaystyle\pi+\partial_{3}>0.$

######  Theorem 4.46 ([39]).

Let $\displaystyle G$ be a graph with the diameter $\displaystyle D\geq 3$,
proximity $\displaystyle\pi(G)$ and third largest distance eigenvalue
$\displaystyle\partial_{3}.$ Then

$\displaystyle\pi+\partial_{3}>0.$

######  Corollary 4.47 ([39]).

Let $\displaystyle G$ be a graph with the diameter $\displaystyle D\geq 3,$
and the third largest distance eigenvalue $\displaystyle\partial_{3}.$ Then

$\displaystyle\displaystyle(i)~{}D+\partial_{3}>0\quad(ii)~{}\rho+\partial_{3}>0\quad(iii)~{}\overline{\ell}+\partial_{3}>0\quad(iv)~{}ecc+\partial_{3}>0\quad(v)~{}r+\partial_{3}>0.$

##  5 Conclusion

The survey collects all the results related to proximity $\displaystyle\pi$
and remoteness $\displaystyle\rho$ published in different journals from 2006
to September 2023.

## Data Availability

There is no data associated with this article.

## Conflict of interest

The authors declare that they have no competing interests.

## References

  * [1] M. Aouchiche, Comparaison Automatisée d’Invariants en Théorie des Graphes. PhD Thesis, École Polytechnique de Montréal, February 2006.
  * [2] M. Aouchiche, G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants MATCH Commun. Math. Comput. Chem. 58 (2007) 365–384.
  * [3] M. Aouchiche, G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs. 8. Variations on Graffiti 105. Congr. Numer. 148 (2001) 129–144.
  * [4] M. Aouchiche and P. Hansen, Proximity and remoteness in graphs: results and conjectures. Networks 58 (2011) 95–102.
  * [5] M. Aouchiche and P. Hansen, Nordhaus-Gaddum Relations for Proximity and Remoteness in Graphs. Comput. Math. Appl. 59 (2010) 2827–2835.
  * [6] M. Aouchiche and P. Hansen, On a conjecture about the Szeged index. European J. Combin. 31 (2010) 1662–1666.
  * [7] M. Aouchiche and P. Hansen, A survey of Nordhaus–Gaddum type relations. Discrete Appl. Math. 161 (2013) 466–546.
  * [8] M. Aouchiche and P. Hansen, Distance spectra of graphs: a survey. To appear in Linear Algebra Appl. 2014.
  * [9] M. Aouchiche and P. Hansen, Proximity, remoteness and distance eigenvalues of a graph. Discrete Appl. Math. 213 (2016) 17–25.
  * [10] M. Aouchiche and P. Hansen, Proximity, remoteness and girth in graphs. Discrete Appl. Math. 222 (2017) 31–39.
  * [11] C. Barnhart and G. Laporte, (eds), ”Transportation”, Handbooks in Operations Research and Management Science. Volume 14, Elsevier, Amsterdam, 2007.
  * [12] G. S. Bloom, J. W. Kennedy and L. V. Quintas, Distance degree regular graphs. In Proc. of the Fourth International Conference on the Theory and Applications of Graphs. Western Michigan University, Kalamazoo, MI, May 6–9, 1980.
  * [13] F. Buckley and F. Harary, Distance in graphs. Addison-Wesley Publishing Company, Redwood, 1990.
  * [14] S. Cabello and P. Lukšić, The complexity of obtaining a distance-balanced graph. Electron. J. Combin. 18, 1 (2011) Paper 49.
  * [15] F. Chung, The average distance and the independence number, J. Graph Theory 12 (1988), 229–235.
  * [16] E. Czabarka, P. Dankelmann, T. Olsen and L. A. Székely, Proximity in triangulations and quadrangulations arxiv:2001.09012 (2020)
  * [17] E. Czabarka, P. Dankelmann, T. Olsen and L. A. Székely, Wiener index and remoteness in triangulations and quadrangulations Discrete Math. Theor. Comp. Sci. 23,1 (2021), $\displaystyle\\#3$
  * [18] P. Dankelmann, Proximity, remoteness and minimuim degree Discrete Appl. Math. 184 (2015) 223–228.
  * [19] P. Dankelmann, New bounds on proximity and remoteness in graphs Comm. Combin. Optm. 1, 1 (2016) 29–41.
  * [20] P. Dankelmann, E. Jonck and S. Mafunda, Proximity and remoteness in triangle-free and $\displaystyle C_{4}$-free graphs in terms of order and minimum degree Discrete Math. 344 (2021) 112513.
  * [21] P. Dankelmann and S. Mafunda, On the difference between proximity and other distance parameters in triangle-free graphs and $\displaystyle C_{4}$-free graphs Discrete Appl. Math. 321 (2022) 295–307.
  * [22] P. Dankelmann, S. Mafunda and S. Mallu, Proximity, remoteness and maximum degree in graphs Discrete Math. Theor. Comp. Sci. 24(2) (2022) https://doi.org/10.46298/dmtcs.9432.
  * [23] S. Fajtlowicz, On conjectures of Graffiti, II. Congr. Numer. 60 (1987) 187–197.
  * [24] R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs. Czechoslovak Math. J. 26(101) (1976) 283–296.
  * [25] G. Ghiani, G. Laporte and R. Musmanno, Introduction to Logistics Systems Planning and Control. Wiley, Chichester, 2004
  * [26] A. J. Goldman, Minimax location of a facility in a network. Transportation Sci. 6 (1972) 407–418.
  * [27] S. L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Res. 12 (1964) 450–459.
  * [28] K. Handa, Bipartite graphs with balanced $\displaystyle(a,b)$–partitions. Ars Combin. 51 (1999) 113–119.
  * [29] F. Harary, Status and contrastatus. Sociometry, 22 (1959) 23–43.
  * [30] H. Hua and K. Ch. Das, Proof of conjectures on remoteness and proximity in graphs. Discrete Appl. Math. 171 (2014) 72–80.
  * [31] H. Hua, Y. Chen and K. Ch. Das, Proof of conjectures on remoteness and proximity in graphs. Discrete Appl. Math. 187 (2015) 103–110.
  * [32] A. Ilić, S. Klavžar, M. Milanović, On distance-balanced graphs. Euro J. Combin. 31 (2010) 733–737.
  * [33] H. Jia and H. Song, Remoteness and distance, distance (signless) Laplacian eigenvalues of a graph J. Ineq. Appl. (2018) 69.
  * [34] J. Jerebic, S. Klavžar, D. F. Rall, Distance-balanced graphs. Annals of Combinatorics 12 (2008) 71–79.
  * [35] C. Jordan, Sur les assemblages de lignes. J. Reine Angew. Math. 70 (1869) 185–190.
  * [36] D. J. Klein, Centrality measure in graphs. J Math. Chem. 47 (2010) 1209–1223.
  * [37] H. Lin, K. C. Das and B. Wu Remoteness and distance eigenvalues of a graph. Discrete Appl. Math. 215 (2016) 218–224.
  * [38] S. A. Mallu, Proximity and Remoteness In Graphs, University of Johannesburg (South Africa), 2022, available at https://hdl.handle.net/10210/498379.
  * [39] S. A. Mojallal and P. Hansen, A relation between proximity and the third largest distance eigenvalues of a graph. Discrete Appl. Math. 293 (2021) 50–58.
  * [40] B. Ma, B. Wu and W. Zhang, Proximity and average eccentricity of a graph. Inf. Process. Lett. 112 (2012) 392–395.
  * [41] E. A. Nordhaus and J. W. Gaddum, On Complementary Graphs. Amer. Math. Monthly 63 (1956) 175–177.
  * [42] C. Payen and N. H. Xoung, Domination balanced Graphs. J. Graph. Theory 6 (1982) 23–32.
  * [43] L. Pei, About AutoGraphiX conjecture on domination number and remoteness of graphs Math. 10(19) (2022) 3706.
  * [44] L. Pei, X. Pan, K. Wang, J. Tian and G. peng, On AutoGraphix conjectures regarding domination number and average eccentrity Filomat 3 (2019) 699–710.
  * [45] L. Pei, X. Pan, K. Wang and J. Tian, Proofs of the AutoGraphix conjectures on the domination number, average eccentrity and proximity Discrete Appl. Math. 289 (2021) 292–301.
  * [46] O. E. Polansky and D. Bonchev, The minimum distance number of trees. MATCH Commun. Math. Comput. Chem. 21 (1986) 341–344.
  * [47] M. Randić, Characterizations of atoms, molecules and classes of molecules based on paths enumerations. Proc. of Bremen Konferenz zur Chemie Univ. Bremen, Bremen, 1978, Part 11, Match No. 7 (1979) 5–64.
  * [48] G. Sabidussi, The centrality index of a graph. Psychometrika, 31 (1966) 581–603.
  * [49] J. Sedlar, D Vukčević, M. Aouchiche, P. Hansen, Variable Neighborhood Search for Extremal Graphs: 25. Products of Connectivity and Distance Measure. Graph Theory Notes of New York 55 (2008) 6–13.
  * [50] J. Sedlar, Remoteness, proximity and few other distance invariants in graphs. Filomat 27 (2013) 1425–1435.
  * [51] P.J. Slater, Counterexamples to Randić’s conjecture on distance degree sequences for trees. J. Graph Theory, 6 (1982) 89–92.
  * [52] S. Smart and P. Slater, Center, median, and centroid subgraphs. Networks 34 (1999) 303–311.
  * [53] L. Soltés,  Transmission in Graphs : a Bound and Vertex Removing. Math. Slovaca 41 (1991) 11–16.
  * [54] M. Tavakoli, F. Rahbarnia, A. R. Ashrafi, Further results on distance-balanced graphs. UPB Scientific Bulletin, Series A: Applied Mathematics and Physics 75 (2013) 77–84.
  * [55] H. Wiener, Structural determination of the Paraffin Boiling Points. J. Amer. Chem. Soc. 69 (1947) 17–20.
  * [56] B. Wu and W. Zhang, Average distance, radius and remoteness of a graph. ARS MATHEMATICA CONTEMPORANEA 7 (2014) 441–452.
  * [57] B. Zelinka, Medians and peripherians of trees. Archivum Mathematicum 4 (1968) 87–95.