东南大学林文松教授学术报告

时间:2021-05-18浏览:51设置

报告题目:On maximum P3-packing in claw-free subcubic graphs

报告人:林文松 东南大学 教授

报告时间:202152214:30-15:30

报告地点:数计学院20306

 

摘要:Let P3 denote the path on three vertices. A P3-packing of a given graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is isomorphic to P3. The maximum P3-packing problem is to and a P3-packing of a given graph G which contains the maximum number of vertices of G. The perfect P3-packing problem is to decide whether a graph G has a P3-packing that covers all vertices of G. Kelmans [A. Kelmans, Packing 3-vertex paths in claw-free graphs and related topics, Discrete Applied Mathematics 159(2011) 112-127] proposed the following problem: Is the P3-packing problem NP-hard in the class of claw-free graphs? In this paper, we solve the problem by proving that the perfect P3-packing problem in claw-free cubic planar graphs is NP-complete. In addition, we show that for any connected claw-free cubic graph (resp. (2; 3)-regular graph, subcubic graph) G with v(G) 14 (resp. v(G) 8, v(G) 3), the maximum P3-packing of G covers at least  (9v(G)-6)/10 (resp. (6v(G)-6)/7, (3v(G)-6)/4) vertices, where v(G) denotes the order of G, and the bound is sharp.

The proofs imply polynomial-time algorithms.

 

邀请人:朱绪鼎


浙江师范大学离散数学研究中心版权所有 © 2018-2028
地址:浙江省金华市迎宾大道688号21幢 邮政编码:321004
联系电话:0579-82282629   电子邮箱:jcsx@zjnu.cn    管理登陆