图的{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 P_l.G is said to have {P_l}—decomposition if G can be decomposed into several P_l.The following are some main results concerning path decomposition:(i) a connected graph G has {P_3}—decomposition if and only if G has even number of edges(see[1]);(ii) a connected graph G has {P_3,P_4}—decomposition if and only if G isn't C_3 or odd tree,where C_3 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 {P_4}—decompositions of 3—regular graphs,then constructs the {P_4}—decompositions of complete graph K_n and complete bipartite graph K_r,s with 3k number of edges.