Tuhost a Hamiltonovskost grafů

Abstract

Hlavní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).