Optimally $(s,t)$-supereulerian
科研大讨论系列报告
报告题目(Title)：Optimally $(s,t)$-supereulerian
报告人(Speaker)：赖虹建教授 （美国西弗吉尼亚大学）
地点(Place)：后主楼1220
时间(Time)：2024 年 7 月 12 日（周五） 16:00--17:00
邀请人(Inviter)：徐敏
报告摘要
For two integers s≥0,t≥0, a graph G is (s,t)-supereulerian, if for any disjoint subsets X,Y⊂E(G), with X≤s,Y≤t, G has a spanning eulerian subgraph H with X⊂E(H) and Y∩E(H)=∅. Pulleyblank in [J. Graph Theory, 3 (1979) 309-310] proved that even within planar graphs, determining if a graph G is (0,0)-supereulerian is NP-complete. Xiong et al. in [Polynomially determine if a graph is (s,3)-supereulerian, Discrete Mathematics, 344 (2021) 112601] identified a function j0(s,t) such that every (s,t)-supereulerian graph must have edge connectivity at least j0(s,t). Examples have been found that having edge connectivity at least j0(s,t) is not sufficient to warrant the graph to be (s,t)-supereulerian. A graph family S is optimally (s,t)-supereulerian if for every pair of given non-negative integers (s,t), a graph G∈Sis (s,t)-supereulerian if and only if κ'G≥j0(s,t). Hence the (s,t)-supereulerian problem in such a graph family can be solved in polynomial time with minimally required edge-connectivity. In this research, we prove that the family of all squares of graphs of order at least 5 is optimally (s,t)-supereulerian.
主讲人简介
美国西弗吉尼亚大学数学系终身教授，博士生导师，国际知名的图论专家，主要研究领域包括图论中的欧拉子图、哈密尔顿性问题、整数流以及图论中的染色和连通度问题，出版学术著作两部，发表学术论文300余篇。完成了两部专著：由克鲁亚学术出版社（Kluwer Academic Publishing）出版的“图与组合学中的矩阵论”和由高等教育出版社出版的“拟阵论”。1996年获学院最优科研奖，2006年获学院最优教师奖和全校最优教师奖，成为西弗吉尼亚大学历史上第一个获此荣誉的华裔教授。曾主持过1996年由美国国家自然科学基金会资助的纪念凯特林（Catlin）教授的欧拉图问题专题会议，2008年由美国国家自然科学基金会资助的第46届美国中西部图论会议，以及2018年的第59届美国中西部图论会议。曾任Discrete Mathematics杂志客座编辑，现担任Applied Mathematics，Graphs and Combinatorics，Congressus Numerantium等多个杂志的编辑。
