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 onepath in the list.G is said to admit a {P_l}-decomposition if G can be decomposed into some copies of P_l,whereP_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 intosome 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 allvertices have odd degree.In this paper,it is shown that a connected graph G admits a {P_3,P_4}-decompositionif and only if G is neither a 3-cycle nor an odd tree.This result includes the related result of Yan,Xu andMutu.Moreover,two polynomial algorithms are given to find {P_3}-decomposition and {P_3,P_4}-decompositionof graphs,respectively.Hence,{P_3}-decomposition problem and {P_3,P_4}-decomposition problem of graphs aresolved completely.

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 {Pl }-decomposition if G can be decomposed into some copies of Pl, where Pl is a path of length l - 1. Similarly, G is said to admit a {Pl, Pk}-decomposition if G can be decomposed into some copies of Pl or Pk. An k-cycle, denoted by Ck, 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 {P3, P4}-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 {P3}-decomposition and {P3, P4}-decomposition of graphs, respectively. Hence, {P3}-decomposition problem and {P3, P4}-decomposition problem of graphs are solved completely.