Cycle spectra of graphs

Abstract

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.