网站首页  |  实验室概况  |  研究团队  |  新闻中心  |  学术交流  |  学术报告  |  实验室年报  |  联系我们

 
 
  当前位置:首页 -> 学术报告
吴文俊数学重点实验室组合图论系列讲座之八十九【吴河辉】
报告人:吴河辉 复旦大学/上海数学中心
报告题目:Graph Partition with Average Degree Constraint
报告时间:周5,下午3-4点
报告地点:1218
摘要: A classical result showed by Stiebitz in 1996 stated that a graph with minimum degree s+t+1 can be decomposed into vertex disjoint subgraphs G1 and G2 such that G1 has minimum degree at least s and G2 has minimum degree at least t. Motivated by this result, Norin raised the conjecture that for any nonnegative real number s and t, such that if G is a non-null graph with e(G) ≥ (s + t + 1)v(G), then there exist a vertex partition (A, B) such that ||A|| ≥ s|A|, ||B|| ≥ t|B|. Recently, we prove the weaker version of the conjecture, that there exists two vertex set A and B that satisfied the required average degree constraint. This is joint work with Yan Wang at Georgia Institute of Technology. 
中国科学院吴文俊数学重点实验室