图的{P4}——分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上．记Pl长度为l-1的路,如果G能够分解成若干个Pl,则称G存在{Pl}——分解,关于图的给定长路分解问题主要结果有：（i）连通图G存在{P3}-分解当且仅当G有偶数条边（见[1]）;（ii）连通图G存在{P3,P4}-分解当且仅当G不是C3和奇树,这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树（见[3]）．本文讨论了3正则图的{P4}--分解情况,并构造证明了边数为3k（k∈Z且k≥2）的完全图Kn和完全二部图Kr,s存在{P4}-分解.

The { P4 }--Decomposition of Graphs

A path decomposition of a graph G is a set of paths such that each edge of G is exactly in one path. A path with length l-1 is denoted by Pt. G is said to have {Pl}--decomposition if G can be decomposed into several Pi. The following are some main results concerning path decomposition： （i） a connected graph G has {P3}-decomposition if and only if G has even number of edges （see[1 ]） ; （ii） a connected graph G has {P3, P4 }-decomposition if and only if G isn＇t C3 or odd tree, where C3 is a cycle of length three and odd tree is a tree in which all vertices have odd degrees （see[3]）. This paper discusses the {P4}--decompositions of 3--regular graphs, then constructs the （P4}--decompositions of complete graph Kn and complete bipartite graph Kr,s with 3k number of edges.