Full metadata record
DC FieldValueLanguage
dc.contributor.authorKabela, Adam
dc.date.accepted2018-6-26
dc.date.accessioned2019-03-18T08:42:16Z-
dc.date.available2014-9-2
dc.date.available2019-03-18T08:42:16Z-
dc.date.issued2018
dc.date.submitted2018-4-25
dc.identifier76744
dc.identifier.urihttp://hdl.handle.net/11025/33609
dc.description.abstractHlavním tématem předložené práce je výzkum související s Chvátalovou hypotézou o tuhosti a Hamiltonovskosti grafů. V úvodu práce připomeneme tuto hypotézu v širším kontextu. Dále studujeme vybrané částečné výsledky a analyzujeme konstrukce, které dávají dolní meze vzhledem k této hypotéze a souvisejícím otázkám. Ve snaze o obecnější porozumění hledáme vzájemné souvislosti mezi vybranými přístupy k tomuto problému. V závěrečné kapitole navrhujeme možná pokračování ve studiu této problematiky, která vycházejí z myšlenek předložené práce. Autor práce předkládá nové výsledky související s Chvátalovou hypotézou. S použitím hypergrafové verze Hallovy věty ukážeme, že každý 10-tuhý chordální graf je Hamiltonovsky souvislý. Dále ukážeme, že k-stromy s tuhostí vyšší než k/3 jsou Hamiltonovsky souvislé pro k >= 3 (a jako důsledek dostáváme Hamiltonovskou souvislost chordálních rovinných grafů s tuhostí vyšší než 1). Zmíněná tvrzení vylepšují dříve známé výsledky Chen a spol. (1998), Broersma a spol. (2007) a Böhme a spol. (1999). Další částečný výsledek se týká takzvaných multisplit grafů, pro které ukážeme, že tuhost alespoň 2 zaručuje Hamiltonovskou souvislost. Zabýváme se také grafy, které mají speciální strukturu odvozenou od takzvaných kaktusů. Ukážeme, že otázka Hamiltonovskosti těchto grafů se dá rozhodovat pomocí Fordovy-Fulkersonovy věty o maximálním toku a minimálním řezu. Studujeme také konstrukce grafů, které mají relativně vysokou tuhost a zároveň relativně krátké nejdelší kružnice. Konkrétně konstruujeme maximální rovinné grafy, jejichž tuhost je 5/4 nebo 8/7 nebo vyšší než 1, a dále 1-tuhé chordální rovinné grafy, 1-tuhé rovinné 3-stromy a k-stromy s tuhostí vyšší než 1 pro k >= 4. Navržené konstrukce vedou k vylepšení dříve známých výsledků Harant a Owens (1995), Tkáč (1996), Böhme a spol. (1999) a Broersma a spol. (2007).cs
dc.format63 s., 21 s. přílohy
dc.format.mimetypeapplication/pdf
dc.language.isoenen
dc.publisherZápadočeská univerzita v Plznics
dc.rightsPlný text práce je přístupný bez omezení.cs
dc.subjecttuhost grafůcs
dc.subjecthamiltonovskostcs
dc.subjectprůnikové reprezentace grafůcs
dc.subjectshortness exponentcs
dc.titleTuhost a Hamiltonovskost grafůcs
dc.title.alternativeToughness and Hamiltonicity of graphsen
dc.typedisertační prácecs
dc.thesis.degree-namePh.D.
dc.thesis.degree-levelDoktorskýcs
dc.thesis.degree-grantorZápadočeská univerzita v Plzni. Fakulta aplikovaných vědcs
dc.thesis.degree-programMatematikacs
dc.description.resultNeobhájenocs
dc.rights.accessopenAccessen
dc.description.abstract-translatedThe present thesis is motivated by the study of Chvátal's t_0-tough conjecture. We recall this conjecture in the context of Hamiltonian Graph Theory. We review partial results to the conjecture, and we analyse constructions which provide lower bounds to this conjecture and to similar problems. We discuss some unifying views on the successful approaches towards this conjecture. Following the ideas presented in the thesis, we suggest possible directions for further research. We present new results related to the t_0-tough conjecture. In particular, we apply the hypergraph extension of Hall's theorem and show that every 10-tough chordal graph is Hamilton-connected. Also we show that k-trees of toughness greater than k/3 are Hamilton-connected for k >= 3 (and consequently, chordal planar graphs of toughness greater than 1 are Hamilton-connected). These results improve the results of Chen et al. (1998), Broersma et al. (2007) and Böhme et al. (1999). In addition, we study so-called multisplit graphs and show that toughness at least 2 implies Hamilton-connectedness of these graphs; and studying certain 'cactus-like' graphs, we show that their Hamiltonicity can be decided by using Max-flow min-cut theorem. Furthermore, we present constructions of graphs of relatively high toughness whose longest cycles are relatively short. Namely, we construct maximal planar graphs of toughness 5/4, 8/7, greater than 1, respectively; and 1-tough chordal planar graphs, 1-tough planar 3-trees, and k-trees of toughness greater than 1 for k >= 4. These constructions improve the bounds presented by Harant and Owens (1995), Tkáč (1996), Böhme et al. (1999) and Broersma et al. (2007).en
dc.subject.translatedtoughness of graphsen
dc.subject.translatedhamiltonicityen
dc.subject.translatedintersection representations of graphsen
dc.subject.translatedshortness exponenten
Appears in Collections:Disertační práce / Dissertations (KMA)

Files in This Item:
File Description SizeFormat 
Toughness_and_Hamiltonicity_of_graphs_Adam_Kabela.pdfPlný text práce1,41 MBAdobe PDFView/Open
posudek-odp-kabela.pdfPosudek oponenta práce1,88 MBAdobe PDFView/Open
protokol-ODP-kabela.pdfPrůběh obhajoby práce899,95 kBAdobe PDFView/Open


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

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