Document Type
Lecture
Publication Date
11-15-2013
Abstract
A graph is said to be planar if G may be con gured in the plane without edge crossings and is chordal if G has no induced cycles of size greater than 3. A graph G is hamiltonian if there is a cycle that passes through all vertices of G, a hamiltonian cycle. In 1999, Bohme et al. showed the every chordal planar graph with toughness exceeding 1 is hamiltonian. The generalized tree, the k-tree is de ned recursively as follows: (i) The smallest k-tree is the k-clique Kk. (ii) For n k, if Tk n is a k-tree with n vertices and a new vertex v of degree k is added and joined to the vertices of a k-clique in Tk n, then the larger graph is a k-tree with n + 1 vertices. In this presentation, we de ne tree-like k-trees, a subclass of k-trees. Chordal planar graphs with toughness exceeding 1 are all shown to be tree-like 3-trees with toughness exceeding 1, and from the perspective of tree-like 3-trees, we strengthen the result of Bohme et al. mentioned above by showing that every edge of a more than 1-tough tree-like 3-tree is contained in a hamiltonian cycle. This is joint work with W. Staton and B. Wei.
Relational Format
presentation
Recommended Citation
Estes, John, "Hamiltonian cycles through a given edge of more than 1-tough chordal planar graphs" (2013). Combinatorics Seminar. 53.
https://egrove.olemiss.edu/math_combinatorics/53
