Degree-light-free graphs and Hamiltonian cycles

A graph is hamiltonian if it has a hamiltonian cycle, a cycle containing all vertices of the graph. Dirac's and Ore's Theorems are probably among the first to consider the degree conditions for hamiltonian graphs. In 1984, Fan showed every 2-connected graph G satisfying max{d(x),d(y)} ≥ |V(G)|/2 for every x,y V(G) with dist( u,v) = 2 is hamiltonian. A graph H is forbidden in G, or G is H-free, if G has no induced subgraph isomorphic to H. G is degree-light H-free (or simply DL-H-free) if G is either H-free or, for every induced subgraph K of G with K ≅ H, and every {u, v} ⊆ K, dist K (u, v) = 2 implies max{dG( u),dG(v)} ≥ | V(G)|/2. This concept combined the ideas of H-free and Fan's condition for hamiltonian graphs.;In this dissertation, we will consider graphs K 1,3, N, P6 and Z and some others. K1,3 is also called a claw, it is a complete bipartite graph on 4 vertices with one partition having one vertex and the other having three. N, P6 and Z all have 6 vertices. N is a triangle with an edge attached to each vertex of the triangle, P6 is a path of 6 vertices, and Z is obtained from P 6 by joining the first and the third vertex of the path an edge.;In 1980, Duffus et.al. [17] showed that every 2-connected {K 1,3, N}-free graph is hamiltonian. In 1991, Bedrossian [1] showed that every 2-connected {K 1,3, P6}-free graph is hamiltonian. Faudree et.al. [20] proved in 1995 that same is true for 2-connected {K 1,3, Z}-free graphs of order at least 10. We will generalize all these three results, and show that a 2-connected graph is hamiltonian, if it is degree-light {K1,3, H}-free for any of H = N, P 6 or Z, except when H = Z, there are three exceptional graphs, all of them having order nine. We will give several classes of graphs to show that the hamiltonicity of the graphs can not be deduced from one of the existing results, but can be deduced from our corresponding generalized result.;A sufficient condition on neighborhood unions for bipartite graphs to be hamiltonian will also be given. Let G = (X, Y, E) be a 2-connected bipartite graph with |X| = | Y| = n. If |N(x 1) ∪ N(x2)| + | N(y1) ∪ N( y2)| ≥ n + 2 for any {x 1, x2}⊆ X and { y1, y2} ⊆ Y, then G is either hamiltonian or is isomorphic to one of five exceptional graphs on at most 12 vertices.