کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649399 1342452 2010 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
چکیده انگلیسی

In 1956, W.T. Tutte proved that every 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. It is shown that Sanders’ result is best possible by constructing 4-connected maximal planar graphs with three edges a large distance apart such that any hamiltonian cycle misses one of them. If the maximal planar graph is 5-connected then such a construction is impossible.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 9, 6 May 2010, Pages 1491–1494
نویسندگان
, ,