若干倍圖的（2，1）－全標號

劉秀麗

（菏澤學(xué)院 數(shù)學(xué)系，山東 菏澤274015）

若干倍圖的（2，1）－全標號

劉秀麗

（菏澤學(xué)院 數(shù)學(xué)系，山東 菏澤274015）

研究了與頻道分配有關(guān)的一種（p，1）－全標號染色問題．根據(jù)倍圖的構(gòu)造特征，利用窮染法，給出了一種標號方法，得到了路、圈、星、扇的倍圖的（2，1）－全標號數(shù)．（p，1）－全標號是對圖的全染色的一種推廣．

染色；（p，1）－全標號；（p，1）－全標號數(shù)；倍圖

隨著圖的染色問題在現(xiàn)實中的廣泛應(yīng)用，它逐漸成為眾多學(xué)者研究的重要領(lǐng)域之一．圖的著色問題是圖論中的重要研究分支，有很強的理論意義和實際意義．近年來，許多新的染色問題被提出，這些染色問題在頻率分配中有很強的應(yīng)用，如泛寬度染色、L（p，1）－標號［1－3］等．特別地，Whittlesey等人在文獻［4］中研究了G的剖分圖的L（2，1）－標號，G的剖分圖S1（G）是由圖G在每條邊上插入1個點所得到的圖．S1（G）的L（p，1）－標號對應(yīng)于G的（p，1）－全標號．

圖G為簡單連通圖，用V（G）、E（G）和Δ（G）分別表示圖G的頂點集、邊集和頂點的最大度．本文所討論的圖均為簡單、有限圖．

1 預(yù)備知識

定義1［5］設(shè)p是1個非負整數(shù)，圖G的1個k－（p，1）－全標號是1個映射f∶V（G）∪E（G）→｛0，1，…，k｝，使得：

當(dāng)p＝1時，圖G的（p，1）－全標號對應(yīng)于圖G的全染色，因此，圖的（p，1）－全標號也是對圖的全染色的一種推廣．本文主要討論了若干倍圖的（2，1）－全標號．

定義2［6］對簡單圖G，其頂點集為V（G）＝｛u1，u2，…，un｝，圖G′為G的拷貝，其頂點集V（G′）＝｛v1，v2，…，vn｝，則稱D（G）為G的倍圖，其中：

引理1［5］對任意圖G，有

引理2［7］若圖G滿足，映射f表示圖G的1個標號集是｛0，1，2，…，Δ（G）＋1｝的（2，1）－全標號，那么對圖G的每個最大度點v，有f（v）＝0或f（v）＝Δ（G）＋1．

引理3［5］若G是正則的，則λpT（G）≥Δ＋p．

文中未加說明的記號和術(shù)語參見文獻［8－9］．

2 主要結(jié)果及證明

定理1 設(shè)Pn是階為nn≥3的路，則

證明 1）n＝3．由圖D（Pn）的定義知由引理1有

2）n＝4．由圖D（Pn）的定義知，．由引理1有

綜上，當(dāng)n＝4時，有λ2T（D（P4））＝5．

3）n≥5．由圖D（Pn）的定義知由引理1有

易證映射f是D（Pn）的1個正常的（2，1）－全標號，所以

定理2 設(shè)Cn是階為n（n≥3）的圈，則

證明 由圖D（Cn）的定義知且為正則圖．由引理3有

易證映射f是D（Cn）的1個正常的（2，1）－全標號，所以

易證映射f是D（Cn）的1個正常的（2，1）－全標號，所以

定理3 設(shè)Sn是階為n＋1（n≥2）的星，則

當(dāng)n≥3時，由圖D（Sn）的定義知由引理1有

易證映射f是圖D（Sn）的1個正常的（2，1）－全標號，所以

定理4 設(shè)Fn是階為

2）當(dāng)n＝3時，由圖D（Fn）的定義知．由引理1有

3）當(dāng)n≥4時，由圖D（Fn）的定義知，Δ（D （Fn））＝2n．由引理1有＝2n＋1．

下證λ2T（D（Fn））≤2n＋1．構(gòu)造1個映射令

易證映射f是圖D（Fn）的1個正常的（2，1）－全標號，所以λ2T（D（Fn））≤2n＋1．

綜上，當(dāng)n≥4時，有λ2T（D（Fn））＝2n＋1．

［1］ Griggs J R，Yeh R K．Labeling graphs with a condition at distance two［J］．SIAM J Discrete Math，1992，5（4）：586－595．

［2］ Georges J P，Mauro D W，Stein M I．Labeling products of complete graphs with a condition at distance two［J］．SIAM J Discrete Math，2001，14（1）：28－35．

［3］ Georges J P，Mauro D W，Whittles M A．Relating path covering to vertex labeling with a condition at distance two［J］．Discrete Math，1994，135（1/3）：103－111．

［4］ Whittles M A，Georges J P，Mauro D W．On theλ－number of Qnand related graphs［J］．SIAM J Discrete Math，1995，8（4）：499－506．

［5］ Havet F，Yu M L．（p，1）－Total labeling of graphs［J］．Discrete Math，2008，308（4）：496－513．

［6］ 王志文，楊隨義，文飛．關(guān)于若干倍圖的關(guān)聯(lián)鄰點可區(qū)別全染色［J］．內(nèi)蒙古師范大學(xué)學(xué)報：自然科學(xué)版，2009，38（6）：643－646．

［7］ Chen Dong，Wang Wei－fan．（2，1）－Total labeling of outer planar graphs［J］．Discrete Applied Mathematics，2007，155（18）：2585－2593．

［8］ Bollobas B．Modern Graph Theory［M］．New York：Springer－Verlag，1998：147－189．

［9］ Bondy J A，Murty U S R．Graph Theory with Applications［M］．London：Macmillan Press Ltd，1976：128－196．

The（2，1）－total labelling of some double graphs

LIU Xiu－li
（Department of Mathematics，Heze University，Heze 274015，China）

We study a coloring problem—（2，1）－total labeling of some graphs，which is related to frequency assignment．By using the eternal coloring method，we give a new labeling method according to the feature of the double graphs of path，circle，star，fan and obtain the（2，1）－total numbers of these graphs．And the（p，1）－total labeling of graphs extends the total coloring of graphs．

coloring；（p，1）－total labelling；（p，1）－total number；double graph

O157．5

A

1004－4353（2012）02－0104－04

2012－06－03

劉秀麗（1977—），女，講師，研究方向為圖論與組合優(yōu)化．