Cycle spectra of graphs
Dissertation
Authors
Müttel, Janina
Faculties
Fakultät für Mathematik und WirtschaftswissenschaftenAbstract
This thesis contains several new results about cycle spectra of graphs. The cycle spectrum of a graph G is the set of lengths of cycles in G. We focus on conditions which imply a rich cycle spectrum. We show a lower bound for the size of the cycle spectrum of cubic Hamiltonian graphs that do not contain a fixed subdivision of a claw as an induced subgraph. Furthermore, we consider cycle spectra in squares of graphs. We give a new shorter proof for a theorem of Fleischner which is an essential tool in this context. For a connected graph G, we also find a lower bound on the circumference of the square of G, which implies a bound for the size of the cycle spectrum of the square of G. Finally, we prove new Ramsey-type results about cycle spectra: We consider edge-colored complete graphs and investigate the set of lengths of cycles containing only edges of certain subsets of the colors.
Date created
2013
Subject Headings
Hamilton-Kreis [GND]Ramsey-Zahl [GND]
Hamiltonian graph theory [LCSH]
Ramsey numbers [LCSH]
Keywords
Caterpillar; Circumference; Cycle length; Cycle spectrum; Fleischner´s theorem; Hamiltonian cycle; Pancyclic graphs; Square of a graph; Subdivided clawDewey Decimal Group
DDC 510 / MathematicsMetadata
Show full item recordCitation example
Müttel, Janina (2013): Cycle spectra of graphs. Open Access Repositorium der Universität Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-2549