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 _k }-decomposition if G can be decomposed into some copies of P _l or P _k . An k-cycle, denoted by C _k , is a cycle with k 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 ₃, P ₄}-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 ₃}-decomposition and {P ₃, P ₄}-decomposition of graphs, respectively. Hence, {P ₃}-decomposition problem and {P ₃, P ₄}-decomposition problem of graphs are solved completely.