关于冠图的路分解

戚啸虎

（淮北师范大学 数学科学学院，安徽 淮北 235000）

关于冠图的路分解

戚啸虎

（淮北师范大学 数学科学学院，安徽 淮北 235000）

冠图是由图G和H合成的图，其中使图G的每一个顶点分别与图H的每一个拷贝的所有顶点相连.如果图G的边集合可以分解为若干个边不相交的子图H，那么称G有子图H的分解，当H是P3或P4时，就称G有{P3,P4}分解.文章讨论了一些冠图的{P3,P4}分解问题，得到冠图存在{P3,P4}分解.

冠图；扇图；轮图；路分解

1 引言

本文所讨论的图都是简单图.对图G，用|V(G)|和|E(G)|分别表示图G的顶点数和边数.若V(H)⊂V(G),E(H)⊂E(G)称H为G的子图，记为H⊂G.用Pk表示包含k个顶点的路，其长度为k-1.如果图G的边集合可以分解为若干个不相交的子图H时，那么就称G有子图H分解，当H是P3或P4时，就称G有{P3,P4}分解.

定义1 设G,H是两个简单图，冠图G∘H是由图G和H合成的图.其中使图G的每一个顶点分别与图H的每一个拷贝的所有顶点相连.

C3∘P2如图 1所示，其中C3的顶点集是 {v1,v2,v3}，P2的三个拷贝的顶点集分别是{u11,u12}、{u21,u22}、{u31,u32}.

图1 冠图C3P2图示

一个图的路分解是指一路集合使得图中每条边恰好出现在其中一条路上.文献［1］证明了3-正则图必有{P3,P4}分解；文献［2］给出了任一正则图均可进行{P3,P4}分解；文献［3］指出每个3正则的二部图都有{P4}分解.而在本文中我们将把注意力放在冠图存在{P3,P4}分解的问题上.

2 冠图PmPn和CmPn存在{P3,P4}分解

我们首先给出扇图的定义及其存在{P3,P4}分解，然后证明了冠图存在{P3,P4}分解.

3 冠图PmCn和CmCn存在{P3,P4}分解

我们首先给出轮图的定义及其存在{P3,P4}分解，然后证明了冠图存在{P3,P4}分解.

［1］闫桂英，许保光，吉日木图.关于3-正则图的路分解［J］.系统科学与数学.2004，24（2）：206-209.［2］钟波，谢挺.关于正则图的路分解［J］.西华大学学报，2005，24（4）：5-7.

［3］翟明清，叶永升.图的{P4}-分解［J］.大学数学，2008，24（1）：75-78.

［4］徐立新.冠图G1G2与边冠图G1G2的维纳指数［J］.湘潭大学自然科学学报，2011，33（4）：4-6.

［5］DOUGLAS B W.Introduction to graph theory［M］.北京：机械工业出版社，2006.

Path Decomposition of Corona Graph

QI Xiao-hu
（School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China）

Corona graphGHis composed ofGandHsynthetic graphs，denoted byGH.Each vertex ofGis respectively connected with every vertice of each copy ofH.Gis said to have decomposition of sub⁃graphsHif the edge set of graphGcan be decomposed into a number of subgraphsHwhich the edges dis⁃joint；Ghas{P3,P4}-decomposition whenHisP3orP4.This paper discusses the problem of the path de⁃ composition of some corona graphs and shows thathave the {P3,P4}-decomposition.

corona graphs；fan graph；wheel graph；path decomposition

O 157.5

：A

：2095-0691（2014）01-0005-03

2013-12-18

安徽省自然科学基金项目（1408085MA08）；安徽省教育厅自然科学基金项目（KJ2013Z279）

戚啸虎（1986- ）,男，安徽宿州人，硕士生，研究方向：图论.