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.
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.
