搜索:
 
 当前位置:>首页 -> 学术报告
9-08吴文俊数学重点实验室组合图论系列讲座之一百零七【李鹏】
报告题目:Use Topological Method to Partition a Graph into Connected Pieces

报告人:Peng Li, Chongqing University of Technology

报告时间: 9月8日  周五 下午4:30-5:30

报告地点:1218

摘要:


Let G be a simple graph with n vertices. Suppose 1 ≤ k ≤ n. We say G is k − good if for any subset{x1, x2, . . . , xk} of V (G) and any nonnegative integers n1, n2, . . . , nk with n1 + n2 + . . . + nk = n,we can always partition G to k connected pieces, say {G1, G2, . . . , Gk}, such that for every i ∈ [k], we have xi ∈ V (Gi) and |V (Gi)| = ni. In his paper Topological Methods in Combinatorics, Lovaszuse topological method to prove that any k-connected graph G is k − good. We use combinatorial method to prove that any k-connected graph G is k − good when k=2,3. We are interest in finding a combinatorial method to prove that any k-connected graph G is k − good for any integer k.
REFERENCES
[1] S.R. Arikati, C.P. Rangan, Linear algorithm for optimal path cover problem on interval
graphs, Information Processing Letters, 35 (1990), pp. 149–153.
  科大主页 | 国家数学与交叉科学中心(合肥) | 中科院吴文俊数学重点实验室 |
中科院数学与系统科学研究院 | 北京国际数学研究中心 | 安徽省数学会