Abstract
A (di)graph G = (V (G),E(G)) is a collection of vertices and edges. The distance between two vertices in G
is defined as the length of a shortest path between them. While in graphs a distance measure is a metric, the
same does not hold true for digraphs since the symmetry property does not always hold. The maximum of
all the distances between two vertices in a graph (or digraph) G is called the diameter of G and is denoted
by diam(G). An orientation of a graph G is a digraph obtained by assigning a direction to every edge of
G. One can think of it as “turning every street into a one-way street”. This might cause some distances to
increase, and this thesis is concerned with finding conditions under which this increase can be guaranteed
to be relatively small. A strong orientation is one in which one can travel between any two vertices in a
digraph. A bridge is an edge whose removal disconnects the graph, and if a graph does not contain a bridge,
it is said to be bridgeless. Strong orientations are known to exist only for bridgeless graphs and so only such
graphs are considered in this thesis. The smallest diameter of a strong orientation of G is called the oriented
diameter of a bridgeless graph G, which constitutes the primary focus of this thesis. It is computationally
difficult (NP-complete) to find the oriented diameter of a given graph, hence, bounds on it are of interest.
In Chapter 1 we introduce the focus of this thesis. In Chapter 2 we present the specific definitions and
terminology used in this study. Thereafter, Chapter 3 delves into a review of the existing literature, laying
the foundation for the investigation into the oriented diameter and its associated bounds. The subsequent
chapters focus on our main results.
A set S of vertices of a graph G is called a dominating set of G if every vertex in V (G) − S is adjacent
to some vertex of S. The domination number !(G) of a graph G is the minimum number of vertices in
a dominating set. Upper bounds on the oriented diameter in terms of the domination number have been
considered in the literature, but to date no sharp upper bound is known. In Chapter 4 we consider two wellstudied
variations of the domination number, namely the connected domination number and the d-distance
domination number. We obtain an upper bound on the oriented diameter in terms of the connected domination
number, and show this bound to be sharp. The connected domination number !c(G) is defined as
the minimum cardinality of a dominating set that induces a connected subgraph. For d 2 N, the d-distance
domination number of G, denoted by !d(G), is the minimum cardinality of a set S of vertices of G such that
every vertex of G is within distance d from some vertex of S. The connected d-distance domination number
!d
c (G) of G is the minimum cardinality of a set S of vertices of G such that S induces a connected graph in
G, and every vertex of G is within distance d of some vertex of S. In Chapter 4 we prove that the oriented
diameter of a bridgeless graph G is at most 2!c(G)+3 if !c(G) is even and 2!c(G)+2 if !c(G) is odd. As an
application of a generalisation of the above result on the connected domination number, we prove an upper
bound on the oriented diameter of the form (2d+1)(d+1)!d(G)+O(d). Furthermore, we construct bridgeless
graphs whose oriented diameter is at least (d + 1)2!d(G) + O(d), thus demonstrating that our above bound
is best possible apart from a factor of about 2. It presents a challenge to determine the exact value of the
coefficient of !d(G). Even for d = 1, from the results mentioned in the introduction, we know that the value
lies between 72
and 4.
In Chapter 5 we present relationships between the oriented diameter and the number of blocks and the
number of cut vertices in a bridgeless graph. A cut vertex of a graph G is a vertex whose removal, together
with any incident edges, disconnects the graph. A block of G is defined to be a maximal connected subgraph
of G that has no cut vertex. We show that every bridgeless graph of order n containing p blocks has an
iv
oriented diameter of at most n − bp
2 c. This bound is sharp for all n and p with p % 2. As a corollary, we
obtain a sharp upper bound on the oriented diameter in terms of order and number of cut vertices. We use
the techniques developed in this chapter to find sharp bounds on the oriented diameter of graphs belonging
to the class of block graphs (also called clique trees) in terms of their order. A graph G is a block graph if
every block of G is a complete graph. We show that the oriented diameter of a bridgeless block graph of
order n is bounded above by b3n
4 c if n is even and b3(n+1)
4 c if n is odd.
In Chapter 6 we investigate the oriented diameter of two graphs derived from other graphs, namely the
complement and the line graph. The complement of the graph G is a graph G on the same set of vertices of
G such that there is an edge between two vertices u and v in G if and only if there is no edge between u and
v in G. It is natural to expect that for large diameter of a graph, the oriented diameter of its complement
will be small. We quantify this in Section 6.1, where we obtain sharp bounds on the oriented diameter of the
complement of a graph G in terms of the diameter of G and the oriented diameter of G. As a corollary, we
obtain Nordhaus-Gaddum type results for the oriented diameter. For sufficiently large n, these bounds are
analogous to those in terms of the diameter of a graph, and are optimal. The line graph L(G) of a graph
G is the graph where the vertices of L(G) are the edges of G and two vertices of L(G) are adjacent if and
only if the corresponding edges of G are adjacent. It is well-known that the diameter of the line graph di↵ers
by at most one from the diameter of the graph. However, we prove that this is not true for the oriented
diameter. In Section 6.2 we prove that the oriented diameter of the line graph of a graph G cannot exceed
the oriented diameter of G by more than one, but that it is at least, approximately, the square root of the
oriented diameter of G. We show that both results, in some sense, are best possible.
We conclude this thesis by discussing our findings in Chapter 7 and exploring potential future research
endeavours in Chapter 8.