A graph is hamiltonian if it contains a spanning cycle. A variety of techniques have been used to determine when a graph has this property. The central theme of this dissertation is to investigate the edge extremal conditions related to some of the results that ensure hamiltonicity.; Two types of edge extremal problems are considered--identifying maximum non-hamiltonian graphs which fail to satisfy a condition for hamiltonicity and identifying minimum graphs which do satisfy a condition for hamiltonicity. Both types of problems are studied for several hamiltonian properties, most of which involve some type of degree condition while some rely either on local structure or on forbidden subgraphs. Edge bounds are determined and extremal graphs are identified with a discussion of uniqueness. The condition for hamiltonicity is generalized in the chapters that discuss the closure of a graph.; The final chapter describes another type of edge extremal problem relative to random graphs, which involves a probabilistic setting. Some new results on complete k-closures in random graphs are obtained in this chapter.
展开▼
