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.