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 p...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.展开更多
基金Supported by the National Natural Science Foundation of China(No.10301010)Science and Technology Commission of Shanghai Municipality(No.04JC14031)Natural Science Project of Chuzhou University(No.2006kyy017)
文摘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.
