Article ID Journal Published Year Pages File Type
4650413 Discrete Mathematics 2008 6 Pages PDF
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.

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