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

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
نویسندگان
,