Cartesian积图的分解  

Decomposition on Cartesian Product of Graphs

作　　者：张梅[1] 袁万莲[1] 

机构地区：[1]滁州学院数学系,安徽滁州239000

出　　处：《科技信息》2008年第7期9-9,共1页Science & Technology Information

基　　金：安徽省教育厅自然科学基金(No.KJ2007B124)

摘　　要：若图G的边集能划分成两两不相交的若干个子集,使得每个子集都导出相同的子图H,则称G存在H分解。两个图Gi=(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积图存在P4分解的充要条件。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.

关 键 词：路 圈 Cartesian积 P4分解 

分 类 号：O157.4[理学—数学] O151.21[理学—基础数学]