Hamilton paths in {K1,4,K1,4+e}-free graphs

摘要

A graph G is called {H1,H2,…,Hk}-free if G contains no induced subgraph isomorphic to any Hi, 1ik. If G is a complete graph, we set NC=|V(G)|-1, otherwise NC is denoted as NC+min｛|N(x)UN(y)|:x,yeV(G)and xyE(G)｝.Let G be a 2-connected {K1,4,K1,4+e}-free graph of order n. If NC(n-2)/2, then G has a Hamilton path, where K1,4+e is a graph obtained by joining a pair of nonadjacent vertices in a K1,4.