Cycle spectra of graphs
Dissertation
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
[GND]: Hamilton-Kreis | Ramsey-Zahl[LCSH]: Hamiltonian graph theory | Ramsey numbers
[Free subject headings]: Caterpillar | Circumference | Cycle length | Cycle spectrum | Fleischner´s theorem | Hamiltonian cycle | Pancyclic graphs | Square of a graph | Subdivided claw
[DDC subject group]: DDC 510 / Mathematics
Metadata
Show full item recordDOI & citation
Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-2549
Müttel, Janina (2013): Cycle spectra of graphs. Open Access Repositorium der Universität Ulm und Technischen Hochschule Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-2549
Citation formatter >