کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649785 1342465 2009 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding Hamiltonian cycles in {quasi-claw,K1,5,K1,5+e}{quasi-claw,K1,5,K1,5+e}-free graphs with bounded Dilworth numbers
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Finding Hamiltonian cycles in {quasi-claw,K1,5,K1,5+e}{quasi-claw,K1,5,K1,5+e}-free graphs with bounded Dilworth numbers
چکیده انگلیسی

Let uu and vv be two vertices in a graph GG. We say vertex uu dominates vertex vv if N(v)⊆N(u)∪{u}N(v)⊆N(u)∪{u}. If uu dominates vv or vv dominates uu, then uu and vv are comparable. The Dilworth number of a graph GG, denoted as Dil(G)Dil(G), is the largest number of pairwise incomparable vertices in the graph GG. A graph GG is called quasi-claw-free if it satisfies the property: d(x,y)=2⇒d(x,y)=2⇒ there exists u∈N(x)∩N(y)u∈N(x)∩N(y) such that N[u]⊆N[x]∪N[y]N[u]⊆N[x]∪N[y]. A graph is called {quasi-claw,K1,5,K1,5+e}{quasi-claw,K1,5,K1,5+e}-free if it is quasi-claw-free and contains no induced subgraph isomorphic to K1,5K1,5 or K1,5+eK1,5+e, where K1,5+eK1,5+e is a graph obtained by joining a pair of nonadjacent vertices in K1,5K1,5. It is shown that if GG is a kk (k≥2k≥2)-connected {quasi-claw,K1,5,K1,5+e}{quasi-claw,K1,5,K1,5+e}-free graph with Dil(G)≤2k−1Dil(G)≤2k−1, then GG is Hamiltonian and a Hamiltonian cycle in GG can be found in polynomial time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2555–2558
نویسندگان
,