關(guān)于冠圖的路分解

戚嘯虎

（淮北師范大學 數(shù)學科學學院，安徽 淮北 235000）

關(guān)于冠圖的路分解

戚嘯虎

（淮北師范大學 數(shù)學科學學院，安徽 淮北 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的頂點數(shù)和邊數(shù).若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 設(shè)G,H是兩個簡單圖，冠圖G°H是由圖G和H合成的圖.其中使圖G的每一個頂點分別與圖H的每一個拷貝的所有頂點相連.

C3°P2如圖 1所示，其中C3的頂點集是 {v1,v2,v3}，P2的三個拷貝的頂點集分別是{u11,u12}、{u21,u22}、{u31,u32}.

圖1 冠圖C3P2圖示

一個圖的路分解是指一路集合使得圖中每條邊恰好出現(xiàn)在其中一條路上.文獻［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］閆桂英，許保光，吉日木圖.關(guān)于3-正則圖的路分解［J］.系統(tǒng)科學與數(shù)學.2004，24（2）：206-209.［2］鐘波，謝挺.關(guān)于正則圖的路分解［J］.西華大學學報，2005，24（4）：5-7.

［3］翟明清，葉永升.圖的{P4}-分解［J］.大學數(shù)學，2008，24（1）：75-78.

［4］徐立新.冠圖G1G2與邊冠圖G1G2的維納指數(shù)［J］.湘潭大學自然科學學報，2011，33（4）：4-6.

［5］DOUGLAS B W.Introduction to graph theory［M］.北京：機械工業(yè)出版社，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- ）,男，安徽宿州人，碩士生，研究方向：圖論.