报 告 人：林文松 教授
报告题目：Three-vertex path packing problemin claw-free subcubic graphs
报告时间：2022年1月6日（周四）上午8:30-11:30
报告地点：腾讯会议（ID：610179523）
主办单位：数学与统计学院、科学技术研究院
报告人简介：
林文松，东南大学教授，博士生导师。1986至1993年就读于山东大学数学系运筹学专业，获理学学士学位和理学硕士学位。2001至2004年就读于香港浸会大学数学系，获博士学位。1993年至今在东南大学数学系任教。长期从事运筹学方面的教学和科研工作。先后主讲的本科生和研究生的课程有：图论及其应用、组合最优化、最优化理论与方法，离散数学、组合数学、运筹学、代数图论、随机图、现代图论等。主要研究方向：图论及其应用、网络最优化等。先后主持完成国家自然科学基金面上项目2项，江苏省自然科学基金面上项目1项，主持在研国家自然科学基金面上项目1项。已发表学术论文六十余篇。
报告摘要：
Let P3 denote the path on three vertices. AP3-packing of a given graph G is a collection of vertex-disjointsubgraphs of G in which each subgraph is isomorphic to P3. Themaximum P3-packing problem is to find a P3-packing of agiven graph G which contains the maximum number of vertices of G. The perfect P3-packingproblem is to decide whether a graph G has a P3-packing that coversall vertices of G. Kelmans [A. Kelmans, Packing 3-vertex paths in claw-freegraphs and related topics, Discrete Applied Mathematics 159(2011) 112-127] proposedthe following problem: Is the P3-packing problem NP-hard in theclass of claw-free graphs? In this paper, we solve the problem by proving thatthe perfect P3-packing problem in claw-free cubic planar graphs isNP-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-packingof 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 implypolynomial-time algorithms.
邀 请 人：苗正科