中文摘要：

给定一个网络，转发指数问题是考虑满足网络中所有点对同时进行通讯时对网络的容量的最低的要求。而它的反问题是对于一个网络，在给定点（或者边）容量的条件下，网络中最多能有多少个点对同时进行通讯，使得其点（或者边）的负载不超过其容量。另外由于在网络的实际运行中，与同一个处理机直接相连的处理机(或连线)同时失灵的可能性实际上是很小的。那么在这种意义下，传统的连通度的概念就不能准确的刻画出网络的这一性质。所以为了更准确地度量网络的容错性，人们提出了图的超连通度和超边连通度的概念。本项目计划研究网络转发指数的反问题和超连通度（超边连通度）。考虑其NP困难性，设计合适的算法。并研究它们与其它参数的关系以及在Cayley图，线图，正则图，笛卡尔乘积图中它们的上下界。

结论摘要：

在本项目中,我们确定了增广立方体的点、边转发指数并首次研究网络（边）转发指数的反问题,考虑了一些限制条件下问题的复杂性,同时给出了相应的多项式近似算法。研究了笛卡儿乘积图的超连通度,给出了两个连通图的笛卡儿乘积的超连通度的下界,特别确定了最大连通图的超连通度,而且给出了笛卡儿乘积图具有超连通性的充分条件.作为推论,我们得到了n维超立方体的超连通度. 另外，本项目给出直径为d,阶数为n的树的wiener指数的最小值和次小值以及达到极值的图. 考虑围长为g阶数为n的单圈图最大的Merrifield－Simmons指数值和最小的Hosoya指数值,并刻画了达到极值的图类. 最后,我们也考虑了平衡立方体的边泛圈和哈密尔顿性. 本项目共完成论文9篇,其中发表6篇,接收2篇,均被SCI收录.