首页   系科介绍   师资队伍   科研团队   本科生教学   研究生培养   招聘信息   联系我们

Previous Next
 
首页 >> 学术报告

Graph Partition with Average Degree Constraint

吴河辉 副研究员(国家青年千人,上海数学中心)
2017-9-21(周四)下午3:30-4:30  闵行校区数学楼 401
 
运筹与控制组学术报告

摘 要: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 $G_1$ and $G_2$ such that $G_1$ has minimum degree at least $s$ and $G_2$ 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)\geq (s+t+1)v(G)$, then there exist a vertex partition $(A,B)$ such that $||A|| \geq s |A|$, $||B|| \geq 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.
   
 
 
快捷链接 >>
 
系内资源 >>
 
教学园地 >>
 
  校外链接 >>    上海市核心数学与基础数学重点实验室    华师大-纽大联合数学中心    上海市数学会    中国数学会    美国数学会    欧洲数学会  
         
       Copyright 2012 All rights reserved    Department of Mathematics, East China Normal University    Tel: 86-21-54342609