蕴含P-可图序列及其算法研究

We will investigate the following several active problems in graph theory with applications which are concerned (or interested) by international counterparts at present: the characterization of potentially maximally edge connected (super edge connected) graphic sequence and the algorithm of its realization、the strongest monotone degree condition of forcibly k-edge-connected (bipartite) graphic sequence、the characterization of potentially m-restricted edge connected graphic sequence and the algorithm of its realization、the extremal problem of potentially A-connected bipartite graphic sequence (A is an (additive) abelian group with identity 0)、the characterization of potentially A-connected graphic sequence and its related problem、two extensions of potentially complete bipartite graph bipartite graphic sequence and the algorithm of its realization、the extremal problem of potentially k-tree graphic sequence and its related problem, etc. These results will improve the research and development of potentially P-graphic sequence and its algorithm、m-restricted edge connectivity of graphs、A-connected graphs and k-trees, and also will be important to graph theory and theoretical computer science in theoretical significances and application prospects.

研究图论及其应用中当今国际同行关注的几个活跃问题：蕴含极大边连通（超级边连通）可图序列的刻划及其实现的算法、强迫k-边连通（二部）可图序列的最强单调度条件、蕴含m限制边连通可图序列的刻划及其实现的算法、蕴含A-连通二部可图序列的极值问题(其中A是一个（可加的）阿贝尔群且具有单位元0)、蕴含A-连通可图序列的刻划问题及其相关问题、蕴含完全二部图的二部可图序列的两个推广及其实现的算法、蕴含k树可图序列的极值问题及其相关问题等，以推进蕴含P-可图序列及其算法、图的m限制边连通度、A-连通图以及k树的研究和发展，将对图论和理论计算机科学具有重要理论意义和应用前景。

本项目主要研究图论中国际同行关注的几个活跃问题：度序列与图性质（如泛圈性，k（限制）-（极大）边连通性，可图序列的Packing性等）的问题，蕴含A-连通二部可图序列的极值问题，蕴含k树-可图序列的极值问题，（蕴含Ks,t）二部可图（区间）序列的条件及二部图的二部劈性，Lourdusamy猜想和图的最优Pebbling数,图论算法的一些应用等。四年来，本基金项目共发表期刊论文23篇，其中SCI收录21篇、EI收录2篇。刻划了蕴含泛圈-几乎正则可图序列、得到了蕴含C3,…,Cl可图序列的一个Dirac型条件、得到了可图序列的一个新的充分的度条件使得它是强迫（蕴含）k（限制）-（极大）边连通可图的、得到了可图序列Packing的一个充分条件、研究了图G与完全劈图的蕴含Ramsey数之值的确定、对于A=Z3或者奇的|A|≧5, 完全确定了蕴含A-连通二部可图序列的最小度和的极值值、给出了蕴含k树-可图序列的极值问题的一个较好的近似解、给出了二部可图对的一个简单的充分条件、刻划了L使得L是蕴含Ks,t-二部可图的、研究了二部图的二部劈性、证明了Lourdusamy猜想对于几乎完全图的乘积和广义有谊图的乘积是成立的、确定了纺锤图(spindle graphs)的最优Pebbling数、研究了图论算法的一些应用等等。这些结果推进了图的度序列、图的k-边连通性、图的A-连通性以及k-树的研究，将对图论和理论计算机科学具有重要理论意义和应用背景。