Graduation Term

2022

Degree Name

Master of Science (MS)

Department

Department of Mathematics

Committee Chair

Songling Shan

Abstract

A Hamiltonian cycle in a graph G is a cycle which contains every vertex of G. The study of Hamiltonian cycle problem has a long history in graph theory and is a central theme. In general, it is NP-complete to decide whether a graph contains a Hamiltonian cycle. Thus researchers have been investigating sufficient conditions that guarantee the existence of a Hamiltonian cycle in a graph. There are many classic results along this line. For example, in 1952, Dirac showed that an n-vertex graph G with n ≥ 3 is Hamiltonian if δ(G) ≥ n. Chv´atal studied Hamiltonian cycles by considering graph toughness, a measure of resilience under the removal of vertices. Let t ≥ 0 be a real number and denote by c(G) the number of components of G. We say a graph G is t-tough if for each cut set S of G we have t · c(G − S) ≤ |S|. The toughness of a graph G, denoted τ (G), is the maximum value of t for which G is t-tough if G is non-complete, and is defined to be ∞ if G is complete. Chv´atal conjectured in 1973 the existence of some constant t such that all t-tough graphs with at least three vertices are Hamiltonian. While the conjecture has been proven for some special classes of graphs, it remains open in general. Supporting this conjecture of Chv´atal’s, in the first part of this thesis, we show that every 3-tough (P2 ∪ 3P1)-free graph with at least three vertices is Hamiltonian, where P2 ∪ 3P1 is the disjoint union of an edge and three isolated vertices. The notion of a 2-factor is a generalization of a Hamiltonian cycle, which consists of vertex disjoint cycles which together cover the vertices of G. Thus, a Hamiltonian cycle is just a 2-factor with exactly one cycle. It is known that every 2-tough graph with at least three vertices has a 2-factor. In graphs with restricted structures the toughness bound 2 can be improved. For example, it was shown that every 2K2-free 3/2-tough graph with at least three vertices has a 2-factor, and the toughness bound 3/2 is best possible. In viewing 2K2, the disjoint union of two edges, as a linear forest, in this thesis, for any linear forest R on 5, 6, or 7 vertices, we find the sharp toughness bound t such that every t-tough R-free graph on at least three vertices has a 2-factor.

Access Type

Thesis-Open Access

DOI

https://doi.org/10.30707/ETD2022.20220705065051192756.999994

Download

Share

COinS