On cycles and independence in graphs [Elektronische Ressource] / Friedrich Regen. Gutachter: Jochen Harant ; Eberhard Triesch. Betreuer: Dieter Rautenbach

TECHNISCHE UNIVERSITÄT ILMENAUFAKULTÄT FÜR MATHEMATIK UND NATURWISSENSCHAFTENINSTITUT FÜR MATHEMATIKOn Cycles and Independence in GraphsDissertationzur Erlangung des akademischen GradesDr. rer. nat.eingereicht vonDipl.-Math. Friedrich RegenInstitut für MathematikTU IlmenauJuli 2010Betreuender Hochschullehrer: Univ.-Prof. Dr. rer. nat. habil. Dieter Rautenbach(Technische Universität Ilmenau)urn:nbn:de:gbv:ilm1-2010000384Meinen lieben ElternContents1 Introduction 31.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.1 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.2 Complexity Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Cycle Packings 92.1 Cycles of a given length . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.1.1 Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.1.2 Hardness of Approximation . . . . . . . . . . . . . . . . . . . . . . 152.2 Cyclomatic Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.2.1 Graphs G with (G) (G) =k . . . . . . . . . . . . . . . . . . . 21e2.2.2 G with (G) (G) =k . . . . . . . . . . . . . . . . . . . 29v3 Cycle Spectrum of Hamiltonian Graphs 373.1 Chords of a Hamiltonian Path . . . . . . . . . . . . . . . . . . . . . . . . . 393.1.1 Chords of length greater than three . . . .