Length of the Longest Path and Diameter in Orientations of Graphs
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 &lambda; be the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether &lambda; 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.
Cite this paper: Zhou, B. (2017) Length of the Longest Path and Diameter in Orientations of Graphs. Open Journal of Discrete Mathematics, 7, 65-70. doi: 10.4236/ojdm.2017.72007.
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.

Top