Grafer med maksimal grad d, diameter k og lille defekt

Studenteropgave: Speciale (inkl. HD afgangsprojekt)

  • Anita Abildgaard Sillasen
4. semester, Matematik, Kandidat (Kandidatuddannelse)
Rapporten er resultatet af spe- ciale perioden på 10. semester i diskret matematik. Specialet tager udgangspunkt i det såkaldte grad/diameter-problem, der omhandler hvor store grafer man kan konstruere, når en maksimal grad d og diameter k er givet på forhånd. En graf der har maksimal grad d og diameter k kaldes en (d;k)-graf og har n(d;k) knuder. I Kapitel 1 bliver en teoretisk øvre grænse for n(d;k) givet vha. Moore- grænsen M(d;k). Desuden bliver det gennemgået, hvordan det kan bevises, at det er meget få (d;k)- grafer, der har M(d;k) knuder. I Kapitel 2 forklares det hvorfor der eksisterer meget få (d;k)-grafer, der har M(d;k) 􀀀 1 knuder, og derfor bliver forskellige egenskaber vedrø- rende (d;k)-grafer med M(d;k) 􀀀 2 knuder betragtet i Kapitel 3. Specielt bliver det bevist, at der ek- sisterer meget få (3;k)-grafer med M(3;k)􀀀2 knuder, hvilket er grun- den til, at Kapitel 4 omhandler (3;k)-grafer medM(3;k)􀀀4 knuder. Igen bevises det, at det er meget få grafer af denne type der eksisterer. Afslutningsvis betragtes nogle af de største kendte (d;k)-grafer. Da mange af disse store grafer er Cayley-grafer betragtes desuden en simpel måde at konstruere store Cayley-grafer på, inden resultater- ne i specialet summeres op i Kapitel 6.
SprogDansk
Udgivelsesdato2009
Antal sider88
Udgivende institutionInstitut for Matematiske Fag, Aalborg Universitet
ID: 17683070