# 学术报告

 东南大学 林文松教授：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项。已发表学术论文六十余篇。 【关闭窗口】