整数流和圈覆盖问题研究

Integer flow and cycle cover of graphs are two relative and interactive research areas of graph theory. Tutte's 3-Flow Conjecture and 5-Flow Conjecture are two kernel problems of integer flow area. Shortest Cycle Cover Conjecture is an important conjecture of cycle cover area. Those conjectures are widely studied and and have strong connections to other conjectures in graph theory, such as, the Jeager's Petersen Flow Conjecture and the Circuit Double Cover Conjecture. In this project, we focus on 3-Flow Conjecture, 5-Flow Conjecture and Shortest Cycle Cover Conjecture ,and also concern about some related conjectures and problems. We want to approach 3-Flow Conjecture and 5-Flow Conjecture by the way from decreasing the flow values of Jaeger's 4-Flow Theorem and Seymour's 6-Flow Theorem respectively, obtain some new bounds for shortest cycle cover of graphs and signed graphs, and determine if there exists a constant k such that every signed graph has a cycle cover covering each edge exactly k-times. The improvements or solutions of these problems will improve the development of graph theory.

图论中的整数流和圈覆盖是图论中两个既相互交叉又互相促进的研究领域。Tutte的3-流猜想和5-流猜想是整数流中的核心问题。最短圈覆盖猜想是圈覆盖领域中的一个重要猜想。这几个猜想已经被广泛深入地研究，并与很多其他图论猜想有很强的关联，比如圆流猜想、Z_3-群连通猜想、Z_5-群连通猜想、Petersen-流猜想和双圈覆盖猜想等。本项目将紧紧围绕3-流猜想、5-流猜想和最短圈覆盖猜想开展研究，同时兼顾和这些猜想密切相关的其他猜想和问题。我们将主要研究从降低Jaeger的4-流定理和Seymour的6-流定理中的流值的角度分别逼近3-流猜想和5-流猜想，给出图以及符号图的最短圈覆盖的新上界，确定是否存在一个常数k，使得符号图都有圈覆盖，覆盖每条边刚好k次。这些问题的进展和解决将对图论理论的完善和发展具有重要意义。

本项目研究图论中的整数流和圈覆盖这两大领域，主要围绕Tutte的整数流猜想、Jaeger的圆流猜想，以及符号图的最短全覆盖猜想研究相关问题。我们证明了(6p+2)-边连通图的流值严格小于(2+1/p)，(6p-2)-边连通图的流值不大于(2+2/(2p-1))；给出了任意6-边连通图都有严格小于3的流值的猜想并在几大类常见的6-边连通图类上验证猜想成立；刻画了其结构和性质与3-流猜想息息相关的3-流临界图的边数的上下界相关性质；给出了有流的符号图的不超过19/6倍边数的最短圈覆盖并且在偶数负边下可进一步将该倍数降低到8/3。 相关结果分别发表在JCTB、DM、SIAMDM、EJC等图论专业期刊。