连通图中的可收缩子图问题

图的连通性是图论研究的核心课题之一。Tutte是此领域的开创者之一，并做出了许多奠基性的工作。过去二十多年来，国际著名图论学家Robertson和Seymour发展了图子式理论，该理论在计算机科学和其他数学领域有着广泛且重要的应用。收缩边（与收缩连通子图）是图子式理论的主要思路。本项目旨在对k连通图（特别是5连通图）找到好的简化技巧。例如：在k连通图中是否存在可收缩（连通）子图，在所期望的可收缩（连通）子图不存在时，能否得到有用的结构信息。我们计划研究并刻画一些特殊图类，如临界k连通图等。另外，我们将深入研究收缩子图方法在Malkevitch关于4连通平面图具有泛圈性的猜想、图论算法以及网络可靠性等问题中的应用。这些问题都是图的连通性研究中的前沿课题，对这些问题进行系统的研究，将有助于图的连通性理论的进一步发展。

图的连通性理论是图论研究的核心课题之一，在计算机科学和其他数学领域有着广泛且重要的应用，近年来吸引了国内外众多图论学者的研究兴趣。本项目只要针对k连通图中可收缩子图的存在性问题展开了深入研究。首先，我们证明了如果一个k连通图不包含导出4-圈和某些特殊图作为子图，则一定含有一个可收缩三角形或者一条有3个顶点的可收缩路，改进了Fujita和Kawarabayashi的结果。其次，我们研究了临界k连通图的刻画问题，得到了关于临界k连通图的一些有用的结构信息。此外，我们刻画了给定独立数时周长达到最小的所有k连通图，从而回答了著名图论学家Saito提出的一个问题。这些问题都是图的连通性研究中的前沿课题，对这些问题进行系统的研究，将有助于图的连通性理论的进一步发展。