Length of the Longest Path and Diameter in Orientations of Graphs ()
1. Introduction
Let
be an undirected graph. An orientation of
is a directed graph
obtained by assigning a direction to every edge in
. A classical result of Gallai, Roy and Vitaver states that in any orientation of a graph
, the number of vertices in the longest directed path is at least the chromatic number of
. Lin [1] asked whether every graph
can be oriented such that the number of vertices in its longest directed path is
where
is any number between the chromatic number of
and the number of vertices in the longest undirected path in
. Let
be a parameter of oriented graphs. We define
and
We say the parameter
has the interval property if for every graph
and every
such that
, there is an orientation
of
such that
. For a graph
is the length of the longest path in
Note that
= (the number of vertices in the longest path in
) − 1. Similarly,
is the length of the longest directed path in a directed graph
. Lin’s question can be phrased as whether
has the interval property. In Section 2, we answer Lin’s question in the affirmative by describing a method to construct an orientation
of any given graph
with
where
is an integer between
and
. In Section 3, we show that the diameter of directed graphs does not have the interval property. We construct an infinite family of graphs and prove that it is not possible to orient these graphs so that their diameters take all the values between the minimum and the maximum diameters.
2. Longest Path in Oriented Graphs
Theorem 1 (Gallai [2] , Roy [3] , Vitaver [4] , also in the book [5] ) If
is an orientation of
, then
Furthermore, equality holds for some orientation of
.
Theorem 1 provides a lower bound of
for all orientations
of
and
is a trivial upper bound of
. The question of whether the parameter
has the interval property is the same as the question of whether
can take every value in the interval
. This is a question raised in [1] by C. Lin. In this section we describe a method to construct an orientation for each such integer
thus giving an affirmative answer to the question of Lin and proving that the parameter
has the interval property.
Theorem 2 For a graph
with
and
and an integer
such that
, there always exists an orientation
of
such that
.
Proof. Suppose that
is a path of
vertices in
. Let
be a
-coloring of
such that the color classes are
. We may permute the colors so that
. We define a
-coloring of
recursively for
. In the
-th coloring, the color classes will be labeled
. For
and
we let
. For
, we define
for
and
. What this means is that in the
-th step, we take the vertex
in the path
and color it with a new color while keeping the colors of all the other vertices unchanged. This is a proper coloring of
. Let
be the orientation of
induced by this
-coloring. That is, in
, the edge
is directed from
to
if
,
and
.
It is easy to see that
and according to Theorem 1,
. Thus we have
. On the other hand,
is a directed path in
. Therefore
. The key idea of the proof of the theorem is the following observation: When the orientation changes from
to
, the length of the longest directed path will increase by at most one.
Claim:
for all
.
Let
be a longest directed path in
. We prove this claim in two cases.
Case 1:
does not contain the vertex
. Since all the edges that are not incident with
are directed the same way in
as in
,
is also a directed path in
. We have
.
Case 2:
contains the vertex
. Since all the edges that are incident to
are directed towards
in
,
must be the last vertex in
. Therefore
is a directed path in
. We have
. This completes the proof of the claim.
To prove the main theorem by contradiction, we assume that there is a value
between
and
such that for all
,
Let
Since
and
, such
exists and is strictly less than
. We have
and
, therefore
This contradicts to the claim.
An efficient algorithm can easily be derived to find the orientation in Theorem 2 when a longest path and a
-coloring of
is given, even though finding a longest path is a well known NP-complete problem ( [6] , Problem ND29).
3. Diameter of Oriented Graphs
The distance between two vertices
in a graph
, denoted
, is the length of a shortest path between
and
. The diameter of
is the largest distance over all the pairs of vertices in
, denoted
. That is,
Similarly, in a directed graph
,
is the length of a shortest directed path from
to
and
Distances and diameters of oriented graphs and their applications have been studied extensively (see e.g. [7] - [13] ). A directed graph
has a finite diameter if and only if
is strongly connected. A well known theorem of Robbins [14] states that a graph
has a strongly connected orientation if and only if
is 2-connected. For this reason, we will only consider 2-connected graphs and their strongly connected orientations in this section. Another result we will use in this section is a theorem of Gutin [12] .
Theorem 3 Let
be a 2-connected graph. The largest diameter of all strongly connected orientations of
is
.
We define an infinite family of graphs
for
Definition 4 Let the vertex set of
be
, and the edges be:
and
. (See Figure 1).
It is easy to see that
and
Lemma 5 There is an orientation
of
such that
.
Proof. Let
be the orientation of
obtained by using the pairs in Definition 4 as ordered pairs. (See Figure 2). We show that for every vertex
and any other vertex
, there is a directed
-path of length at most
. By symmetry, we only need to consider two cases that either
or
,
.
Case 1.
. Let
. If
, there is a
-path of length at most
:
. If
, there is a
-path of length at most
:
. If
, there is a
-path of length at most
:
.
Case 2.
and
. Let
. We consider the following four subcases.
Case 2.1
.
is a
-path of length at most
.
Case 2.2
.
is a
path of length at most
since this path at at most
edges from
to
and at most
edges from
to
.
Case 2.3
.
is a
path of length at most
since this path has at at most
edges from
to
, one edge from
to
and at most
edges from
to
.
Case 2.4
.
is a
path of length at most
since this path has at most
edges from
to
, one edge from
to
one edge from
to
, and at most
edges from
to
.
Combining all these cases, we see that
for all vertices
in
and
Therefore
.
Lemma 6 There are at most
different orientations of
with finite diameters.
Proof. The vertices
all have degree two. For the orientation to be strongly connected, the path
must be a directed path, either from
to
or from
to
. Similarly, the paths
and
have to be directed paths too. There are two possible directions for each of these three paths and two possible directions for each of the edges
and
. Therefore, there are at most
orientations that are strongly connected thus with finite diameters.
By symmetry, many of the
orientations have the same diameter. The number of distinct values of the diameters of orientations of
is much less than 64. Using Gutin’s theorem ( [12] ), we find that the largest diameter among all orientations of
is
. By Lemma 5, the smallest diameter is at most
. There are
values in the interval
. Therefore, we have our main result of this section.
Theorem 7 Let
be an integer greater than 64. It is not possible to orient the graph
such that the diameter of the orientations take all the values between the smallest diameter and the largest diameter.
Corollary 8 The diameter of oriented graphs does not have the interval property.
Acknowledgements
The author wish to thank two anonymous referees for their helpful comments.