کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650336 1342485 2008 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamiltonian properties of triangular grid graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Hamiltonian properties of triangular grid graphs
چکیده انگلیسی

A triangular grid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional triangular grid. In 2000, Reay and Zamfirescu showed that all 2-connected, linearly-convex triangular grid graphs (with the exception of one of them) are hamiltonian. The only exception is a graph DD which is the linearly-convex hull of the Star of David. We extend this result to a wider class of locally connected triangular grid graphs. Namely, we prove that all connected, locally connected triangular grid graphs (with the same exception of graph DD) are hamiltonian. Moreover, we present a sufficient condition for a connected graph to be fully cycle extendable. We also show that the problem Hamiltonian Cycle is NP-complete for triangular grid graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 24, 28 December 2008, Pages 6166–6188
نویسندگان
, , ,