Cycle Spectra of Graphs

图的循环谱

• 批准号: 161475137
• 负责人: Professor Dr. Dieter Rautenbach
• 金额: --
• 依托单位: Institut für Optimierung und Operations Research
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2009
• 资助国家: 德国
• 起止时间: 2008-12-31 至 2013-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/161475137?language=en
• 关键词: Cycle; Spectra; 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.

循环的概念是图论中最重要和最基本的概念之一。图中周期的许多方面已经受到了广泛的关注，近年来出现了一些新的和具有挑战性的研究方向，即所谓的图的周期谱，即图的周期长度的集合。我们的研究重点将放在丰富循环谱的充要条件上，即存在不同长度的循环的充要条件。这类经典的充分条件一般在相当密集的图中成立，稀疏图的循环谱值得进一步研究。富循环谱的必要条件以相反的方式更方便地研究：缺乏富循环谱或某些周期长度对其他图理论性质的影响是什么？最近，人们设计了强大的（概率）方法来研究循环长度与同态、着色、独立集或支配集之间的相互作用。

项目成果

Cycles Avoiding a Color in Colorful Graphs

避免彩色图表中的颜色的循环

• DOI: 10.1002/jgt.21879
• 发表时间: 2016
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: D. Meierling;J. Müttel;D. Rautenbach
• 通讯作者: D. Rautenbach

The Erdős–Pósa Property for Long Circuits

ErdÅsâPósa 的长电路特性

• DOI: 10.1002/jgt.21769
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: D. Meierling;D. Rautenbach;T. Sasse
• 通讯作者: T. Sasse

Cycle Lengths of Hamiltonian $$P_\ell $$Pℓ-free Graphs

哈密​​顿量 $$P_ell $$Pâ-free 图的周期长度

• DOI: 10.1007/s00373-014-1494-1
• 发表时间: 2015
• 期刊: Graphs and Combinatorics
• 影响因子: 0.7
• 作者: D. Meierling;D. Rautenbach
• 通讯作者: D. Rautenbach