当前位置: 首页 >> 新闻中心 >> 学术报告 >> 正文

学术报告

东南大学 林文松教授:On maximum $P_3$-packing in claw-free subcubic graphs
2021-06-03 16:20  

 

报告题目On maximum $P_3$-packing in claw-free subcubic graphs

 

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

 

报告时间2021.6.3 9:30-10:30

 

地点:南山校区6号楼407

 

报告摘要:Let $P_3$ denote the path on three vertices. A $P_3$-packing of a given graph

 

$G$ is a collection of vertex-disjoint subgraphs of $G$ in which each subgraph is isomorphic

 

to $P_3$. The maximum $P_3$-packing problem is to find a $P_3$-packing of a given graph

 

$G$ which contains the maximum number of vertices of $G$. The perfect $P_3$-packing

 

problem is to decide whether a graph $G$ has a $P_3$-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

 

$P_3$-packing problem NP-hard in the class of claw-free graphs? In this paper, we solve the

 

problem by proving that the perfect $P_3$-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)\ge 14$ (resp. $v(G)\ge 8$, $v(G)\ge

 

3$), the maximum $P_3$-packing of $G$ covers at least $\lceil \frac{9v(G)-6}{10} \rceil$ (resp.

 

$\lceil \frac{6v(G)-6}{7} \rceil$, $\lceil \frac{3v(G)-6}{4} \rceil$) vertices, where $v(G)$ denotes

 

the order of $G$, and the bound is sharp. The proofs imply polynomial-time algorithms.

 

个人简介:林文松,东南大学数学学院教授、博士生导师。从事运筹学方面的教学和科研工作。主要研究方向:图论及其应用、网络最优化。先后主持国家自然科学基金面上项目3项,主持江苏省自然科学基金面上项目1项。已发表学术论文六十余篇。

 

关闭窗口

联系地址:绍兴市城南大道900号 | 邮编:312000 | 电话:0575-88341001

版权所有:绍兴文理学院数理信息学院 | 技术支持:海马科技