关于冠图的路分解

Path Decomposition of Corona Graph

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

Corona graph G°H is composed of G and H synthetic graphs,denoted by G°H .Each vertex of G is respectively connected with every vertice of each copy of H . G is said to have decomposition of sub-graphs H if the edge set of graph G can be decomposed into a number of subgraphs H which the edges dis-joint;G has {P3,P4}-decomposition when H is P3 or P4 .This paper discusses the problem of the path de-composition of some corona graphs and shows that Pm°Pn 、Pm°Cn 、Cm°Pn and Cm°Cn have the{P3,P4}-decomposition.