کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646665 | 1342309 | 2016 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Spanning trees homeomorphic to a small tree
ترجمه فارسی عنوان
هومومورفیک درختان پوشا برای یک درخت کوچک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درخت پوشا؛ زير مجموعه؛ هومومورفیک؛ مسیر همیلتونی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A classical result of Ore states that if a graph GG of order nn satisfies degGx+degGy≥n−1degGx+degGy≥n−1 for every pair of nonadjacent vertices xx and yy of GG, then GG contains a hamiltonian path. In this note, we interpret a hamiltonian path as a spanning tree which is a subdivision of K2K2 and extend Ore’s result to a sufficient condition for the existence of a spanning tree which is a subdivision of a tree of a bounded order. We prove that for a positive integer kk, if a connected graph GG satisfies degGx+degGy≥n−kdegGx+degGy≥n−k for every pair of nonadjacent vertices xx and yy of GG, then GG contains a spanning tree which is a subdivision of a tree of order at most k+2k+2. We also discuss the sharpness of the result.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 677–681
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 677–681
نویسندگان
Akira Saito, Kazuki Sano,