Cycle decompositions of graphs and related problems

图的循环分解及相关问题

• 批准号: RGPIN-2016-04798
• 负责人: Sajna, Mateja
• 金额: $ 1.6万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=664109
• 关键词: Cycle; decompositions; graphs; related; problems

I have been fascinated by cycle decompositions of graphs for nearly 20 years. This vibrant research area on the intersection of graph theory and the theory of combinatorial designs has made breathtaking progress in the last few years. Nevertheless, some central problems remain open and have now become more accessible because of the recent advances. It is my long-term vision to make a significant and lasting contribution to this body of knowledge. *** A graph is said to be decomposed into cycles if its edges can be coloured so that the collection of all edges of any one colour forms a cycle. One of the central cycle decomposition problems, first introduced in 1967 in the context of scheduling, is the Oberwolfach Problem. It asks whether n participants at a conference can be seated at a number of round tables of specified sizes for k nights so that each pair of participants sit next to each other exactly once (assuming that the table sizes add up to n). In mathematical terms, the problem asks whether a complete graph can be decomposed into 2-factors (nights), each consisting of cycles (tables) of specified lengths.*** For this original version of the problem, many solutions are known for specific table sizes, however, the problem is in general still wide open. In this research plan, I am proposing to solve two new variants of the problem, primarily for equal table sizes. I also intend to investigate a version of the Oberwolfach Problem for complete symmetric equipartite digraphs, as well as study cycle decomposition problems from another point of view: using a technique called amalgamation-detachment to obtain new cycle decompositions of complete multipartite graphs from existing cycle decompositions of complete multigraphs.*** The second topic of my research proposal – eulerian properties of hypergraphs – is related to the first since a connected graph admits a decomposition into cycles (of lengths that cannot be predetermined) if and only if it admits an Euler tour (cyclic traversal of the graph that encounters each edge exactly once). It is well known that a graph admits an Euler tour if and only if every vertex has even degree. No similar results are known for hypergraphs; in fact, it has recently been shown that the analogous problem is NP-complete even for some restricted subclasses of hypergraphs. Moreover, there is more than one natural way to generalize the notion of an Euler tour to hypergraphs, and I propose to investigate various classes of hypergraphs with respect to these properties.*** The question of existence of a decomposition of a given graph into cycles of specified lengths is a fundamental open problem in graph theory, as is the question of existence of a (strict) Euler tour of a hypergraph. The two concepts are related, and both can be used to model certain types of scheduling. Thus, I anticipate that the proposed work will not only leave a significant mark on this research area, but also find practical applications.*****

近20年来，我一直对图的圈分解着迷。这一充满活力的研究领域是图论和组合设计理论的交集，在过去的几年里取得了惊人的进步。然而，由于最近的进展，一些核心问题仍然悬而未决，现在变得更容易解决。我的长期愿景是为这一知识体系做出重大而持久的贡献。*如果一个图的边可以被着色，使得任何一种颜色的所有边的集合形成一个圈，则称该图可分解成圈。中心循环分解问题之一是Oberwolfach问题，该问题于1967年在调度的背景下首次引入。它询问一次会议的n个与会者是否可以在k个晚上的多个指定大小的圆桌旁就座，以便每一对与会者恰好相邻就座一次(假设桌子大小加起来为n)。用数学术语来说，这个问题是问一个完整的图是否可以分解成两个因子(夜晚)，每个因子由指定长度的圈(表)组成。*对于这个问题的原始版本，对于特定的表大小，许多解决方案是已知的，然而，这个问题总体上仍然是开放的。在这项研究计划中，我建议解决这个问题的两个新变种，主要是针对相同的表格大小。我还打算研究完全对称等分有向图的Oberwolfach问题的一个版本，以及从另一个角度研究圈分解问题：使用一种称为合并-分离的技术从完全多图的现有圈分解中获得完全多部图的新的圈分解。*我的研究建议的第二个主题-超图的欧拉性质-与第一个主题有关，因为一个连通图允许分解成圈(长度不能预先确定的长度)当且仅当它允许欧拉圈(恰好遇到每条边一次的图的循环遍历)。众所周知，一个图允许欧拉环游当且仅当每个顶点都有偶度。对于超图没有类似的结果；事实上，最近的研究表明，即使对于超图的某些限制子类，类似的问题也是NP完全的。此外，将欧拉圈的概念推广到超图上有多种自然的方法，我建议研究关于这些性质的各种类型的超图。*将给定的图分解成指定长度的圈的存在性问题是图论中的一个基本开放问题，就像超图的(严格)欧拉圈的存在性问题一样。这两个概念是相关的，都可以用来对某些类型的调度进行建模。因此，我预计，拟议的工作不仅将在这一研究领域留下深刻的印记，而且还将找到实际应用。