2017/07/25 by Adam Kabela, Kabela, Adam
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1707.08026
openalex publication_date 2017/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that every k-tree of toughness greater than (k)/(3) is Hamilton-connected for k ≥ 3. (In particular, chordal planar graphs of toughness greater than 1 are Hamilton-connected.) This improves the result of Broersma et al. (2007) and generalizes the result of Böhme et al. (1999). On the other hand, we present graphs whose longest paths are short. Namely, we construct 1-tough chordal planar graphs and 1-tough planar 3-trees, and we show that the shortness exponent of the class is 0, at most log3022, respectively. Both improve the bound of Böhme et al. Furthermore, the construction provides k-trees (for k ≥ 4) of toughness greater than 1.