劉秀麗

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

幾類特殊圖的（2，1）－全標(biāo)號(hào)

劉秀麗

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

研究了與頻道分配有關(guān)的1種 （p，1）－全標(biāo)號(hào)染色問題.（p，1）－全標(biāo)號(hào)是從V（G）∪E（G）到集合｛0，1，…，k｝的1個(gè)映射，滿足：①G的任2個(gè)相鄰的頂點(diǎn)得到不同的整數(shù)；②G的任2個(gè)相鄰的邊得到不同的整數(shù)；③任1個(gè)點(diǎn)和與它相關(guān)聯(lián)的邊得到的整數(shù)至少相差p.通過在2個(gè)簡(jiǎn)單圖之間疊加一系列匹配構(gòu)造了幾類有趣圖，并根據(jù)所構(gòu)造圖的特征，利用窮染法得到了這些圖的（2，1）－全標(biāo)號(hào)數(shù).

染色；（p，1）－全標(biāo)號(hào)；（p，1）－全標(biāo)號(hào)數(shù)；弱聯(lián)圖

0 引言

由于圖的染色問題在現(xiàn)實(shí)中有著廣泛應(yīng)用，因而該問題受到眾多學(xué)者的重視.近年來，研究者［1－3］又提出了許多新的染色問題，且這些染色問題在頻率分配中得到了很好的應(yīng)用，如泛寬度染色和L（p，1）－標(biāo)號(hào).特別地，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的頂點(diǎn)集和邊集，對(duì)?v∈V（G），用dG（v）表示頂點(diǎn)v在圖G中的度，用Δ（G）表示圖G中頂點(diǎn)的最大度.本文所討論的圖均為簡(jiǎn)單有限圖.

定義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｝，使得：①G的任2個(gè)相鄰的頂點(diǎn)u和v，有②G的任2條相鄰的邊e和e′，有；③G的任2個(gè)相關(guān)聯(lián)的點(diǎn)v和邊e，有－全標(biāo)號(hào)的跨度是指2個(gè)標(biāo)號(hào)差的最大值，圖G的（p，1）－全標(biāo)號(hào)的最小跨度稱為（p，1）－全標(biāo)號(hào)數(shù)，記作λTp（G）.

當(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).

引理1［5］對(duì)任意圖G，有λTp（G）≥Δ＋p－1.

引理2［6］若圖G滿足λT2（G）＝Δ（G）＋1，映射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是正則的，則λTp（G）≥Δ＋p.

文中未加說明的記號(hào)和術(shù)語(yǔ)參見文獻(xiàn)［7－8］.

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

設(shè)G和G′均為簡(jiǎn)單連通圖，其頂點(diǎn)集分別為V（G）＝ ｛u1，u2，…，un｝，V（G′）＝ ｛v1，v2，…，vn｝.在G和G′之間疊加匹配uivi，uivi＋1，uivi＋2，…，uivi＋m，…，uivi＋（n－1），其中i＝1，2，…，n；m＝0，1，2，…，n－1；當(dāng)i＋m＞n時(shí)，i＋m為modn意義下的加法.這樣得到一系列新圖稱為圖G和G′的弱聯(lián)圖.顯然，G（n）n，n＝G∨G′.

定理1 設(shè)V1＝ ｛u1，u2，…，un｝，V2＝ ｛v1，v2，…，vn｝，在兩部之間疊加上述匹配可得到一系列正則二部圖Gn（1，n），Gn（2，n），…，Gn（m，n＋1），…，Gn（n，n）＝Kn，n，則有λ2T（Gn（m，n＋1））＝m＋3，其中m＝0，1，2，…，n－1.

證明 由圖Gn（m，n＋1）的構(gòu)造知，Δ（Gn（m，n＋1））＝m＋1，并且圖Gn（m，n＋1）為（m＋1）－正則圖.由引理3有，

下證λ2T（Gn（m，n＋1））≤m＋3.構(gòu)造1個(gè)映射f∶V（Gn（m，n＋1））∪E（Gn（m，n＋1））→ ｛0，1，2，…，m＋3｝.f（ui）＝m＋2，f（vi）＝m＋3，i＝1，2，…，n；f（uivi＋j）＝j(luò)，i＝1，2，…，n，j＝0，1，2，…，m，當(dāng)i＋j＞n時(shí)，i＋j為mod n意義下的加法.易證映射f是Gn（m，n＋1）的1個(gè)正常的（2，1）－全標(biāo)號(hào)，所以λ2T（Gn（m，n＋1））≤m＋3.

綜上，有λ2T（Gn（m，n＋1））＝m＋3，其中m＝0，1，2，…，n－1.

定理2 設(shè)Pn和P′n為2個(gè)階均為n的路，在Pn和P′n之間疊加上述匹配得到一系列圖Pn（1，n），Pn（2，n），…，Pn（m，n＋1），…，Pn（n，n），則有λ2T（Pn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1，n≥4.

證明 不妨設(shè)V（Pn）＝ ｛u1，u2，…，un｝，V（P′n）＝ ｛v1，v2，…，vn｝.由圖Pn（m，n＋1）的構(gòu)造知，Δ（Pn（m，n＋1））＝m＋1＋2＝m＋3.由引理1得λ2T（Pn（m，n＋1））≥Δ＋2－1＝m＋4.

首先證明λ2T（Pn（m，n＋1））＝m＋4不成立，即標(biāo)號(hào)集｛0，1，2，…，m＋4｝無法完成對(duì)圖Pn（m，n＋1）的正常的（2，1）－全標(biāo)號(hào).運(yùn)用反證法.假設(shè)存在1個(gè)映射f∶V（Pn（m，n＋1））∪E（Pn（m，n＋1））→ ｛0，1，2，…，m＋4｝是圖Pn（m，n＋1）的1個(gè)正常的（2，1）－全標(biāo)號(hào)，由引理2知，Pn（m，n＋1）的最大度點(diǎn)只能標(biāo)0或m＋4.由圖Pn（m，n＋1）的結(jié)構(gòu)知，當(dāng)n≥4時(shí)，最大度點(diǎn)生成的子圖中包含三角形，而三角形的頂點(diǎn)色數(shù)為3，所以0和m＋4無法完成對(duì)最大度點(diǎn)的全標(biāo)號(hào)，矛盾.所以λ2T（Pn（m，n＋1））≥m＋5.

再證λ2T（Pn（m，n＋1））≤m＋5.構(gòu)造1個(gè)映射f∶V（Pn（m，n＋1））∪E（Pn（m，n＋1））→ ｛0，1，2，…，m＋5｝.用0，1循環(huán)標(biāo)點(diǎn)u1，u2，…，un；用4，3循環(huán)標(biāo)點(diǎn)v1，v2，…，vn；用3，4循環(huán)標(biāo)邊u1u2，u2u3，…，un－1un；用0，1循環(huán)標(biāo)邊v1v2，v2v3，…，vn－1vn；用2，5循環(huán)標(biāo)邊uivi（i＝1，2，…，n）；用 m＋5標(biāo)邊uivi＋m（i＝1，2，…，n；m＝1，2，…，n－1；當(dāng)i＋m＞n時(shí)，i＋m為mod n意義下的加法）.易證映射f是Pn（m，n＋1）的1個(gè)正常的（2，1）－全標(biāo)號(hào).所以λ2T（Pn（m，n＋1））≤m＋5.

綜上，有λ2T（Pn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1，n≥4.

定理3 設(shè)Cn和C′n為2個(gè)階均為n（n≥3）的圈，在Cn和C′n之間疊加上述匹配得到一系列正則圖Cn（1，n），Cn（2，n），…，Cn（m，n＋1），…，Cn（n，n），則有：① 當(dāng)n為偶數(shù)時(shí)，有λ2T（Cn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1；② 當(dāng)n為奇數(shù)時(shí)，有m＋5≤λ2T（Cn（m，n＋1））≤m＋6，其中m＝0，1，2，…，n－1.

證明 不 妨 設(shè)V（Cn）＝ ｛u1，u2，…，un｝，V（C′n）＝ ｛v1，v2，…，vn｝.由 圖Cn（m，n＋1）的 構(gòu) 造 知，.又因?yàn)镃n為2－正則圖，所以Cn（m，n＋1）為（m＋3）－正則圖，由引理3得

1）當(dāng)n為偶數(shù)時(shí).構(gòu)造1個(gè)映射f∶V（Cn（m，n＋1））∪E（Cn（m，n＋1））→ ｛0，1，2，…，m＋5｝.用0，1循環(huán)標(biāo)點(diǎn)u1，u2，…，un；用4，3循環(huán)標(biāo)點(diǎn)v1，v2，…，vn；用3，4循環(huán)標(biāo)邊u1u2，u2u3，…，un－1un，unu1；用0，1循環(huán)標(biāo)邊v1v2，v2v3，…，vn－1vn，vnv1；用2，5循環(huán)標(biāo)邊uivi（i＝1，2，…，n）；用m＋5標(biāo)邊uivi＋m（i＝1，2，…，n；m ＝1，2，…，n－1；當(dāng)i＋m＞n時(shí)，i＋m為mod n意義下的加法）.易證映射f是Cn（m，n＋1）的1個(gè)正常的（2，1）－全標(biāo)號(hào).所以λ2T（Cn（m，n＋1））≤m＋5.綜上，當(dāng)n為偶數(shù)時(shí)，有λ2T（Cn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1.

2）當(dāng)n為奇數(shù)時(shí).構(gòu)造1個(gè)映射f∶V（Cn（m，n＋1））∪E（Cn（m，n＋1））→ ｛0，1，2，…，m＋6｝.用0，1循環(huán)標(biāo)點(diǎn)u1，u2，…，un－1，用2標(biāo)點(diǎn)un；用4，3循環(huán)標(biāo)點(diǎn)v1，v2，…，vn－1，用5標(biāo)點(diǎn)vn；用3，4循環(huán)標(biāo)邊u1u2，u2u3，…，un－1un，用5標(biāo)邊unu1；用0，1循環(huán)標(biāo)邊v1v2，v2v3，…，vn－1vn，用2標(biāo)邊vnv1；用6，5，2，5循環(huán)標(biāo)邊uivi（i＝1，2，…，n－1），用0標(biāo)邊unvn；用m＋6標(biāo)邊uivi＋m（i＝1，2，…，n；m＝1，2，…，n－1；當(dāng)i＋m ＞n時(shí)，i＋m為mod n意義下的加法）.易證映射f是Cn（m，n＋1）的1個(gè)正常的（2，1）－全標(biāo)號(hào).所以λ2T（Cn（m，n＋1））≤m＋6.綜上，當(dāng)n為奇數(shù)時(shí)，有m＋5≤λ2T（Cn（m，n＋1））≤m＋6，其中m＝0，1，2，…，n－1.

注：顯然，當(dāng)m＝0時(shí)，即為圖Cn（1，n），稱之為雙圈［9］.

在本文的寫作過程中，得到山東師范大學(xué)數(shù)學(xué)科學(xué)院的孫磊老師和高敬振老師的幫助，謹(jǐn)致謝意.

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

［2］Georges J P，Mauro D W，Stein MI.Labelling products of complete graphs with a condition at distance two［J］.SIAMJ Discrete Math，2001，14（1）：28－35.

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

［4］Whittles MA，Georges J P，Mauro D W.On theλ－number ofQnand related graphs［J］.SIAMJ Discrete Math，1995，8（4）：499－506.

［5］Havet F，Yu ML.（p，1）－total labelling of graphs［J］.Discrete Math，2008，308（4）：496－513.

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

［7］Bollobas B.Modern Graph Theory［M］.Ne wYork：Springer－Verlag，1998：145－177.

［8］Bondy J A，Murty U S R.Graph Theory with Applications［M］.London：Macmillan Press Ltd，1976：123－196.

［9］孫磊，孫艷麗，董海燕.幾類特殊圖的鄰點(diǎn)可區(qū)別的全染色［J］.西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，31（4）：1－4.

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

LIU Xiu－li
（DepartmentofMathematics，HezeUniversity，Heze274015，China）

We study（p，1）－total labelling of a graphG，which related to frequency assignment problem of coloring problem.（p，1）－total labelling is an assignment from the setV（G）∪E（G）to the integer｛0，1，…，k｝，such that：①any two adjacent vertices ofG

istinct integers；②any two adjacent edges ofG

istinct integers；and③ a vertex and its incident edge receive integers that differ by at leastpin absolute value.Some special graphs are constructed by superimposing matchs between two simple graphs，and the（2，1）－total numbers of these graphs are given by the eternal coloring according to their feature.

coloring；（p，1）－total labelling；（p，1）－total number；weak join of two graphs

O157.5

A

1004－4353（2012）01－0038－03

2011－11－13

劉秀麗（1977—），女，講師，研究方向?yàn)閳D論與組合優(yōu)化.