Local conditions for Hamiltonicity of graphs

This thesis contains new contributions to the subfield of graph theory which is usually referred to as hamiltonian graph theory. The main concept in this area of discrete mathematics is a Hamilton cycle. In a graph G=(V,E) on vertex set V=〖{v〗_1,v_2,…〖,v〗_n} and edge set E, a Hamilton cycle corresponds to a sequence v_1 v_2…v_n v_1 such that v_i v_(i+1)∈E for all i∈{i,…,n-1} and v_n v_1∈E. If G admits such a Hamilton cycle, then G is called hamiltonian. Studying the hamiltonicity of graphs means examining conditions for the existence (or nonexistence) of Hamilton cycles in graphs.

In this thesis we mainly focus on local conditions for hamiltonicity of graphs. Our new results involve a diversity of local conditions. In Chapter 2 we focus on localizing the global degree condition for claw-free graphs due to Matthews and Sumner.

In Chapter 3, we are interested in the smallest value of the integer k such that a k -connected K_1,4-free graph G is hamiltonian if for every pair of vertices u,v with d(u,v)=2, N(u) ⋂▒〖N(v)〗≤2. We prove that if k=2, then either G is 1-tough or G belongs to two well-described classes of exceptional graphs, and that if G satisfies a connectivity condition (implying k=3), then G is hamiltonian.

In Chapter 4, we focus on extending local theorems for hamiltonicity to spanning trees with few leaves. We first extend a local degree condition for bipancyclicity of balanced bipartite graphs, due to Shi and Lou, to spanning trees with few leaves in (non)balanced bipartite graphs. Secondly, we establish a local closure result for spanning trees with few leaves, similar to the closure result due to Bondy and Chvátal.

In Chapter 5, we characterize the structure of the c-closure of 2-connected {R,S} - o -heavy graphs, where R= K_1,3 and S={P_4,P_5,C_3,Z_1,Z_2,B,N,W}. Our main results extend or generalize several earlier results on hamiltonicity involving forbidden or o-heavy subgraphs.

In Chapter 6, we restrict Ore's degree condition (or Dirac's degree condition) to induced copies of the net and the wounded for guaranteeing that a 2-connected claw- o -heavy graph is hamiltonian.

All the results of this thesis are somehow motivated by the overall challenge to obtain the weakest possible conditions that guarantee the hamiltonicity of graphs (or related properties). Since it is plausible and widely believed that there does not exist a nice easy to check necessary and sufficient condition for hamiltonicity, this seems to be an everlasting challenge. We hope that this will motivate new researchers to contribute with new ideas to this fascinating area.