图的广义（边）连通度若干问题的研究

Connectivity is one of the most basic concepts of graph-theoretic subjects. There are many elegant and powerful results on connectivity in graph theory. The generalized connectivity of a graph G, introduced by Chartrand et al., is a natural and nice generalization of the concept of (vertex-)connectivity. As a natural counterpart of the generalized connectivity, recently, X. Li et al. introduced the concept of generalized edge-connectivity, which is a generalization of the concept of edge-connectivity. The generalized (edge-)connectivity is related to some important problems in graph theory, for example, the Spanning Tree Packing Problem and the Steiner Tree Packing Problem, and thus is attracting more and more attentions. . This project will study the complexity of some problems on the generalized (edge-)connectivity of a graph, and will try to give a polynomial-time algorithm to determine the generalized edge-connectivity or prove the problem is NP-hard; The project will start with characterizing " the graph which is minimal for κ_{3}=2 ", and then characterize graphs with κ_{3}=1, λ_{3}=1, κ_{3}=2 or λ_{3}=2; This project will study the necessary and sufficient condition to make the inequality κ_{k}≤κ_{k-1} hold for a graph, where 3≤k≤n. Finally the project will study the structures of the Cayley graph, the symmetric graph and so on, and will try to give the exact value of the generalized (edge-)connectivity of these special classes of graphs.

连通度是图论学科中最基本的概念之一，关于连通度，已经有了许多优美、强大的结论。图的广义连通度，是由Chartrand等人提出的，它是连通度概念的一个自然、漂亮的推广。类似于广义连通度，最近李学良教授等又提出了广义边连通度的概念，它是边连通度概念的一个推广。广义（边）连通度与图论中的一些重要问题，例如生成树打包问题、斯坦纳树打包问题等有着紧密的联系，已经吸引了越来越多的研究者的关注和兴趣。 . 本项目将研究广义（边）连通度相关问题的复杂性，力争给出确定图的广义边连通度的多项式时间算法或证明是NP-困难的；从刻画"对κ_{3}=2是极小的图"入手，刻画κ_{3}，λ_{3}等于1或2的极图；研究不等式κ_{k}≤κ_{k-1}成立的充分条件甚至是充要条件，其中3≤k≤n；通过研究凯莱图，对称图等图类的结构性质，努力确定这些特殊图类的广义（边）连通度的精确值。

连通度是图论学科中最基本的概念之一，关于连通度，已经有了许多优美、强大的结论。图的广义（边）连通度是（边）连通度概念的一个自然、漂亮的推广。广义（边）连通度不仅与图论中的一些重要问题，例如生成树打包问题、斯坦纳树打包问题等有着紧密的联系，而且在实际生活中也有着重要的应用。因此，对广义（边）连通度的研究是非常有意义的。.本项目在国家自然科学基金委的资助下，经项目组成员一致努力，完成了项目预期的各项主要目标。目前，项目组得到的主要结果有：.(1)我们研究了对二部图判定rc(G)(rvc(G))的复杂性问题。.(2)我们研究了极小2-连通且κ_{3}=2的图的结构。另外，我们得到了一些可逆操作，这些操作均保持了“κ_{3}=2”，这对研究其它问题有重要意义及作用。.(3)我们研究了由星生成的凯莱图Sn和由路生成的凯莱图Bn的广义3-连通度，得到Sn和Bn的广义3-连通度均为n-1。.(4)我们对社交网络相关问题进行了研究。提出了以影响-距离为基础的影响者检测问题，并提供了一个3-近似算法。其次我们提出了用最大似然估计法检测影响者，并证明了对有向无圈图可以在多项式时间内得到最优的MLE。