کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419855 683868 2011 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamiltonian properties of locally connected graphs with bounded vertex degree
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Hamiltonian properties of locally connected graphs with bounded vertex degree
چکیده انگلیسی

We consider the existence of Hamiltonian cycles for the locally connected graphs with a bounded vertex degree. For a graph GG, let Δ(G)Δ(G) and δ(G)δ(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with Δ(G)⩽4Δ(G)⩽4. We show that every connected, locally connected graph with Δ(G)=5Δ(G)=5 and δ(G)⩾3δ(G)⩾3 is fully cycle extendable which extends the results of Kikust [P.B. Kikust, The existence of the Hamiltonian circuit in a regular graph of degree 5, Latvian Math. Annual 16 (1975) 33–38] and Hendry [G.R.T. Hendry, A strengthening of Kikust’s theorem, J. Graph Theory 13 (1989) 257–260] on full cycle extendability of the connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for the locally connected graphs with Δ(G)⩽7Δ(G)⩽7 is NP-complete.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 16, 28 September 2011, Pages 1759–1774
نویسندگان
, , , ,