运 筹 学 讨 论 班

报告题目: Path decomposition of graphs with given length
报告人: 吕长虹 副教授;
单位: 华东师范大学数学系;
报告地点: 理科大楼A1510
时间: 11月8号（周三）下午3:30-4:30
报告内容: A path decomposition of a graph $G$ is a list of paths such that each edge appears in exactly one path in the list. $G$ is said to admit a ${P_l}$ - decomposition if $G$ can be decomposed into some copies of $P_l$, where $P_l$ is a path of length $l-1$. Similarly, $G$ is said to admit a ${P_l,P_k}$ -decomposition if $G$ can be decomposed into some copies of $P_l$ or $P_k$. A connected graph $G$ admits a ${P_3}$ - decomposition if and only if $G$ has even number of edges. But it is NP-complete to determine if $G$ admits a ${P_4}$-decomposition for any graph $G$. In this talk, I will introduce some results and quesitons on path decomposition (Include the famous Gallai Conjecture, Chuang’s conjecture and Fan’s result). Then, I will prove that a connected graph $G$ admits a ${P_3,P_4}$ - decomposition if and only if $G$ is neither a $3$-cycle nor an odd tree. This result includes the related result of Yan, Xu and MuTu. Moreover, a polynomial algorithm is given to find ${P_3,P_4}$- decomposition of graphs.


欢迎大家光临！