Article ID Journal Published Year Pages File Type
4649785 Discrete Mathematics 2009 4 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,