Nieuwe algoritmes en computer-geassisteerde methodes voor het oplossen van hamiltoniciteitsproblemen

Het strategische doel van dit project is om nieuwe grafenalgoritmen en andere computerondersteunde bewijstechnieken te ontwikkelen om moeilijke grafentheoretische problemen op te lossen. We zijn van plan om deze problemen op te lossen met behulp van een gecombineerde theoretische en computationele aanpak.In het bijzonder zullen we ons concentreren op hamiltoniciteitsproblemen, een onderwerp dat centraal staat in de grafentheorie. Onze inspanningen zullen op drie uitdagende onderzoekslijnen gericht worden.Ons doel voor de eerste onderzoekslijn is om constructieve algoritmen te ontwerpen voor het genereren van K2-hamiltoniaanse grafen om vooruitgang te boeken op een vermoeden van Grünbaum en om gerelateerde open problemen op te lossen.In de tweede onderzoekslijn zullen we uitbreidingen van stellingen van Tutte en Thomassen over lange cykels in polyhedrale grafen onderzoeken.Ten slotte heeft de derde onderzoekslijn betrekking tot een vermoeden van Faudree en Schelp. Hier zullen we het cykelspectrum van hamiltoniaans-verbonden grafen analyseren.

Trefwoorden:Hamiltonicity, Computer-aided methods, Long cycles, Graph generation, Graph theory, Graph algorithms, Vertex-deleted subgraphs, Hamiltonian-connected

Disciplines:Toegepaste discrete wiskunde, Combinatoriek, Computerwetenschappen