构造给定度序列的高阶连通图

In 1983, Harary proposed the concept of conditional connectivity, which is not only the integration of a variety of classical concepts of connectivity, but also yields a large number of new concepts of connectivity that having profound background in the design of optimization network, such as super vertex (edge) connectedness and restricted vertex (edge) connectivity and so on. For degree sequence and connected property of graph, there are usually two kinds of problems to be studied: one is forcible problem, that is, all graphs with the given degree sequence must have the connected property; the other is the potential problem, that is, there is a graph with the given degree sequence having the connected property. In this project, we will study degree sequence with super vertex (edge) connectedness and optimally restricted edge connectedness by using the theory and methods of optimization theory and graph theory. Specifically, we will study the potentially super vertex (edge) connected and optimally restricted edge connected graphical sequence, multi-graphical sequence and bipartite graphical sequence. Furthermore, we will consider the potentially super vertex (edge) connected and optimally restricted edge connected graphical sequence, multi-graphical sequence and bipartite graphical sequence with small diameter.

Harary于1983年提出了条件连通度的概念，它不仅统合了各类经典连通性概念，而且由此引发了大量新的在网络优化设计中具有深刻背景的连通性概念，如超点（边）连通性和限制性点（边）连通度等。对于度序列和图的连通性质，一般有两类问题需要研究：一类是强制性问题，即对所有满足给定度序列的图，都要满足给定的图的连通性质；另一类是存在性问题，也就是找到一个满足给定度序列的图，使得它满足给定的图的连通性质。本项目将综合应用组合优化和图论的理论和方法研究度序列和图的超点（边）连通性质、最优限制边连通性质的存在性问题。具体地说，我们将研究存在超点（边）连通、最优限制边连通的图序列、重图序列和二部图序列。更近一步，我们将考虑限定直径的存在超点（边）连通、最优限制边连通的图序列、重图序列和二部图序列。

图的各类条件连通度，如超（点）边连通性和限制性（点）边连通度等，是衡量网络可靠性的重要参数。对于度序列和图的连通性质，如何找到一个满足给定度序列的图使得它满足给定的图的连通性质，是属于度序列的存在性问题。本项目综合应用组合优化和图论的理论和方法研究图的度序列的连通性存在问题和图的各类条件连通度。我们得到如下主要结果：刻画了重图序列的超边连通性质；证明了连通的半点传递有向图是最大点连通的；笛卡尔积图k-限制点连通的相关结果（1<k<5）；笛卡尔积图圈点连通度的相关结果；保持连通度的子树的研究结果。