关键词: Local condition, Hamilton cycle

Abstract:

Let G be a 2-connected graph of order n( 3). If I(u, v)  S(u, v) or max {d(u), d(v)}  n/2 for any two vertices u, v at distance two in an induced subgraph K1 ,3 or P3 of G , then G is hamiltonian. Here I(u, v) = |N(u)\N(v)|, S(u, v) denotes the number of edges of maximum star containing u, v as an induced subgraph in G.

Key words: Local condition, Hamilton cycle