Research ArticleOpen AccessGoogle Scholar indexed
Length of the Longest Path and Diameter in Orientations of Graphs
Department of Mathematics, Trent University, Peterborough, ON K9J 7B8, Canada
- 1 Department of Mathematics, Trent University, Peterborough, ON K9J 7B8, Canada
Open Journal of Discrete Mathematics·Volume 07 (2017)·Pages 65–70·Published 17 April 2017·DOI10.4236/ojdm.2017.72007
Copy link · social · email
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.
KeywordsDirected GraphsGraph OrientationInterval PropertyLongest PathPath LengthDiameter
- 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
- 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.
- Roy, B. (1967) Nombre chromatique et plus longs chemins d'un graph. Rev. AFIRO, 1, 127-132.
- 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.
- West, D.B. (1996) Introduction to Graph Theory. Prentice-Hall, New Jersey.
- 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.
- Chvatal, V. and Thomassen, C. (1978) Distances in Orientations of Graphs. Journal of Combinatorial Theory, Series B, 24, 61-75.
- Eggemann, N. and Noble, S.D. (2012) The Complexity of Two Graph Orientation Problems. Discrete Applied Mathematics, 160, 513-517.
- 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.
- Gendron, B., Hertz, A. and St-Louis, P. (2006) On Edge Orienting Methods for Graph Coloring. Journal of Combinatorial Optimization, 13, 163-178.
- 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.
- Gutin, G. (1994) Minimizing and Maximizing the Diameter in Orientations of Graphs. Graphs and Combinatorics, 10, 225-230.
- 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.
- Robbins, H.E. (1929) Theorem on Graphs, with an Application to a Problem of Traffic Control. The American Mathematical Monthly, 46, 281-283.