劉秀麗

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

若干倍圖的（2，1）－全標(biāo)號(hào)

劉秀麗

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

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

染色；（p，1）－全標(biāo)號(hào)；（p，1）－全標(biāo)號(hào)數(shù)；倍圖

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

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

1 預(yù)備知識(shí)

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

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

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

引理1［5］對(duì)任意圖G，有

引理2［7］若圖G滿足，映射f表示圖G的1個(gè)標(biāo)號(hào)集是｛0，1，2，…，Δ（G）＋1｝的（2，1）－全標(biāo)號(hào)，那么對(duì)圖G的每個(gè)最大度點(diǎn)v，有f（v）＝0或f（v）＝Δ（G）＋1．

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

文中未加說(shuō)明的記號(hào)和術(shù)語(yǔ)參見(jiàn)文獻(xiàn)［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時(shí)，有λ2T（D（P4））＝5．

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

易證映射f是D（Pn）的1個(gè)正常的（2，1）－全標(biāo)號(hào)，所以

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

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

易證映射f是D（Cn）的1個(gè)正常的（2，1）－全標(biāo)號(hào)，所以

易證映射f是D（Cn）的1個(gè)正常的（2，1）－全標(biāo)號(hào)，所以

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

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

易證映射f是圖D（Sn）的1個(gè)正常的（2，1）－全標(biāo)號(hào)，所以

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

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

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

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

易證映射f是圖D（Fn）的1個(gè)正常的（2，1）－全標(biāo)號(hào)，所以λ2T（D（Fn））≤2n＋1．

綜上，當(dāng)n≥4時(shí)，有λ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)鄰點(diǎn)可區(qū)別全染色［J］．內(nèi)蒙古師范大學(xué)學(xué)報(bào)：自然科學(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àn)閳D論與組合優(yōu)化．