Project

Langste cykels en opspannende deelgrafen

Looptijd
01-10-2019 → Lopend
Financiering
Fonds voor Wetenschappelijk Onderzoek - Vlaanderen (FWO)
Mandaathouder
Onderzoeksdisciplines
Niet beschikbaar
Trefwoorden
Hamiltoniaanse cyclus Spanning-subgraaf Langste cyclus Vertex-verwijderde subgraaf Kortheidsexponent Spanning van bomen met weinig bladeren
 
Projectomschrijving

De hoofdthema's van dit voorstel uit de grafentheorie zijn langste cykels en opspannende deelgrafen van abstracte of ingebedde grafen. Een deelgraaf is "opspannend" als deze alle toppen van de supergraaf bevat. Nadruk zal liggen op hamiltoniaanse cykels, d.w.z. opspannende cykels, en hun interactie met andere belangrijke structurele eigenschappen van de graaf zoals geslacht, kruisingsgetal, samenhang en "toughness". De eerste twee meten hoe ver een graaf verwijderd is van vlak te zijn (het planair geval kan als het meest natuurlijke beschouwd worden), terwijl de laatste twee aangeven hoe strak de graaf aan elkaar hangt. Centrale onderzoeksrichtingen in dit project, deels in samenwerking met Duitse, Hongaarse, Japanse, Slowaakse en Zuid-Afrikaanse grafentheoretici, zijn het bestuderen van • uitbreidingen van een stelling van Thomassen over de hamiltoniciteit van een graaf en zijn toppen-verwijderde deelgrafen; • een probleem van Grünbaum over langste cykels die elk paar van toppen vermijden, en een gerelateerde vraag van Katona, Kostochka, Pach en Stechkin; • hamiltoniciteit in 3-samenhangende grafen met weinig cuts en kruisingen; • de "shortness exponent", een limiet geïntroduceerd door Grünbaum en Walther die de omtrek van grafen uit een familie van grafen meet; • het Digraph Path Partition vermoeden; • planariserende 2-factoren, natuurlijke uitbreidingen van vlakke hamiltoniaanse cykels naar een hoger geslacht; en • criticaliteit in opspannende bomen met weinig bladeren.