摘要
一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上.记P_(l)长度为l-1的路,如果G能够分解成若干个P_(l),则称G存在{P_(l)}—分解.关于图的给定长路分解问题主要结果有:(i)连通图G存在{P_(3)}—分解当且仅当G有偶数条边(见[1]);(ii)连通图G存在{P_(3),P_(4)}—分解当且仅当G不是C3和奇树,这里C_(3)的长度为3的圈而奇树是所有顶点皆度数为奇数的树(见[3]).本文讨论了3正则图的{P_(4)}—分解情况,并构造证明了边数为3k(k热∈Z且k≥2)的完全图Kn和完全二部图Kr,s存在{P_(4)}—分解.
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_(t).G is said to have{P_(l)}--decomposition if G can be decomposed into several Pi.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(P4)--decompositions of complete graph Kn and complete bipartite graph Kr,s with 3k number of edges.
作者
翟明清
叶永升
ZHAI Ming—qing;YE Yong—sheng(Department of Mathematics,Chuzhou University,Chuzhou 239012,China;Department of Mathematics,Huaibei Coal Industry Teachers College,Huaibei,Anhui 235000,China;Department of Mathematics,East China Normal University,Shanghai 200241,China)
出处
《大学数学》
北大核心
2008年第1期75-78,共4页
College Mathematics
基金
安徽省教育厅自然科学基金(KJ2007B124,2006KJ085B)
