Length of the Longest Path and Diameter in Orientations of Graphs

Bing Zhou

Department of Mathematics, Trent University, Peterborough, ON K9J 7B8, Canada.

DOI: 10.4236/ojdm.2017.72007                

Abstract

We say that a parameter p of directed graphs has the interval property if for every graph G and orientations of G, p can take every value between its minimum and maximum values. Let λ be the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λ has the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.

Keywords

Directed Graphs, Graph Orientation, Interval Property, Longest Path, Path Length, Diameter

1. Introduction

Let $G$ be an undirected graph. An orientation of $G$ is a directed graph $D$ obtained by assigning a direction to every edge in $G$ . A classical result of Gallai, Roy and Vitaver states that in any orientation of a graph $G$ , the number of vertices in the longest directed path is at least the chromatic number of $G$ . Lin [1] asked whether every graph $G$ can be oriented such that the number of vertices in its longest directed path is $k$ where $k$ is any number between the chromatic number of $G$ and the number of vertices in the longest undirected path in $G$ . Let $p$ be a parameter of oriented graphs. We define

$p_{\min }\left(G\right)=\min \left\{p\left(D\right)\mathrm{<mo>\; :\; </mo>}D\text{isanorientationof}G\right\}$

and

$p_{\max }\left(G\right)=\max \left\{p\left(D\right)\mathrm{<mo>\; :\; </mo>}D\text{isanorientationof}G\right\}$

We say the parameter $p$ has the interval property if for every graph $G$ and every $k$ such that $p_{min}\left(G\right)\le k\le p_{max}\left(G\right)$ , there is an orientation $D$ of $G$ such that $p\left(D\right)=k$ . For a graph $G\mathrm{,}$ $\lambda \left(G\right)$ is the length of the longest path in $G\mathrm{.}$ Note that $\lambda \left(G\right)$ = (the number of vertices in the longest path in $G$ ) − 1. Similarly, $\lambda \left(D\right)$ is the length of the longest directed path in a directed graph $D$ . Lin’s question can be phrased as whether $\lambda$ has the interval property. In Section 2, we answer Lin’s question in the affirmative by describing a method to construct an orientation $D$ of any given graph $G$ with $\lambda \left(D\right)=k$ where $k$ is an integer between $\chi \left(G\right)-1$ and $\lambda \left(G\right)$ . 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 $D$ is an orientation of $G$ , then $\chi \left(G\right)\le \lambda \left(D\right)+1.$ Furthermore, equality holds for some orientation of $G$ .

Theorem 1 provides a lower bound of $\lambda \left(D\right)$ for all orientations $D$ of $G\mathrm{,}$ and $\lambda \left(G\right)$ is a trivial upper bound of $\lambda \left(D\right)$ . The question of whether the parameter $\lambda$ has the interval property is the same as the question of whether $\lambda \left(D\right)$ can take every value in the interval $\left[\chi \left(G\right)-\mathrm{1,}\lambda \left(G\right)\right]$ . 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 $k\mathrm{,}$ thus giving an affirmative answer to the question of Lin and proving that the parameter $\lambda$ has the interval property.

Theorem 2 For a graph $G$ with $\chi \left(G\right)=t$ and $\lambda \left(G\right)=l$ and an integer $k$ such that $t-1\le k\le l$ , there always exists an orientation $D$ of $G$ such that $\lambda \left(D\right)=k$ .

Proof. Suppose that $P=v_1{v}_2\cdots v_{l+1}$ is a path of $l+1$ vertices in $G$ . Let $C$ be a $t$ -coloring of $G$ such that the color classes are $V_1\mathrm{,}{V}_2\mathrm{,}\cdots \mathrm{,}{V}_t$ . We may permute the colors so that $v_1\in V_t$ . We define a $\left(t+m-1\right)$ -coloring of $G$ recursively for $m=1,2,\cdots ,l$ . In the $m$ -th coloring, the color classes will be labeled $V_1^m,V_2^m,\cdots ,V_{t+m-1}^m$ . For $m=1$ and $i=1,2,\cdots ,t$ we let $V_i^1=V_i$ . For

$m=2,3,\cdots ,l$ , we define $V_i^m=V_i^{m-1}\backslash \left\{v_m\right\}$ for $i=1,2,\cdots ,t+m-2$ and

$V_{t+m-1}^m=\left\{v_m\right\}$ . What this means is that in the $m$ -th step, we take the vertex $v_m$ in the path $P$ and color it with a new color while keeping the colors of all the other vertices unchanged. This is a proper coloring of $G$ . Let $D_m$ be the orientation of $G$ induced by this $\left(t+m-1\right)$ -coloring. That is, in $D_m$ , the edge $uv$ is directed from $u$ to $v$ if $u\in V_i^m$ , $v\in V_j^m$ and $i<j$ .

It is easy to see that $\lambda \left(D_1\right)\le t-1$ and according to Theorem 1,

$\lambda \left(D_1\right)\ge t-1$ . Thus we have $\lambda \left(D_1\right)=t-1$ . On the other hand, $P$ is a directed path in $D_l$ . Therefore $\lambda \left(D_l\right)=l$ . The key idea of the proof of the theorem is the following observation: When the orientation changes from $D_i$ to $D_{i+1}$ , the length of the longest directed path will increase by at most one.

Claim: $\lambda \left(D_m\right)\le \lambda \left(D_{m-1}\right)+1$ for all $m=2,\cdots ,l$ .

Let $Q$ be a longest directed path in $D_m$ . We prove this claim in two cases.

Case 1: $Q$ does not contain the vertex $v_m$ . Since all the edges that are not incident with $v_m$ are directed the same way in $D_m$ as in $D_{m-1}$ , $Q$ is also a directed path in $D_{m-1}$ . We have $\lambda \left(D_m\right)\le \lambda \left(D_{m-1}\right)$ .

Case 2: $Q$ contains the vertex $v_m$ . Since all the edges that are incident to $v_m$ are directed towards $v_m$ in $D_m$ , $v_m$ must be the last vertex in $Q$ . Therefore $Q\backslash \left\{v_m\right\}$ is a directed path in $D_{m-1}$ . We have $\lambda \left(D_{m-1}\right)\ge \lambda \left(D_m\right)-1$ . This completes the proof of the claim.

To prove the main theorem by contradiction, we assume that there is a value $k$ between $t$ and $l$ such that for all $i$ , $\lambda \left(D_i\right)\ne k\mathrm{.}$ Let

$i^{\ast }=\max \left\{i:\lambda \left(D_i\right)<k\right\}.$

Since $\lambda \left(D_1\right)=t$ and $\lambda \left(D_l\right)=l$ , such $i^{\ast }$ exists and is strictly less than $l$ . We have $\lambda \left(D_{i^{*}}\right)<k$ and $\lambda \left(D_{i^{\ast }+1}\right)\mathrm{<mo>\; >\; </mo>}k$ , therefore $\lambda \left(D_{i^{\ast }+1}\right)\mathrm{<mo>\; >\; </mo>}\lambda \left(D_{i^{\ast }}\right)+1.$ 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 $t$ -coloring of $G$ 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 $u\mathrm{,}v$ in a graph $G$ , denoted $\mathrm{dist}\left(u,v\right)$ , is the length of a shortest path between $u$ and $v$ . The diameter of $G$ is the largest distance over all the pairs of vertices in $G$ , denoted $\text{diam}\left(G\right)$ . That is,

$\text{diam}\left(G\right)=\max \left\{\text{dist}\left(u,v\right):u,v\in V\left(G\right)\right\}.$

Similarly, in a directed graph $D$ , $\text{dist}\left(u\mathrm{,}v\right)$ is the length of a shortest directed path from $u$ to $v$ and

$\text{diam}\left(D\right)=\max \left\{dist\left(u,v\right):u,v\in V\left(D\right)\right\}\text{.}$

Distances and diameters of oriented graphs and their applications have been studied extensively (see e.g. [7] - [13] ). A directed graph $D$ has a finite diameter if and only if $D$ is strongly connected. A well known theorem of Robbins [14] states that a graph $G$ has a strongly connected orientation if and only if $G$ 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 $G$ be a 2-connected graph. The largest diameter of all strongly connected orientations of $G$ is $\lambda \left(G\right)$ .

We define an infinite family of graphs $G_{3k}$ for $k=3,4,\cdots$

Definition 4 Let the vertex set of $G_{3k}$ be $\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_{3k}\right\}$ , and the edges be: $\left(v_i,v_{i+1}\right):i=1,2,\cdots ,3k-1;$ and $\left(v_{3k}\mathrm{,}{v}_1\right)\mathrm{,}$ $\left(v_1\mathrm{,}{v}_{k+1}\right)\mathrm{,}$ $\left(v_{k+1}\mathrm{,}{v}_{2k+1}\right)\mathrm{,}$ $\left(v_{2k+1}\mathrm{,}{v}_1\right)$ . (See Figure 1).

It is easy to see that $\lambda \left(G_{3k}\right)=3k-1$ and $\text{diam}\left(G_{3k}\right)\le k+1.$

Lemma 5 There is an orientation $D_{3k}$ of $G_{3k}$ such that

$\text{diam}\left(D_{3k}\right)\mathrm{<mo>\; =\; </mo>2}k-1$ .

Proof. Let $D_{3k}$ be the orientation of $G_{3k}$ obtained by using the pairs in Definition 4 as ordered pairs. (See Figure 2). We show that for every vertex $u$ and any other vertex $v$ , there is a directed $uv$ -path of length at most $2k-1$ . By symmetry, we only need to consider two cases that either $u=v_1$ or $u=v_i$ , $1<i\le k$ .

Case 1. $u=v_1$ . Let $v=v_j$ . If $j\in \left[\mathrm{2,}k\right]$ , there is a $uv$ -path of length at most $k-1$ : $v_1{v}_2\cdots v_j$ . If $j\in \left[k+\mathrm{1,2}k\right]$ , there is a $uv$ -path of length at most $k$ : $v_1{v}_{k+1}\cdots v_j$ . If $j\in \left[2k+\mathrm{1,3}k\right]$ , there is a $uv$ -path of length at most $k+1$ :

$v_1{v}_{k+1}{v}_{2k+1}\cdots v_j$ .

Case 2. $u=v_i$ and $i\in \left[\mathrm{2,}k\right]$ . Let $v=v_j$ . We consider the following four subcases.

Case 2.1 $j\in \left[i\mathrm{,}k\right]$ . $v_i{v}_{i+1}\cdots v_j$ is a $uv$ -path of length at most $k-i\le k-2$ .

Case 2.2 $j\in \left[k+\mathrm{1,2}k\right]$ . $v_i{v}_{i+1}\cdots v_k{v}_{k+1}\cdots v_j$ is a $uv$ path of length at most $2k-4$ since this path at at most $k-2$ edges from $v_i$ to $v_{k+1}$ and at most $k-2$ edges from $v_{k+1}$ to $v_j$ .

Case 2.3 $j\in \left[2k+\mathrm{1,3}k\right]$ . $v_i{v}_{i+1}\cdots v_k{v}_{k+1}{v}_{2k+1}\cdots v_j$ is a $uv$ path of length at most $2k-1$ since this path has at at most $k-1$ edges from $v_i$ to $v_{k+1}$ , one edge from $v_{k+1}$ to $v_{2k+1}$ and at most $k-1$ edges from $v_{k+1}$ to $v_j$ .

Case 2.4 $j\in \left[1,i-1\right]$ . $v_i{v}_{i+1}\cdots v_k{v}_{k+1}{v}_{2k+1}{v}_1\cdots v_j$ is a $uv$ path of length at most $k+1$ since this path has at most $k-i$ edges from $v_i$ to $v_{k+1}$ , one edge from $v_{k+1}$ to $v_{2k+1}\mathrm{,}$ one edge from $v_{2k+1}$ to $v_1$ , and at most $i-1$ edges from $v_1$ to $v_j$ .

Combining all these cases, we see that $\text{dist}\left(u,v\right)\le 2k-1$ for all vertices $u\mathrm{,}v$ in $G_{3k}$ and $\text{dist}\left(v_2,v_{3k}\right)=2k-1.$ Therefore $\text{diam}\left(D_{3k}\right)=2k-1$ .

Figure 1. G₃k.

Figure 2. D₃k.

Lemma 6 There are at most $2^6$ different orientations of $G_{3k}$ with finite diameters.

Proof. The vertices $v_2\mathrm{,}{v}_3\mathrm{,}\cdots \mathrm{,}{v}_k$ all have degree two. For the orientation to be strongly connected, the path $v_1{v}_2\cdots v_{k+1}$ must be a directed path, either from $v_1$ to $v_{k+1}$ or from $v_{k+1}$ to $v_1$ . Similarly, the paths $v_{k+1}{v}_{k+2}\cdots v_{2k+1}$ and

$v_{2k+1}{v}_{2k+2}\cdots v_1$ 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 $\left(v_1\mathrm{,}{v}_{k+1}\right)\mathrm{,}$ $\left(v_{k+1}\mathrm{,}{v}_{2k+1}\right)\mathrm{,}$ and $\left(v_{2k+1}\mathrm{,}{v}_1\right)$ . Therefore, there are at most $2^6$ orientations that are strongly connected thus with finite diameters.

By symmetry, many of the $2^6=64$ orientations have the same diameter. The number of distinct values of the diameters of orientations of $G_{3k}$ is much less than 64. Using Gutin’s theorem ( [12] ), we find that the largest diameter among all orientations of $G_{3k}$ is $3k-1$ . By Lemma 5, the smallest diameter is at most $2k-1$ . There are $k$ values in the interval $\left[2k-\mathrm{1,3}k-1\right]$ . Therefore, we have our main result of this section.

Theorem 7 Let $k$ be an integer greater than 64. It is not possible to orient the graph $G_{3k}$ 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.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Lin, C. (2007) Simple Proofs of Results on Paths Representing All Colors in Proper Vertex-Colorings. Graphs and Combinatorics, 23, 201-203. https://doi.org/10.1007/s00373-007-0694-3
[2]	Gallai, T. (1968) On Directed Paths and Circuits. In: Erdös, P. and Katona, G., Eds., Theory of Graphs, Academic Press, New York. 115-118.
[3]	Roy, B. (1967) Nombre chromatique et plus longs chemins d'un graph. Rev. AFIRO, 1, 127-132.
[4]	Vitaver, L.M. (1962) Determination of Minimal Coloring of Vertices of a Graph by Means of Boolean Powers of the Incidence Matrix (Russian). Doklady Akademii Nauk SSSR, 147, 758-759.
[5]	West, D.B. (1996) Introduction to Graph Theory. Prentice-Hall, New Jersey.
[6]	Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability. A Guide to the Theory of NP-Completeness.W.H., Freeman and Company, New York.
[7]	Chvatal, V. and Thomassen, C. (1978) Distances in Orientations of Graphs. Journal of Combinatorial Theory, Series B, 24, 61-75.
[8]	Eggemann, N. and Noble, S.D. (2012) The Complexity of Two Graph Orientation Problems. Discrete Applied Mathematics, 160, 513-517.
[9]	Figueiredo, R.M.V., Barbosa, V.C., Maculan, N. and De Souza, C.C. (2008) A Cyclic Orientations with Path Constraints. RAIRO—Operations Research, 42, 455-467.
[10]	Gendron, B., Hertz, A. and St-Louis, P. (2006) On Edge Orienting Methods for Graph Coloring. Journal of Combinatorial Optimization, 13, 163-178.
[11]	Gendron, B., Hertz, A. and St-Louis, P. (2008) On a Generalization of the Gallai-Roy-Vitaver Theorem to the Bandwidth Coloring Problem. Operations Research Letters, 36, 345-350.
[12]	Gutin, G. (1994) Minimizing and Maximizing the Diameter in Orientations of Graphs. Graphs and Combinatorics, 10, 225-230.
[13]	Kwok, P.K., Liu, Q. and West, D.B. (2010) Oriented Diameter of Graphs with Diameter 3. Journal of Combinatorial Theory, Series B, 100, 265-274.
[14]	Robbins, H.E. (1929) Theorem on Graphs, with an Application to a Problem of Traffic Control. The American Mathematical Monthly, 46, 281-283.