All Title Author
Keywords Abstract

Length of the Longest Path and Diameter in Orientations of Graphs

DOI: 10.4236/ojdm.2017.72007, PP. 65-70

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

Full-Text   Cite this paper   Add to My Lib


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.


[1]  Lin, C. (2007) Simple Proofs of Results on Paths Representing All Colors in Proper Vertex-Colorings. Graphs and Combinatorics, 23, 201-203.
[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.


comments powered by Disqus

Contact Us


微信:OALib Journal