一類二部圖生成的廣義格子圖的鄰點(diǎn)可區(qū)別邊染色

劉信生，緱 艷，姚 兵，劉元元

（西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州730070）

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

圖的染色問題是圖論的重要研究?jī)?nèi)容之一，具有重要的理論價(jià)值和實(shí)際意義.由不同實(shí)際問題引出了不同的染色概念，如倉庫數(shù)的研究、地圖染色、有線通信網(wǎng)、無線通信網(wǎng)等引出的鄰點(diǎn)可區(qū)別邊染色問題，得到國(guó)內(nèi)外圖論研究者的關(guān)注.近些年來，雖然許多學(xué)者在這一領(lǐng)域已經(jīng)取得了很多成果［1－8］，但這方面的研究工作尚屬開始，許多猜想的解決處于特殊圖的驗(yàn)證階段.本文定義了一類2維廣義格子圖H2（G，n，m；k1，k2），且通過從圖的結(jié)構(gòu)出發(fā)，利用構(gòu)造染色的方法，得到了圖H2（Kp，p，n，m；p，p）的鄰點(diǎn)可區(qū)別邊色數(shù).從而驗(yàn)證了鄰點(diǎn)可區(qū)別邊色數(shù)猜想.

定義1［1］設(shè)G（V，E）是階數(shù)至少為3的簡(jiǎn)單連通圖，k－是正整數(shù).若G（V，E）是一個(gè)k－正常邊染色f 滿足：?uv∈E（G），S（u）≠S（v），其中S（u）＝｛f（uv）｜uv∈E（G）｝，則稱f 為G 的一個(gè)k－鄰點(diǎn)可區(qū)別邊染色，簡(jiǎn)記為k－AVDPEC，且稱χ′a（G）＝min｛k｜G 存在k－AVDPEC｝為G 的鄰點(diǎn)可區(qū)別邊色數(shù).

猜想［1］設(shè)圖G 是階數(shù)至少為3的簡(jiǎn)單連通圖，若G≠C5，則χ′a（G）≤Δ＋2.

定義2 把一個(gè)根圖G 做n 個(gè)拷貝，記做G（1），G（2），…，G（n）.連接每相鄰兩個(gè)G（i）與G（i＋1）（i＝1，2，…，n－1）間的k1對(duì)頂點(diǎn)，所得的圖記做H1（G，n；k1），并稱為1 維廣義格子圖，見圖1.然后把H1（G，n；k1）做m 個(gè)拷貝，記做H（1）1（G，n；k1），H（2）1（G，n；k1），…，H（m）1（G，n；k1）.將H（j）1（G，n；k1）中的每個(gè)根圖記為G（1，j），G（2，j），…，G（n，j）（j＝1，2，…，m）.連接G（i，j）與G（i，j＋1）（i＝1，2，…，n；j＝1，2，…，m－1）間的k2對(duì)頂點(diǎn)，所得的圖記做H2（G，n，m；k1，k2），并稱為2維廣義格子圖，見圖2.

注 定義2中的2維廣義格子圖不難推廣到t維廣義格子圖Ht（G，n1，n2，…，nt；k1，k2，…，kt）.

圖1 1維廣義格子圖H1（G，n；k1）

引理1［1］對(duì)階數(shù)不小于3的簡(jiǎn)單連通圖G，有χ′a（G）≥Δ.若G 中存在相鄰的最大度點(diǎn)，則

其他的相關(guān)術(shù)語和記號(hào)，可參見文獻(xiàn)［9］.

圖2 2維廣義格子圖H2（G，n，m；k1，k2）

2 主要結(jié)果

定理1 對(duì)n≥3，m≥3，有χ′a（H2（Kp，p，n，m；p，p））＝p＋6.

證明 把根圖Kp，p做n 個(gè) 拷 貝，記 做Kp（1，p），Kp（2，p），…，Kp（n，p）.且 記V（Kp（i，）p）＝Xi∪Yi，Xi∩Yi＝?，｜Xi｜＝｜Yi｜＝p，其 中Xi＝｛v1（i），v2（i），…，vp（i）｝，Yi＝｛u1（i），u2（i），…，up（i）｝（i＝1，2，…，n）.連 接vj（i）與vj（i＋1），uj（i）與uj（i＋1）（i＝1，2，…，n－1；j＝1，2，…，p）后所得的圖記做H1（Kp，p，n；p）.然后把H1（Kp，p，n；p）做m 個(gè)拷貝，記做H1（1）（Kp，p，n；p），H1（2）（Kp，p，n；p），…，H1（m）（Kp，p，n；p）.其中，H1（j）（Kp，p，n；p）中的每個(gè)根圖記為Kp（1，p，j），Kp（2，p，j），…，Kp（n，p，j）（j＝1，2，…，m）.且 記V（Kp（i，，pj））＝Xi，j∪Yi，j，Xi，j∩Yi，j＝?，｜Xi，j｜＝｜Yi，j｜＝p，其中Xi，j＝｛v1（i，j），v2（i，j），…，vp（i，j）｝，Yi，j＝｛u1（i，j），u2（i，j），…，up（i，j）｝（i＝1，2，…，n；j＝1，2，…，m）.連接vt（i，j）與vt（i，j＋1），ut（i，j）與ut（i，j＋1）（i＝1，2，…，n；j＝1，2，…，m－1；t＝1，2，…，p）后所得到的圖記做H2（Kp，p，n，m；p，p），見圖3.

圖3 2維廣義格子圖H2（Kp，p，n，m；p，p）

由于圖H2（Kp，p，n，m；p，p）中存在相鄰的最大度頂點(diǎn)，且Δ（H2（Kp，p，n，m；p，p））＝p＋4，由引理1可知，χ′a（H2（Kp，p，n，m；p，p））≥p＋5，如果χ′a（H2（Kp，p，n，m；p，p））＝p＋5，那么不失一般性，可設(shè)（在這里，我們用（u）表示S（u）在顏色構(gòu)成的集合｛1，2，…，p＋6｝中的補(bǔ)集）.那么點(diǎn)vt（i，j）的所有鄰點(diǎn)的補(bǔ)集合里都必須包含色q.由于無論p是奇數(shù)還是偶數(shù)，由圖H2（Kp，p，n，m；p，p）的結(jié)構(gòu)可知，這些點(diǎn)中的任意兩點(diǎn)之間都只有偶數(shù)條邊相連，故不存在這p＋4個(gè)點(diǎn)的完美匹配.因此，用p＋5種顏色不能對(duì)圖H2（Kp，p，n，m；p，p）進(jìn)行鄰點(diǎn)可區(qū)別邊染色，故χ′a（H2（Kp，p，n，m；p，p））≥p＋6，為證χ′a（H2（Kp，p，n，m；p，p））＝p＋6，只需給出H2（Kp，p，n，m；p，p）的一個(gè)p＋6－AVDPEC即可.我們分兩種情況來證明結(jié)論.

情況Ⅰ 當(dāng)p≡1（mod 2）時(shí)，分以下四個(gè)步驟給出具體染色f：

ⅰ 對(duì)拷貝H1（1）（Kp，p，n；p）的邊進(jìn)行染色，令f 為：

當(dāng)h≡1（mod 2）時(shí)，f（vi（h，1）uj（h，1））＝［j＋2（i－1）］p＋2（i＝1，2，…，p；j＝1，2，…，p；h＝1，2，…，n）.

當(dāng)h≡0（mod 2）時(shí)，f（vi（h，1）uj（h，1））＝［j＋2（j－1）］p＋2（i＝1，2，…，p；j＝1，2，…，p；h＝1，2，…，n）.

ⅱ 對(duì)拷貝H1（2）（Kp，p，n；p）的邊進(jìn)行染色，令f 為：

當(dāng)h≡1（mod 2）時(shí)，f（vi（h，1）uj（h，1））＝［j＋2（j－1）］p＋2（i＝1，2，…，p；j＝1，2，…，p；h＝1，2，…，n）.

當(dāng)h≡0（mod 2）時(shí)，f（vi（h，1）uj（h，1））＝［j＋2（i－1）］p＋2（i＝1，2，…，p；j＝1，2，…，p；h＝1，2，…，n）.

ⅲ 拷貝H（j）1（Kp，p，n；p）（j≡1（mod 2）且3≤j≤m）的邊染色與H（1）1（Kp，p，n；p）的邊染色完全一致，拷貝H（j）1（Kp，p，n；p）（j≡0（mod 2）且4≤j≤m）的邊染色與H（2）1（Kp，p，n；p）的邊染色完全一致.

ⅳ 對(duì)每相鄰兩個(gè)拷貝H（j）1（Kp，p，n；p）與H（j＋1）1（Kp，p，n；p）（1≤j≤m－1）之間的邊進(jìn)行染色，令f 為：

下證明以上染色是鄰點(diǎn)可區(qū)別的：

由圖H2（Kp，p，n，，m；p，p）的結(jié)構(gòu)可知，只需證明中的各頂點(diǎn)是鄰點(diǎn)可區(qū)別的即可.因此，當(dāng)i≡0（mod 2）且j≡0（mod 2）或當(dāng)i≡1（mod 2）且j≡1（mod 2）時(shí)，對(duì)f 有當(dāng)i≡0（mod 2）且j≡1（mod 2）或當(dāng)i≡1（mod 2）且j≡0（mod 2）時(shí)，對(duì)f有

綜上，易看出當(dāng)p≡1（mod 2）時(shí)，圖H2（Kp，p，n，m；p，p）中任意相鄰兩頂點(diǎn)的色集合均不同，故f是圖H2（Kp，p，n，m；p，p）的一個(gè)p＋6－AVDPEC.且滿足鄰點(diǎn)可區(qū)別邊色數(shù)猜想.

情況Ⅱ 當(dāng)p≡0（mod 2）時(shí)，分以下四個(gè)步驟給出具體染色f：

ⅰ 對(duì)拷貝H（1）1（Kp，p，n；p）的邊進(jìn)行染色，令f 為：

ⅱ 對(duì)拷貝H（2）1（Kp，p，n；p）的邊進(jìn)行染色，令f 為：

ⅲ 拷貝H（j）1（Kp，p，n；p）（j≡1（mod 2）且3≤j≤m）的邊染色與H（1）1（Kp，p，n；p）的邊染色完全一致，拷貝H（j）1（Kp，p，n；p）（j≡0（mod 2）且4≤j≤m）的邊染色與H（2）1（Kp，p，n；p）的邊染色完全一致.

ⅳ對(duì)每相鄰兩個(gè)拷貝H（j）1（Kp，p，n；p）與H（j＋1）1（Kp，p，n；p）（1≤j≤m－1）之間的邊進(jìn)行染色，令f為:

下面證明以上染色是鄰點(diǎn)可區(qū)別的：

由圖H2（Kp，p，n，，m；p，p）的結(jié)構(gòu)可知，只需證明中的各頂點(diǎn)是鄰點(diǎn)可區(qū)別的即可.因此，當(dāng)i≡0（mod 2）且j≡0（mod 2）或當(dāng)i≡1（mod 2）且j≡1（mod 2）時(shí)，對(duì)f 有且且6≤t≤p.當(dāng)i≡0（mod 2）且j≡1（mod 2）或當(dāng)i≡1（mod 2）且j≡0（mod 2）時(shí)，對(duì)f 有且0（mod 2）且

綜上，易看出當(dāng)p≡0（mod 2）時(shí)，圖H2（Kp，p，n，m；p，p）中任意相鄰兩頂點(diǎn)的色集合均不同，故f是圖H2（Kp，p，n，m；p，p）的一個(gè)p＋6－AVDPEC，且滿足鄰點(diǎn)可區(qū)別邊色數(shù)猜想.