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

劉秀麗

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

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

劉秀麗

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

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

（p，1）－全標(biāo)號；（p，1）－全標(biāo)號數(shù)；Pkn圖；Cn·Fm圖

在頻率分配問題中，會出現(xiàn)需要給中轉(zhuǎn)站分配頻率波段（每個中轉(zhuǎn)站得到對應(yīng)于1個整數(shù)的頻率波段）的情況.為了避免干擾，如果2個站點離得非常近，那么它們的頻率之差至少要相差2，而且如果2個站點離得近（不是非常近），那么它們得到的頻率不同.受到這個問題的啟發(fā)，Griggs和Yeh［1］引入了L（2，1）－標(biāo)號，它的自然推廣就是圖G的L（p，1）－標(biāo)號.關(guān)于這個標(biāo)號已有作者對其進(jìn)行了研究［2］，特別地，Whittlesey等在文獻(xiàn)［3］中研究了G的剖分圖S1（G）的L（2，1）－標(biāo)號，S1（G）的L（p，1）－標(biāo)號對應(yīng)于G的（p，1）－全標(biāo)號.

1 預(yù)備知識

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

當(dāng)p＝1時，圖G的（p1－全標(biāo)號對應(yīng)于圖G的全染色，這種情況也被廣泛研究，因此，圖的（p，1）－全標(biāo)號不僅與圖的距離2標(biāo)號問題密切相關(guān)，而且也是對圖的全染色的一種推廣.本文將主要討論p＝2時即圖G的（2，1）－全標(biāo)號.

定義2［5］在含有n個頂點的路Pn上，當(dāng)且僅當(dāng)2點的距離（模）為k時加1條邊，所得到的圖稱為Pkn圖.

定義3［6］Fm表示階為m＋1的扇，當(dāng)n個扇Fm的扇心連成圈Cn時，用Cn·Fm表示.設(shè)V（Cn）＝｛v1，v2，…，vn｝，則

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

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

文中未加說明的記號和術(shù)語參見文獻(xiàn)［8］和［9］.

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

下面給出部分Pkn圖的（2，1）－全標(biāo)號.

定理1 對圖Pkn，有λT2（Pkn）＝6，k＞1且k不能被12整除，n≥3k＋2.

證明 由圖Pkn的定義易知，Δ（Pkn）＝4，由引理1有λT2（Pkn）≥Δ＋2－1＝5.首先證明λT2（Pkn）＝5不成立，即標(biāo)號集｛0，1，2，3，4，5｝無法完成對圖Pkn的正常的（2，1）－全標(biāo)號.反證法.假設(shè)存在1個映射是圖Pkn的1個正常的（2，1）－全標(biāo)號.由引理2知，圖Pkn的最大度點只能標(biāo)0或5.不妨設(shè)V（Pn）＝ ｛v1，v2，…，vn｝.若n≥3k＋2，則存在1個最大度點vi至少與3個最 大度點vj，vm，vl相連.由（2，1）－全標(biāo)號的定義知，與0和5相差2的只有2和3這2個數(shù)，無法完成對vivj，vivm，vivl這3條邊的標(biāo)號，矛盾，所以λT2（Pkn）≥6.

1）k≡0（mod 2）.1′2

2′但3不能整除k，即k＝4，8，16，20，28，32，40….①k＝4（3m－2），m＝1，2，3，…，即k＝4，16，28，40，….用0，4，6循環(huán)標(biāo)點vi（i＝1，2，…，n）；用6，0，4循環(huán)標(biāo)邊vivi＋1（i＝1，2，…，n－1）；用2，1，3循環(huán)標(biāo)邊vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡1（mod 3））；用1，3，2循環(huán)標(biāo)邊vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡2（mod3））；用3，2，1循環(huán)標(biāo)邊vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡0（mod 3））.易證映射f是圖Pkn的1個正常的（2，1）－全標(biāo)號，所以λT2（Pkn）≤6.②k＝4（3m－1），m＝1，2，3，…，即k＝8，20，32，44，….用0，4，6循環(huán)標(biāo)點vi（i＝1，2，…，n）；用6，0，4循環(huán)標(biāo)邊vivi＋1（i＝1，2，…，n－1）；用3，1，2循環(huán)標(biāo)邊vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡1（mod 3））；用2，3，1循環(huán)標(biāo)邊vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡2（mod 3））；用1，2，3循環(huán)標(biāo)邊vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k；i≡0（mod 3））.易證映射f是圖Pkn的1個正常的（2，1）－全標(biāo)號，所以λT2（Pkn）≤6.

2）k≡1（mod 2）.用0，1循環(huán)標(biāo)點vi（i＝1，2，…，n）；用3，4循環(huán)標(biāo)邊vivi＋1（i＝1，2，…，n－1）；用5，6循環(huán)標(biāo)邊vivk＋i，vk＋iv2k＋i，v2k＋iv3k＋i，…（i＝1，2，…，k）.易證映射f是圖Pkn的1個正常的（2，1）－全標(biāo)號，所以λT2（Pkn）≤6．

綜上，有λT2（Pkn）＝6，k＞1，n≥3k＋2．

證明 1）n≡0（mod 2）．① 當(dāng)m＝1時，由圖Cn·Fm的定義易知，Δ（Cn·Fm）＝3．所以由引理1，有λT2（Cn·Fm）≥Δ＋2－1＝4．首先證明λT2（Cn·Fm）＝4不成立，即標(biāo)號集｛0，1，2，3，4｝無法完成對圖Cn·Fm的正常的（2，1）－全標(biāo)號．事實上，假設(shè)存在1個映射是圖Cn·Fm的1個正常的（2，1）－全標(biāo)號．由引理2知，圖Cn·Fm的最大度點vi（i＝1，2，…，n）只能標(biāo)0或4，即＝0或若則4（i＋1為mod n意義下的加法），與0和4相差2的只有2這1個數(shù)．由（2，1）－全標(biāo)號的定義知，無法完成對vi－1vi和vivi＋1這2條邊的標(biāo)號，矛盾．若）＝4，同理可得出矛盾，所以

再證λ2（Cn·Fm）≤5．構(gòu)造1個映射用0，5循環(huán)標(biāo)點v1，v2，…，vn；用2，3循環(huán)標(biāo)邊v1v2，v2v3，…，vn－1vn，vnv1；用2標(biāo)點ui1（i＝1，2，…，n）．若0，則令若，則令易證映射f是圖Cn·Fm的1個正常的（2，1）－全標(biāo)號，所以λT2（Cn·Fm）≤5．綜上，有λT2（Cn·Fm）＝5．

② 當(dāng)m ≥2時，由圖Cn·Fm的定義易知，Δ（Cn·Fm）＝m＋2．所以由引理1有，λT2（Cn·Fm）≥Δ＋2－1＝m＋3．下證λT2（Cn·Fm）≤m＋3．構(gòu)造1個映射．用0，m＋3循環(huán)標(biāo)點v1，v2，…，vn；用2，3循環(huán)標(biāo)邊v1v2，v2v3，…，vn－1vn，vnv1．若則用4，5，6，…，m＋3依次標(biāo)邊viui1，viui2，…，viuim；用2，3，4，…，m＋1依次標(biāo)點ui1，ui2，…，uim；用0，1循環(huán)標(biāo)邊uijuij＋1（j＝1，2，…，m－1；i＝1，2，…，n）．若f （vi）＝m＋3，則用0，1，4，5，6，…，m＋1依次標(biāo)邊viui1，viui2，…，viuim；用2，3循環(huán)標(biāo)點ui1，ui2，…，uim；用m＋3，m＋2循環(huán)標(biāo)邊uijuij＋1（j＝1，2，…，m－1；i＝1，2，…，n）．易證映射f 是圖Cn·Fm的1個正常的（2，1）－全標(biāo)號，所以λ2T（Cn·Fm）≤m＋3．綜上，有λ2T（Cn·Fm）＝m＋3．

2）n≡1（mod 2）① 當(dāng)m＝1時，由圖Cn·Fm的定義易知，Δ（Cn·Fm）＝3．所以由引理1有，λ2T（Cn·Fm）≥Δ＋2－1＝4．首先證明λ2T（Cn·Fm）＝4不成立，即標(biāo)號集｛0，1，2，3，4｝無法完成對圖Cn·Fm的正常的（2，1）－全標(biāo)號．事實上，假設(shè)存在1個映射是圖Cn·Fm的1個正常的（2，1）－全標(biāo)號．由引理2知，圖Cn·Fm的最大度點vi（i＝1，2，…，n）只能標(biāo)0或4，即或．顯然無法完成對奇數(shù)個點的正常（2，1）－全標(biāo)號，所以λT2（Cn·Fm）＝4不成立，因此

再證λT2（Cn·Fm）≤5．構(gòu)造1個映射用0，5循環(huán)標(biāo)點v1，v2，…，vn－1；用1標(biāo)點vn；用2，3循環(huán)標(biāo)邊v1v2，v2v3，…，vn－1vn；用4標(biāo)邊vnv1；用2標(biāo)點ui1（i＝1，2，…，n）．若或1，則令若，則令易證映射f是 圖Cn·Fm的1個正常的（2，1）－全標(biāo)號，所以λT2（Cn·Fm）≤5．綜上，有λT2（Cn·Fm）＝5．② 當(dāng)m≥2時，由圖Cn·Fm的定義易知．所以由引理1，有m＋3．首先證明λT2（Cn·Fm）＝m＋3不成立，即標(biāo)號集｛0，1，2，3，…，m＋3｝無法完成對圖Cn·Fm的正常 的 （2，1）－全 標(biāo) 號． 事 實 上， 假 設(shè) 存 在 1 個 映 射是圖Cn·Fm的1個正常的（2，1）－全標(biāo)號．由引理2知，圖Cn·Fm的最大度點vi（i＝1，2，…，n）只能標(biāo)0或m＋3，即或．顯然這2個數(shù)無法完成對奇數(shù)個點的正常（2，1）－全標(biāo)號，所以λT2（Cn·Fm）＝m＋3不成立，因此λT2（Cn·Fm）≥m＋4．

下證λT2（Cn·Fm）≤m＋4．構(gòu)造1個映射用0，m＋3循環(huán)標(biāo)點v1，v2，…，vn－1；用1標(biāo)點vn；用2，3循環(huán)標(biāo)邊v1v2，v2v3，…，vn－1vn，用4標(biāo)邊vnv1；若則用4，5，6，…，m＋3依次標(biāo)邊viui1，viui2，…，viuim；用2，3，4，…，m＋1依次標(biāo)點ui1，ui2，…，uim；用0，1循環(huán)標(biāo)邊uijuij＋1（j＝1，2，…，m－1；i＝2，3，…，n－1）．若，則用0，1，4，5，6，…，m＋1依次標(biāo)邊viui1，viui2，…，viuim；用2，3循環(huán)標(biāo)點ui1，ui2，…，uim；用m＋3，m＋2循環(huán)標(biāo)邊uijuij＋1（j＝1，2，…，m－1；i＝2，3，…，n－1）．

用2，3循環(huán)標(biāo)點u11，u12，…，u1m；用5，6，7，…，m＋4依次標(biāo)邊v1u11，v1u12，…，v1u1m；用0，5循環(huán)標(biāo)邊u1ju1j＋1（j＝1，2，…，m－1）；用2，3，4，5，…，m＋1依次標(biāo)點un1，un2，…，unm；用5，6，7，8，…，m＋4依次標(biāo)邊vnun1，vnun2，…，vnunm；用0，1循環(huán)標(biāo)邊unjunj＋1（j＝1，2，…，m－1）．易證映射f是圖Cn·Fm的1個正常的（2，1）－全標(biāo)號，所以λT2（Cn·Fm）≤m＋4．綜上，有λT2（Cn·Fm）＝m＋4，且當(dāng)n≡0（mod 2）時，有當(dāng)n≡1（mod 2）時，有

［1］ Griggs J R，Yeh R K．Labeling Graphs with a Condition at Distance Two［J］．SIAMJ Discrete Math，1992，5（4）：586－595．

［2］ Chang G J，ke W T，Yeh R K，et al．OnL（d，1）－labeling of Graphs［J］．Discrete Math，2000，220：57－66．

［3］ Whittles MA，Georges J P，Mauro D W．On theλ－Number ofQnand Related Graphs［J］．SIAMJ Discrete Math，1995，8（4）：499－506．

［4］ Havet F，Yu ML．（p，1）－total Labeling of Graphs［J］．Discrete Math，2008，308（4）：496－513．

［5］ 馬生全，李敬文，等．Pkn（k≡2（mod 3））的鄰點可區(qū)別的強全染色［J］．經(jīng)濟(jì)數(shù)學(xué)，2003，20（4）：77－80．

［6］ 李敬文，劉君，張忠輔，等．Cn·Fm的鄰點可區(qū)別的邊色數(shù)［J］．蘭州交通大學(xué)學(xué)報，2004，23（4）：128－130．

［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］．Ne wYork：Springer－Verlag，1998：145－177．

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

The（2，1）－total Labeling of Two Special Graphs

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

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

istinct integers；②any two adjacent edges ofG

istinctintegers；③a vertex and its incident edge receive integers that differ by at leastpin absolutevalue.The minimal number ofkis called the（p，1）－total number ofG.The（2，1）－total numbers of these graphs were given by the eternal coloring according to their feature.

（p，1）－totallabeling；（p，1）－total number；Pkngraph；Cn·Fmgraph

O157.5

A

1004－4353（2011）03－0230－04

2011 -04 -12

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