کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871230 | 1440180 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Gallai's question and constructions of almost hypotraceable graphs
ترجمه فارسی عنوان
سوال و ساختارهای گالیله از نمودارهای تقریبا غیر قابل تحمل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Consider a graph G in which the longest path has order |V(G)|â1. We denote the number of vertices v in G such that Gâv is non-traceable with tG. Gallai asked in 1966 whether, in a connected graph, the intersection of all longest paths is non-empty. Walther showed that, in general, this is not true. In a graph G in which the longest path has |V(G)|â1 vertices, the answer to Gallai's question is positive iff tGâ 0. In this article we study almost hypotraceable graphs, which constitute the extremal case tG=1. We give structural properties of these graphs, establish construction methods for connectivities 1 through 4, show that there exists a cubic 3-connected such graph of order 28, and draw connections to works of Thomassen and Gargano et al.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 243, 10 July 2018, Pages 270-278
Journal: Discrete Applied Mathematics - Volume 243, 10 July 2018, Pages 270-278
نویسندگان
Gábor Wiener, Carol T. Zamfirescu,