کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647678 | 1342366 | 2013 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Intersecting longest paths
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Intersecting longest paths Intersecting longest paths](/preview/png/4647678.png)
چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 313, Issue 12, 28 June 2013, Pages 1401–1408
نویسندگان
Susanna F. de Rezende, Cristina G. Fernandes, Daniel M. Martin, Yoshiko Wakabayashi,