图上若干极值问题的研究

极值组合学处于组合数学与图论的交叉点上，很多计数问题本身研究的就是极值性质，而图由于其自身的规则及多样性提供了极好的研究对象。图论中的极值问题是很多学者感兴趣的热点。此项研究计划考查与图上α, τ, γ等类型的重要参数相关的若干极值类问题，这些问题有深刻的组合背景，近年来受到广泛关注。研究中结合传统的组合手段与近年来逐渐成熟的组合数学中的代数方法、概率方法等工具，这是一项有特色和有前景的研究工作。

组合数学中的许多计数问题其本身研究的是极值问题，而图由于其自身的规则性及多样性提供了极好的研究对象，同时计数往往虽不明显却隐含在问题的背后成为组合问题的实质。本课题主要针对图上参数问题、计数理论、极值图论、组合统计量等相互交织的问题开展了多方面的研究。在三年的课题时间内，我们在对与组合参数相关的图上组合极值问题的研究中取得了一些有科学意义的成果，包括：关于图上极大独立集，我们研究了若干重要图构形的极大独立多项式的单峰性、对数凸性和实根性，其中既用到组合方法，也用到概率方法等工具；针对当距离为2的任意一对顶点度数较大者有比范条件松一点的下界时，给出了与图的Hamilton性有关的刻画；得到一系列以q-二项式系数为系数的、关于q-调和数的恒等式，这是关于已知结果的q-模拟；得到有关图上全控制数的最新结果；根据降数至少为d统计量得到关于集合分拆的计数结果及组合统计量生成函数；关于图上Zagreb参数及其共轭参数得到两类推广的研究结果。针对困难的Tuza类问题，我们获得了一些关于该猜想的更广泛的理论推广框架，希望未来在已有工作基础上得到更加完善的理论。和以上工作有关的论文至今已经发表了5篇，其中两篇研究论文分别发表在较有影响力的重要刊物美国数学会进展、印度科学院进展（数学版）上。国内外学术合作交流与人才培养情况方面，在全国组合数学与图论大会等重要会议做邀请报告，取得了较好的学术交流效果，目前已指导1名硕士研究生毕业并有3名博士研究生在读。