Title: Long paths and toughness of k-trees and chordal planar graphs
Authors: Kabela, Adam
Citation: KABELA, A. Long paths and toughness of k-trees and chordal planar graphs. DISCRETE MATHEMATICS, 2019, roč. 342, č. 1, s. 55-63. ISSN 0012-365X.
Issue Date: 2019
Publisher: Elsevier
Document type: postprint
postprint
URI: 2-s2.0-85054444831
http://hdl.handle.net/11025/30772
ISSN: 0012-365X
Keywords in different language: k-trees;Chordal planar graphs;Hamilton-connectedness;Shortness exponent;Toughness
Abstract: 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 log_{30}22, respectively. Both improve the bound of Böhme et al. Furthermore, the construction provides k-trees (for k >= 4) of toughness greater than 1.
Abstract in different language: 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 log_{30}22, respectively. Both improve the bound of Böhme et al. Furthermore, the construction provides k-trees (for k >= 4) of toughness greater than 1.
Rights: © Elsevier
Appears in Collections:Postprinty / Postprints (KMA)
OBD

Files in This Item:
File SizeFormat 
1707.08026.pdf308,46 kBAdobe PDFView/Open


Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/30772

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

search
navigation
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD