کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6424546 1632979 2015 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Equivalence of Jackson's and Thomassen's conjectures
ترجمه فارسی عنوان
همسان بودن فرضهای جکسون و تامسن
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A graph G is said to be claw-free if G has no induced subgraph isomorphic to K1,3. For a cycle C in a graph G, C is called a Tutte cycle of G if C is a Hamilton cycle of G, or the order of C is at least 4 and every component of G−C has at most three neighbors on C. Ryjáček (1997) [17] proved that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is Hamiltonian) and by Thomassen (every 4-connected line graph is Hamiltonian) are equivalent. In this paper, we show the above conjectures are equivalent with the conjecture by Jackson in 1992 (every 2-connected claw-free graph has a Tutte cycle).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 114, September 2015, Pages 124-147
نویسندگان
, , , , ,