群连通度与等密图和拟阵

The proposed research has two objectives. The first is to study the problems related to nowhere zero flows, the group connectivity (nonhomogeneous nowhere zero flows) and the mod (2s+1)-orientation of graphs and matroids.The second is to study the problems related to uniformly dense graphs and matroids. Our first goal is aiming at the Tutte's 3-flow conjecture and 5-flow conjecture, Jaeger et al's on group connectivity of graphs, and Jaeger's conjecture on mod (2s+1)-orientations of graphs. We approach these problems by investigate the graph decomposition, the structures of the minimal counterexamples, the obstacles for graphs to have such properties, and the reduction method related to these problems. We will also study the related dual problem, the group coloring problem of graphs, and the problem whether group connectivity of graphs is independent of the structure of the related abelian groups. The second objective of the proposed project will be targeted on Kajitani et al's conjecture on a characterization of uniformly dense networks and matroids by cyclic base ordering, Kajitani et al's conjecture on linear base ordering of block matroids, Cordovil and Moreira's conjectures on complementary bases of block matroids, and decompositions of graphs and matroids based on the subgraph density distributions. The decomposition will be used to approach the above-mentioned conjectures on matroid cyclic and linear base ordering, and on block matroids. The decomposition will also be used to study the problem decomposition of a graph into forests with additional degree constrains, including the NDT conjecture.

我们的研究计划有两个方面。第一个是研究图和拟阵的处处非零流，群连通度（非齐次处处非零流）和模(2s+1)-定向的问题。第二个是研究与等密图和拟阵相关的问题。我们的第一个目标是Tutte的3-流猜想和5-流猜想以及Jaeger关于图的模(2s+1)-定向的猜想。我们将通过研究把图分解为满足一定连通性和奇偶性条件的子图，最小反例的结构，以及约简的方法处理这类问题。我们也将研究他们的对偶问题，图的群染色问题以及图的群连通度是否与相应的阿贝尔群的结构无关的问题。我们的第二个目标是Kajitani等人提出的对等密图和拟阵循环基排序以及线性基排序的猜想，Cordovil和Moreira的关于团拟阵的互补基的猜想以及图与拟阵按密度进行的分解。对图和拟阵的分解将成为我们研究上述猜想的主要方法，同时我们也会应用这种方法处理将图分解为满足一定度条件的森林的问题，包括九龙树猜想。

本项目主要对群连通度，等密图和超欧拉图的性质进行了研究。群连通度方面，主要研究了图的模(2s+1)定向问题。我们证明了在有n个顶点的简单图G中，如果任意两个不相邻的顶点的度和都大于等于一个关于n的线性表达式，则G是强Z_{2s+1}-连通的或者G的Z_{2s+1}-约化图在一个有限的非强Z_{2s+1}-连通图的集合中。另外，我们证明了一个连通图有模(2s+1)-定向的充分必要条件是它是一个(2s+1)-正则二部图的收缩。我们还证明了每个(4s-1)-边连通的串并联图是强Z_{2s+1}-连通的，并且每个简单4p-连通的弦图是强Z_{2s+1}-连通的。.等密图和等密有向图方面，我们证明了一个有向图D是k弧强连通的当且仅当对于D中的任意顶点v，D中都存在k个以v为根的弧不相交的支撑有向树。并给出了有向图D是等密有向图的几个等价条件。还研究了满足特殊参数条件的图的性质。我们利用Mader和Matula提出了最大子图边连通度的概念，给出了k-极大图和有n个顶点的边连通度等于边不交支撑树数目的极小图的刻画。关于超欧拉图，我们定义了图G的超欧拉宽度。把可缩叠图的概念推广到s-可缩叠图并且找到了一个新的约化方法来研究图的超欧拉宽度。并且证明了K_{3,3}是超欧拉宽度小于3的最小的3-边连通图。我们也对具有较小匹配数的超欧拉图的性质进行了研究。并且证明了每个独立数不大于3的2-连通无爪图都是哈密顿的，除了一些已经刻画好的例外情况。