Tætheden af inerti-båndet af grafer: Hvornår er inerti-båndet ikke tæt?

Studenteropgave: Speciale (inkl. HD afgangsprojekt)

  • Nicolai Aarup Nielsen
4. semester, Matematik, Kandidat (Kandidatuddannelse)
Denne rapport om algebraisk grafteori præsenterer en øvre begrænsning for uafhængighedsnummeret af grafer, og studerer hvorvidt denne begrænsning er opnåelig for alle grafer. Begrænsningen kaldes inerti-båndet.
Startende med den indledende graf- og matrixteori udledes inerti-båndet, sammen med de forhold som gør at begrænsningen ikke er tæt, og nogle eksempler af grafer, som opnår tæthed af inerti-båndet.
Dernæst introduceres Paley grafer og deres egenskaber, med særligt fokus på Paley grafen med 17 punkter og nogle af dens delgrafer.
Fra disse egenskaber kan det vises, at uanset hvilke værdier der tildeles kanterne af Paley 17, kan den ikke opnå tæthed af inerti-båndet. Derfor kan ikke alle grafer have tæthed af inerti-båndet.
Rapporten afrundes med en præsentation af emner, som er velegnede for videre studering. Deriblandt et dybere indblik i de egenskaber for grafer, som resulterer i tæthed i inerti-båndet, samt en undersøgelse af, hvad der sker for inertibåndet, når de værdier der tildeles kanterne i grafer, tages over et andet legeme.
SprogEngelsk
Udgivelsesdato1 jun. 2018
Antal sider35
ID: 280258680