Abstract
In this thesis, we investigate bounds on two prominent distance measures in graph
theory: proximity and remoteness. If G is a finite, connected graph of order n, then
the proximity π(G) and the remoteness ρ(G) are the minimum and maximum average
distances of a vertex in G among all vertices, respectively, where the distance dG(u,v)
between two vertices u and v of G is the usual shortest-path distance, and the average
distance of a vertex u is given by 1
n−1 Σv∈V(G) dG(u,v).
Our study focuses on establishing new upper bounds on these distance-based parameters
for various classes of graphs, in particular planar graphs and Eulerian digraphs.
For general graphs, we derive sharp upper bounds on the remoteness of a graph
in terms of its order, connectivity, and size. We also obtain corresponding bounds for
2-edge-connected and 3-edge-connected graphs, as well as bounds in terms of order
and size for triangle-free graphs. Furthermore, we extend our investigation to strong
digraphs and show that the upper bounds on remoteness, given order, size, and connectivity
constraints, can be improved and generalized to a larger class of digraphs,
including all Eulerian digraphs.
For planar graphs, we derive sharp upper bound on the proximity and remoteness of
a maximal outerplanar graph in terms of its order. We also establish an upper bound on
the proximity of 2-connected outerplane graphs in terms of order and maximum face
length. Moreover, we show that the well-known upper bound ⌊n
4⌋+1 on the radius of
maximal outerplanar graphs extends to all 2-connected outerplane graphs of order n
whose maximum face length does not exceed n+2
4 .
Finally, we prove several results on differences between distance parameters. For
maximal planar graphs with given connectivity constraints, we show that the difference
between radius and proximity is about n
12 , which can be further improved to n
16 and n
20
if the graph is 4-connected or 5-connected, respectively. Similar improvements are
obtained for quadrangulations and maximal outerplanar graphs. For the difference
between remoteness and proximity, and between diameter and proximity, we show
that the general bounds are approximately n
4κ and 3n
4κ , where κ ∈ {2,3,4,5}.