劉秀麗

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

幾類特殊圖的（2，1）－全標號

劉秀麗

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

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

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

0 引言

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

定義1［5］設(shè)p是1個非負整數(shù)，圖G的1個k－（p，1）－全標號是1個映射f∶V（G）∪E（G）→｛0，1，…，k｝，使得：①G的任2個相鄰的頂點u和v，有②G的任2條相鄰的邊e和e′，有；③G的任2個相關(guān)聯(lián)的點v和邊e，有－全標號的跨度是指2個標號差的最大值，圖G的（p，1）－全標號的最小跨度稱為（p，1）－全標號數(shù)，記作λTp（G）.

當p＝1時，圖G的（p，1）－全標號對應(yīng)于圖G的全染色，因此圖的（p，1）－全標號也是對圖的全染色的一種推廣.本文主要討論幾類特殊圖的（2，1）－全標號.

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

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

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

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

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

設(shè)G和G′均為簡單連通圖，其頂點集分別為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；當i＋m＞n時，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個映射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，當i＋j＞n時，i＋j為mod n意義下的加法.易證映射f是Gn（m，n＋1）的1個正常的（2，1）－全標號，所以λ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個階均為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不成立，即標號集｛0，1，2，…，m＋4｝無法完成對圖Pn（m，n＋1）的正常的（2，1）－全標號.運用反證法.假設(shè)存在1個映射f∶V（Pn（m，n＋1））∪E（Pn（m，n＋1））→ ｛0，1，2，…，m＋4｝是圖Pn（m，n＋1）的1個正常的（2，1）－全標號，由引理2知，Pn（m，n＋1）的最大度點只能標0或m＋4.由圖Pn（m，n＋1）的結(jié)構(gòu)知，當n≥4時，最大度點生成的子圖中包含三角形，而三角形的頂點色數(shù)為3，所以0和m＋4無法完成對最大度點的全標號，矛盾.所以λ2T（Pn（m，n＋1））≥m＋5.

再證λ2T（Pn（m，n＋1））≤m＋5.構(gòu)造1個映射f∶V（Pn（m，n＋1））∪E（Pn（m，n＋1））→ ｛0，1，2，…，m＋5｝.用0，1循環(huán)標點u1，u2，…，un；用4，3循環(huán)標點v1，v2，…，vn；用3，4循環(huán)標邊u1u2，u2u3，…，un－1un；用0，1循環(huán)標邊v1v2，v2v3，…，vn－1vn；用2，5循環(huán)標邊uivi（i＝1，2，…，n）；用 m＋5標邊uivi＋m（i＝1，2，…，n；m＝1，2，…，n－1；當i＋m＞n時，i＋m為mod n意義下的加法）.易證映射f是Pn（m，n＋1）的1個正常的（2，1）－全標號.所以λ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個階均為n（n≥3）的圈，在Cn和C′n之間疊加上述匹配得到一系列正則圖Cn（1，n），Cn（2，n），…，Cn（m，n＋1），…，Cn（n，n），則有：① 當n為偶數(shù)時，有λ2T（Cn（m，n＋1））＝m＋5，其中m＝0，1，2，…，n－1；② 當n為奇數(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) 造 知，.又因為Cn為2－正則圖，所以Cn（m，n＋1）為（m＋3）－正則圖，由引理3得

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

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

注：顯然，當m＝0時，即為圖Cn（1，n），稱之為雙圈［9］.

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

［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］孫磊，孫艷麗，董海燕.幾類特殊圖的鄰點可區(qū)別的全染色［J］.西南師范大學(xué)學(xué)報：自然科學(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ōu)化.