Full metadata record
DC pole | Hodnota | Jazyk |
---|---|---|
dc.contributor.author | Kabela, Adam | |
dc.date.accessioned | 2019-01-14T11:00:09Z | |
dc.date.available | 2019-01-14T11:00:09Z | |
dc.date.issued | 2019 | |
dc.identifier.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. | en |
dc.identifier.issn | 0012-365X | |
dc.identifier.uri | 2-s2.0-85054444831 | |
dc.identifier.uri | http://hdl.handle.net/11025/30772 | |
dc.format | 9 s. | cs |
dc.format.mimetype | application/pdf | |
dc.language.iso | en | en |
dc.publisher | Elsevier | en |
dc.relation.ispartofseries | Discrete Mathematics | en |
dc.rights | © Elsevier | en |
dc.title | Long paths and toughness of k-trees and chordal planar graphs | en |
dc.type | postprint | cs |
dc.type | postprint | en |
dc.rights.access | openAccess | en |
dc.type.version | acceptedVersion | en |
dc.description.abstract-translated | 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. | en |
dc.subject.translated | k-trees | en |
dc.subject.translated | Chordal planar graphs | en |
dc.subject.translated | Hamilton-connectedness | en |
dc.subject.translated | Shortness exponent | en |
dc.subject.translated | Toughness | en |
dc.identifier.doi | 10.1016/j.disc.2018.08.017 | |
dc.type.status | Peer-reviewed | en |
dc.identifier.document-number | 451939300006 | |
dc.identifier.obd | 43924231 | |
dc.project.ID | LO1506/PUNTIS - Podpora udržitelnosti centra NTIS - Nové technologie pro informační společnost | cs |
dc.project.ID | GA17-04611S/Ramseyovské aspekty barvení grafů | cs |
dc.project.ID | SGS-2016-003/Kvalitativní a kvantitativní studium matematických modelů III. | cs |
Vyskytuje se v kolekcích: | Postprinty / Postprints (KMA) OBD |
Soubory připojené k záznamu:
Soubor | Velikost | Formát | |
---|---|---|---|
1707.08026.pdf | 308,46 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/30772
Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.