کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647678 1342366 2013 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Intersecting longest paths
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Intersecting longest paths
چکیده انگلیسی

In 1966, Gallai asked whether every connected graph has a vertex that is common to all longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs and 2-trees. Another related question was raised by Zamfirescu in the 1980s: Do any three longest paths in a connected graph have a vertex in common? The answer to this question is unknown. We prove that for connected graphs in which all nontrivial blocks are Hamiltonian the answer is affirmative. Finally, we state a conjecture and explain how it relates to the three longest paths question.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 12, 28 June 2013, Pages 1401–1408
نویسندگان
, , , ,