Path Decomposition of Graphs with Given Path Length

摘要

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_κ}-decomposition if G can be decomposed into some copies of P_l or P_κ. An κ-cycle, denoted by C_κ, is a cycle with κ vertices. An odd tree is a tree of which all vertices have odd degree. In this paper, it is shown 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, two polynomial algorithms are given to find {P_3}-decomposition and {P_3, P_4}-decomposition of graphs, respectively. Hence, {P_3}-decomposition problem and {P_3, P_4}-decomposition problem of graphs are solved completely.