Grafer med maksimal grad d, diameter k og lille defekt

Sillasen, Anita Abildgaard

4. semester

Matematik, Kandidat

2009

2009-06-09

88 pages

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.

Download
Vis denne rapport i AAU Studenterprojekter