On Finding A Minimum Toughness Condition for a k-tree to be Hamiltonian

The toughness of a graph is a connectivity measure of how easy it is to shatter a graph into many pieces. The higher the toughness of a graph, the harder it is to break the graph into a significant number of pieces. I will give a formal definition of the toughness in my talk.

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 k-clique. The smallest k-tree is a complete graph on k vertices. A graph with more than k vertices is said to be a k-tree if it has a k-simplicial vertex v such that G-v is a k-tree. Note that a k-tree is a chordal graph and has a nice recursive definition.

A graph is said to be Hamiltonian if it has a cycle that visits every vertex exactly once. 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 finding a tight bound for k-trees.

Speaker Bio: Dr James Shook obtained a B.S. in Mathematics from the University of Maryland. With the support of a GAANN fellowship he earned a M.S. and Ph.D. in Mathematics from the University of Mississippi. James started in August 2011, as a National Research Council Postdoctoral Research Associate in the Applied and Computational Mathematics Division in the ITL at NIST. Dr. Shook is interested in structural graph theory and the evolution of affiliations in social networks.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Robin Bickel; (301) 975-3668; at least 24 hours in advance.