劉秀麗

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

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

劉秀麗

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

研究了與頻道分配有關(guān)的一種染色問題——（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.稱最小的數(shù)k為圖G的（p，1）－全標(biāo)號(hào)數(shù).根據(jù)所構(gòu)造圖的特征，利用窮染法得到了這些圖的（2，1）－全標(biāo)號(hào)數(shù).

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

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

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

定義1［4］設(shè)p是1個(gè)非負(fù)整數(shù)，圖G的1個(gè)k－（p，1）－全標(biāo)號(hào)是1個(gè)映射f∶V（G）∪E（G）→｛k｝，使得：①G的任2個(gè)相鄰的頂點(diǎn)u和v，有0，1，…，②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的（p1－全標(biāo)號(hào)對(duì)應(yīng)于圖G的全染色，這種情況也被廣泛研究，因此，圖的（p，1）－全標(biāo)號(hào)不僅與圖的距離2標(biāo)號(hào)問題密切相關(guān)，而且也是對(duì)圖的全染色的一種推廣.本文將主要討論p＝2時(shí)即圖G的（2，1）－全標(biāo)號(hào).

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

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

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

引理2［7］若圖G滿足λ2T（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.

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

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

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

定理1 對(duì)圖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)號(hào)集｛0，1，2，3，4，5｝無法完成對(duì)圖Pkn的正常的（2，1）－全標(biāo)號(hào).反證法.假設(shè)存在1個(gè)映射是圖Pkn的1個(gè)正常的（2，1）－全標(biāo)號(hào).由引理2知，圖Pkn的最大度點(diǎn)只能標(biāo)0或5.不妨設(shè)V（Pn）＝ ｛v1，v2，…，vn｝.若n≥3k＋2，則存在1個(gè)最大度點(diǎn)vi至少與3個(gè)最 大度點(diǎn)vj，vm，vl相連.由（2，1）－全標(biāo)號(hào)的定義知，與0和5相差2的只有2和3這2個(gè)數(shù)，無法完成對(duì)vivj，vivm，vivl這3條邊的標(biāo)號(hà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)點(diǎn)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個(gè)正常的（2，1）－全標(biāo)號(hào)，所以λT2（Pkn）≤6.②k＝4（3m－1），m＝1，2，3，…，即k＝8，20，32，44，….用0，4，6循環(huán)標(biāo)點(diǎn)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個(gè)正常的（2，1）－全標(biāo)號(hào)，所以λT2（Pkn）≤6.

2）k≡1（mod 2）.用0，1循環(huán)標(biāo)點(diǎn)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個(gè)正常的（2，1）－全標(biāo)號(hào)，所以λT2（Pkn）≤6．

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

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

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

② 當(dāng)m ≥2時(shí)，由圖Cn·Fm的定義易知，Δ（Cn·Fm）＝m＋2．所以由引理1有，λT2（Cn·Fm）≥Δ＋2－1＝m＋3．下證λT2（Cn·Fm）≤m＋3．構(gòu)造1個(gè)映射．用0，m＋3循環(huán)標(biāo)點(diǎn)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)點(diǎn)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)點(diǎn)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個(gè)正常的（2，1）－全標(biāo)號(hào)，所以λ2T（Cn·Fm）≤m＋3．綜上，有λ2T（Cn·Fm）＝m＋3．

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

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

下證λT2（Cn·Fm）≤m＋4．構(gòu)造1個(gè)映射用0，m＋3循環(huán)標(biāo)點(diǎn)v1，v2，…，vn－1；用1標(biāo)點(diǎn)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)點(diǎn)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)點(diǎn)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)點(diǎn)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)點(diǎn)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個(gè)正常的（2，1）－全標(biāo)號(hào)，所以λT2（Cn·Fm）≤m＋4．綜上，有λT2（Cn·Fm）＝m＋4，且當(dāng)n≡0（mod 2）時(shí)，有當(dāng)n≡1（mod 2）時(shí)，有

［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））的鄰點(diǎn)可區(qū)別的強(qiáng)全染色［J］．經(jīng)濟(jì)數(shù)學(xué)，2003，20（4）：77－80．

［6］ 李敬文，劉君，張忠輔，等．Cn·Fm的鄰點(diǎn)可區(qū)別的邊色數(shù)［J］．蘭州交通大學(xué)學(xué)報(bào)，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àn)閳D論與組合優(yōu)化.