Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650413 | Discrete Mathematics | 2008 | 6 Pages |
Abstract
A graph G is called {H1,H2,…,Hk}{H1,H2,…,Hk}-free if G contains no induced subgraph isomorphic to any HiHi, 1⩽i⩽k1⩽i⩽k. If G is a complete graph, we set NC=|V(G)|-1NC=|V(G)|-1, otherwise NC is denoted as NC=min{|N(x)∪N(y)|:x,y∈V(G)andxy∉E(G)}.Let G be a 2-connected {K1,4,K1,4+e}{K1,4,K1,4+e}-free graph of order n . If NC⩾(n-2)/2NC⩾(n-2)/2, then G has a Hamilton path, where K1,4+eK1,4+e is a graph obtained by joining a pair of nonadjacent vertices in a K1,4K1,4.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Houyuan Lin, Jianglu Wang,