Cycle Spectra of Graphs

点击翻译按钮获取中文摘要

One of the most important and basic graph theoretical concepts is the notion of a cycle. While many aspects of cycles in graphs have already received much attention, several new and challenging research directions concerning the so-called cycle spectrum of a graph, dened as the set of its cycle lengths, emerged during recent years. The focus of our research will be on necessary and sufficient conditions which imply a rich cycle spectrum, i.e. which imply the existence of cycles of different lengths. Classical sufficient conditions of this type typically hold in rather dense graphs and the cycle spectrum of sparse graphs deserves further investigation. Necessary conditions for a rich cycle spectrum are more conveniently studied in contraposition: What is the impact of the absence of a rich cycle spectrum or of certain cycle lengths on other graph theoretical properties? Recently, powerful (probabilistic) methods have been devised to study the interplay between cycle lengths on the one hand and for instance homomorphisms, colourings, independent sets or dominating sets on the other hand.