TITLE:
Length of the Longest Path and Diameter in Orientations of Graphs
AUTHORS:
Bing Zhou
KEYWORDS:
Directed Graphs, Graph Orientation, Interval Property, Longest Path, Path Length, Diameter
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.7 No.2,
April
19,
2017
ABSTRACT: We say that a parameter p of directed graphs has the interval property if for every graph Gand 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.