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

项目名称： 图的广义（边）连通度若干问题的研究

项目编号： No.11301480

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 李莎莎

作者单位： 浙江大学宁波理工学院

项目金额： 22万元

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

中文关键词： 广义连通度；斯坦纳树；计算复杂性；极图；凯莱图

英文摘要： 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, t

英文关键词： generalized connectivity；Steiner Tree；computational complexity；extremal graph；Cayley graph