Length of the Longest Path and Diameter in Orientations of Graphs
, PP. 65-70 10.4236/ojdm.2017.72007
Keywords: Directed Graphs, Graph Orientation, Interval Property, Longest Path, Path Length, Diameter
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  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. 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.
comments powered by Disqus. comments powered by
Contact Us email@example.com