Document Type
Lecture
Publication Date
5-12-2011
Abstract
A graph is said to be chordal if it does not have an induced cycle greater than three. A vertex is said to be k-simplicial if its neighborhood is a kclique. The smallest k-tree is a clique with k vertices. A graph G with more than k vertices is said to be k-tree if it has a k-simplicial vertex s1 such that G s1 is a k-tree. Note that a k-tree is a chordal graph. In the paper Tough enough chordal graphs are Hamiltonian the authors G. Chen, M. S. Jacobson, A. E. Kezdy, and J. Lehel showed that 18-tough chordal graphs are Hamiltonian. It is believed that the actual bound is closer to 2-tough. I will discuss the status of this problem, and present some advances on nding a tight bound for k-trees.
Relational Format
presentation
Recommended Citation
Shook, James, "On Finding a Minimum Toughness Condition for a k-Tree to be Hamiltonian" (2011). Combinatorics Seminar. 69.
https://egrove.olemiss.edu/math_combinatorics/69
