Grafer med maksimal grad d, diameter k og lille defekt
Oversat titel
Graphs with maximal degree d, diameter k and small defect
Forfatter
Semester
4. semester
Uddannelse
Udgivelsesår
2009
Afleveret
2009-06-09
Antal sider
88
Abstract
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.