Cartesian积图的分解

若图G的边集能划分成两两不相交的若干个子集,使得每个子集都导出相同的子图H,则称G存在H分解。两个图G=（Vi,Ei）（i=1,2）的Cartesian积,记作G1□G2,其顶点集V=V1×V2,边集E={（（u1,u2）,（v1,v2））｜u1=v1∈V1,u2v2∈E2或u2=v2∈V2,u1v1∈E1}。本文给出了路和圈的Cartesian积图存在只分解的充要条件。

Decomposition on Cartesian Product of Graphs

A graph G is said to have an H decomposition, if the set of its edges can be partitioned into several mutual disjoint subsets such that each induces the same subgraph H. The Cartesian product of two graphs G=（Vi,Ei）（i=1,2）, denoted by G1□G2, is a graph with vertex-set V=V1×V2 and edge-set E={（（u1,u2）,（v1,v2））｜u1=v1∈V1,u2v2∈E2 or u2=v2∈V2,u1v1∈E1}.This paper provides sufficient and necessary conditions for Cartesian product of paths and cycles admitting P4 decomposition, respectively.