题目： Minimum degree and sparse connected spanning subgraphs

主讲人：陈耀俊 教授

时间：2025年12月18日（星期四）14:00                

地点：#腾讯会议：317-532-085

主办单位：理学院

主讲人简介：

陈耀俊，南京大学数学学院教授，博士生导师，中国运筹学会理事。2000年7月在中国科学院数学与系统科学研究院获理学博士学位；2000.7-2002.6在南京大学数学系从事博士后研究工作；2003.9-2005.8在香港理工大学商学院物流系从事博士后研究工作；目前主要从事图中特定子图结构、Ramsey 问题、Turán问题、图的定向直径以及理论计算机与组合图论交叉问题的研究。先后主持国家自然科学基金项目多项，国家重点研发计划项目1项。在图论及理论计算机领域的主流期刊Journal of Combinatorial Theory, Series B, Journal of Graph Theory, IEEE/ACM Transactions on Networking, IEEE/OSA Journal of Lightwave Technology等专业学术杂志上发表研究论文百余篇。

摘要：

Let $G$ be a connected graph on $n$ vertices and at most $n(1+\epsilon)$ edges with bounded maximum degree, and $F$ a graph on $n$ vertices with minimum degree at least $n-k$, where $\epsilon$ is a constant depending on $k$.  In this paper, we prove that $F$ contains $G$ as a spanning subgraph provided $n\ge 6k^3$, by establishing tight bounds for the Ramsey number $r(G,K_{1,k})$, where $K_{1,k}$ is a star on $k+1$ vertices. Our result generalizes and refines the work of Erd\H{o}s, Faudree, Rousseau, and Schelp (JCT-B, 1982), who established the corresponding result for $G$ being a tree. Moreover, the tight bound for $r(G,tK_{1,k})$ is also obtained.