图Ramsey数及编码理论中相关的极值问题

在本项目中，首次利用图的边数与围长之间的关系, 图的边数与泛圈性之间的关系以及一个图与其补图围长之间的关系，完全证明了Surahmat 等人关于大圈对偶阶数轮的猜想，基本上解决了Surahmat 等人关于大圈对奇阶数轮的猜想，为这一类问题的研究提供了全新的思路。基于此种方法，本项目还确定了其他几类圈-轮型Ramsey数的值。证明了轮-四圈Ramsey函数与另一个备受关注的困难问题星-四圈Ramsey函数是相等的。在平面图方面，确定了不含四圈平面图最大可能边数并考虑了相应的极值结构，计算了几乎所有的圈-轮平面Ramsey数以及完全图-树平面Ramsey数，后者是与通常Ramsey数经典结果Chvátal定理相应的平面Ramsey数形式；证实了Sun等人有关四圈-完全图猜想的一个特例；证明了当图的补图是平面图时，Erdös-Sós有关图的边数与各阶树存在性之间关系的著名猜想是成立的。研究了按照谱半径对树的排序问题，确定了第8-10棵具有最小谱半径的树。给出了赋权图的谱半径和拉普拉斯谱半径的若干下界，并刻画了达到下界的图的结构。借助图的邻接矩阵谱半径，分别给出了一个二部图具有Hamilton圈和一般图具有Hamilton路的新的充分条件。利用图的结构性质，结合代数方法，分别给出了一个图是k-边连通的拉普拉斯谱条件和无符号拉普拉斯谱条件，也分别得到了与图的围长有关的拉普拉斯谱条件，推广了一些已知结论。另外，本项目还研究Burnt Pancake图的条件边容错哈密尔顿性，证明了该图类是(2n-5)-条件边容错哈密尔顿图。