Length of the Longest Path and Diameter in Orientations of Graphs

• 作者: Bing Zhou
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: Directed GRAPHS Graph Orientation INTERVAL Property Longest PATH PATH LENGTH DIAMETER
• 年，卷（期）: 2017,（2）
• 页码范围: 65-70
• 页数: 6页
• 分类号: O1

摘要

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.