Hamilton Cycles, Paths and Centers of Chordal Graphs

A graph that does not contain induced cycles other than a triangle is said to be a chordal graph. Every chordal graph has at least two vertices whose vertex neighborhoods are cliques. In this dissertation we investigate two classic problems applied to the class of a chordal graphs.;Determining if a graph has a Hamilton cycle has been studied extensively in graph theory. Most researchers give either a sufficient or a necessary condition, but rarely give both. It is an important problem to characterize the Hamiltonian graphs in a particular class of graphs with a known necessary condition.;A k-tree is a chordal graph that can be defined recursively in the following way. The smallest k-tree is a k-clique. A graph is said to be a k-tree if there exists a vertex whose neighborhood is a clique of size k, that when the vertex is removed the resulting graph is a k-tree.;We will introduce a new parameter called the branch number of a k-tree and give an equation that relates the branch number to some other graph parameters. Using the branch number, we will present some results on Hamiltonian properties of k-trees. We will then look to see how we can extend our results to general chordal graphs. Some k-trees containing no Hamiltonian cycles under certain conditions will also be constructed.;The second topic focuses on the conjecture which says that all longest paths in a connected chordal graph share a common vertex. It is known that there exists a clique that contains a vertex from every longest path, but this does not settle the conjecture. In many examples, the longest paths intersect their centers. Thus, understanding the structures of centers of chordal graphs may help to settle this conjecture. We will present a complete characterization of the centers of chordal graphs.;At the end of this dissertation, we will propose some related problems for further research.