-
Natural sciences
- Combinatorics
- Applied discrete mathematics
In de grafentheorie is een cykel in een graaf hamiltoniaans als hij elke top van de graaf bevat. Hamiltoniciteit bepalen is moeilijk en is een van Karps beroemde 21 NP-complete problemen. Toepassingen van hamiltoniciteit variëren van combinatorische optimalisatie - in het bijzonder het Handelsreizigersprobleem - en operationeel onderzoek tot coderingstheorie, theoretische computerwetenschap, moleculaire chemie en fouttolerantie in netwerken. Mijn project is nauw verbonden met het bestuderen van hamiltoniaanse cykels en verwante structuren. Ik zal een reeks onderling verbonden vermoedens en problemen behandelen over langste cykels en opspannende deelgrafen, met speciale nadruk op planaire 3-samenhangende grafen, d.w.z. de 1-skeleta van veelvlakken.