کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651334 | 1632450 | 2006 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tough graphs and hamiltonian circuits
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/ts/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t0t0, every t0t0-tough graph is hamiltonian. Since a square of a k-connected graph is always k -tough, a proof of this conjecture with t0=2t0=2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of (3/2)-tough nonhamiltonian graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 10–11, 28 May 2006, Pages 910–917
Journal: Discrete Mathematics - Volume 306, Issues 10–11, 28 May 2006, Pages 910–917
نویسندگان
V. Chvátal,