کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649785 | 1342465 | 2009 | 4 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: 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](/preview/png/4649785.png)
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.
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2555–2558