Title: Zobecněné hamiltonovské kružnice
Other Titles: Generalized Hamiltonian cycles
Authors: Kabela, Adam
Advisor: Teska, Jakub
Referee: Holub, Přemysl
Issue Date: 2012
Publisher: Západočeská univerzita v Plzni
Document type: diplomová práce
URI: http://hdl.handle.net/11025/3683
Keywords: hamiltonovská kružnice;r-trestle;tuhost;chordální grafy;rovinné grafy;shortness exponent;zakázané podgrafy
Keywords in different language: hamiltonian cycle;r-trestle;toughness;chordal graphs;planar graphs;shortness exponent;forbidden subgraphs
Abstract: V této práci ukážeme různé souvislosti mezi hamiltonovskými kružnicemi, r-trestly a tuhostí grafu. Budeme sledovat, jak se tyto souvislosti mění, pokud namísto obecných grafů uvažujeme chordální grafy nebo rovinné grafy. Zmíníme další možná zobecnění hamiltonovských kružnic a jejich vzájemné vztahy, a v neposlední řadě také souvislost hamiltonovských kružnic a r-trestlů se zakázanými podgrafy. Práce obsahuje nové výsledky související s touto problematikou. Konkrétně jsou to chordální grafy a chordální rovinné grafy s relativně velkou tuhostí, které nemají r-trestle. Tyto grafy vylepšují horní odhad pro shortness exponent třídy 1-tuhých chordálních rovinných grafů. Ukážeme také dvojici zakázaných podgrafů, která zajistí, že daný graf má r-trestle.
Abstract in different language: This thesis shows the relations among the hamiltonian cycle, the r-trestle and the toughness of a graph and how the relations change considering general graphs, chordal graphs and planar graphs. Some other relations dealing with generalizing hamiltonicity, the toughness of a graph and also the hamiltonicity and forbidden subgraphs are mentioned. As the original results we present chordal graphs and chordal planar graphs with high toughness and no r-trestle. These graphs improves the upper bound on the shortness exponent of the class of 1-tough chordal planar graphs. We also present a sufficient condition on forbidden subgraphs for a graph to have an r-trestle.
Rights: Plný text práce je přístupný bez omezení
Appears in Collections:Diplomové práce / Theses (KMA)

Files in This Item:
File Description SizeFormat 
DP_Adam_Kabela.pdfPlný text práce619,28 kBAdobe PDFView/Open
PV-Kabela.pdfPosudek vedoucího práce133,67 kBAdobe PDFView/Open
PO-Kabela.pdfPosudek oponenta práce255,03 kBAdobe PDFView/Open
P-Kabela.pdfPrůběh obhajoby práce36,32 kBAdobe PDFView/Open


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

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