中图分类：O157.5

学科分类：110.77

成果类别：软科学

研究起止时间：2005-01～2007-12

评价形式：结题

本课题来源于国家自然科学基金项目《极值图论及其相关课题的研究》批准号：10401010,执行年限：2005年1月～2007年12月。本课题主要研究图论中当今国际同行关注的几个活跃问题：极值图论中的一些经典Turán数在度序列中的变形,蕴含或者强迫图论性质P（或者子图H）的可图序列刻划,图的Pebbling数以及Erds-Sós猜想,图的容错直径和宽直径等。本课题共发表文章17篇（含待发1篇）,其中已被SCI收录11篇,EI收录1篇。证明了Mubayi在[J.Graph Theory, 34（2000）20～29]中提出的关于使得Erdos-Jacobson-Lehel猜想成立的门槛数猜想,从而完全解决了Erds等人提出的确定完全图的经典Turán 数在度序列中的变形值问题。证明了Yin-Li-Mao在[Ars Combinatoria,74（2005）151-159]中提出的关于完全图减去一条边的Turán数在度序列中的变形值猜想。证明了Lai C.H.在[Discrete Mathematics and Theoretical Computer Science,7（2005）75～81]中提出的关于完全三部图的Turán 数在度序列中的变形值猜想。解决了Erds-Sós猜想在度序列中的变形问题,这是对Erds-Sós猜想的一个有力支持。对于较大的n,解决了完全多部图和广义友谊图的经典Turán数在度序列中的变形值问题以及其它的一些Turán数在度序列中的变形值问题。给出了蕴含完全图可图序列两个简单的充分条件,从而推广了Li等人在[Science in China Ser.A,41（1998）510～520]中给出的一个充分条件。研究了蕴含完全二部图、圈与泛圈的可图序列刻划。验证了广义友谊图的Pebbling数及其Graham猜想。得到了2连通图（网络）中宽直径关于容错直径的最好上界。刻划了满足Ore条件的所有Z3连通图。这些结果的理论证明具有相当难度,并已受到了国内外同行的广泛关注,推进了极值图论、图的度序列和连通图理论的研究,将对图论和理论计算机科学具有重要理论意义和应用背景。