劉 歡，強會英*，白 羽，王洪申

（1.蘭州交通大學(xué) 數(shù)理學(xué)院，蘭州 730070；2.蘭州理工大學(xué) 機電工程學(xué)院，蘭州 730050）

圖的可區(qū)別染色問題是圖染色理論的一個分支，具有重要的理論意義和應(yīng)用背景.2013年，F(xiàn)landrin等［1］考慮了相鄰頂點色集合的元素之和，首次提出圖的鄰和可區(qū)別邊染色的概念，并給出一些特殊圖的鄰和可區(qū)別邊色數(shù).文獻［2-5］在此基礎(chǔ)上，研究了一些簡單圖的鄰和可區(qū)別邊染色問題.2021年，強會英等［6］在鄰和可區(qū)別邊染色的基礎(chǔ)上進行了2-距離和可區(qū)別邊染色的研究，得到無K4-子式圖的2-距離和可區(qū)別邊色數(shù)的一個上界.近幾年，不少圖論方向研究人員對蛛形圖［7-8］和蛛網(wǎng)圖［9-11］的各類染色問題做了大量的研究.本文在上述研究的基礎(chǔ)上討論了蛛形圖和蛛網(wǎng)圖的2-距離和可區(qū)別邊染色問題，得到蛛形圖、蛛網(wǎng)圖的2-距離和可區(qū)別邊色數(shù).

文中討論的圖都是有限、無向的簡單連通圖，V（G）和E（G）分別表示圖G的頂點集和邊集，Δ（G）表示圖G的最大度．令C=｛1，2，…，k｝為k-色集（k是正整數(shù)），C（vij）表示點vij的色集合，符號｛x1，x2，…，xn｝→｛a1，a2，…，an｝表示用顏色序列a1，a2，…，an去染元素序列x1，x2，…，xn，其它未加說明的術(shù)語，請參考文獻［12-14］．

1 預(yù)備知識

定義1令f是圖G的一個正常［k］-邊染色，若對任意uv∈E（G），有S*（u）≠S*（v），其中S*（u）=則稱f為圖G的鄰和可區(qū)別邊染色［2］．染色中用到的最小k值稱為G的鄰和可區(qū)別邊色數(shù)，記為

定義2令f是圖G的一個正常［k］-邊染色，若對任意u，v∈V（G），dG（u，v）≤2，都有S（u）≠S（v），其中，則稱f為圖G的2-距離和可區(qū)別邊染色［6］．染色中用到的最小值k稱為G的2-距離和可區(qū)別邊色數(shù)，記為

定義3從v0出發(fā)有k（k≥3）條路，除v0外，每條路有k個點，共有n（n=k2+1）個點的圖稱為蛛形圖［7］，記為Sk，它的頭點用v0表示，刪去v0后，這k條路分別記為pi=vi1vi2…vik（1≤i≤k），eij表示邊vi（j-1）vij（1≤i≤k，1≤j≤k）．

定義4在蛛形圖Sk中添加邊v1jv2j，v2jv3j，v3jv4j，…，v（k-1）jvkj，vkjv1j（1≤j≤k-1）所得到的圖稱為蛛網(wǎng)圖［9］，記為wk．

引理1對于簡單圖Δ（G）．若圖G有相鄰最大度點，則

引理2若簡單圖G在2-距離內(nèi)有兩個最大度點，則

2 主要結(jié)論

定理1對于蛛形圖

證明根據(jù)蛛形圖的結(jié)構(gòu)，下面分兩種情形去討論．

情形1當(dāng)k=3時，不存在相鄰的最大度點，根據(jù)引理1知，．假設(shè)存在S3的2-距離和可區(qū)別3-邊染色，設(shè)色集合C=｛1，2，3｝，則C（v0）=｛1，2，3｝，要滿足正常的邊染色且距離小于2的色集合和值不同，令f（v0v11）=1，f（v11v12）=2，則f（v12v13）=3，否則S（v11）=S（v12），又由邊v11v12和邊v12v13的色數(shù)不同且分別屬于C（v11）和C（v13），此時S（v11）=S（v13）=3，出現(xiàn)矛盾，故不存在S3的2-距離和可區(qū)別3-邊染色．

下面給出蛛形圖S3的一個2-距離和可區(qū)別4-邊染色：

按上述染色法各點色集合與色數(shù)和如表1所列.

表1 圖S3各點色集合C（vij）和色數(shù)和S（vij）的情況Tab．1 Sets of colors C（vij）and the chromatic number sum S（vij）of each vertex in Graph S3

從表1易見f是圖S3的2-距離和可區(qū)別4-邊染色.

情形2當(dāng)k≥4時，不存在相鄰的最大度點，根據(jù)引理1知

當(dāng)k=4、5時，圖S4、S5不適合下述染色方法，現(xiàn)給出S4、S5具體染色方法，如圖1和圖2所示．

圖1 蛛形圖S4Fig．1 Spider graph of S4

圖2 蛛形圖S5Fig．2 Spider graph of S5

當(dāng)k≥6時，下面給出圖Sk的一個2-距離和可區(qū)別k-邊染色：

如下定義一個從E（Sk）→｛1，2，3，…，k｝的映射f，f（ei1）=i（1≤i≤k）；f（v11v12）=k-1；f（vi1vi2）=k（2≤i≤k-1）；f（vk1vk2）=1．

此時，C（v0）=｛1，2，3，4，…，k｝；C（v11）=｛1，k-1｝；C（vi1）=｛i，k｝（2≤i≤k-1）；C（vk1）=｛1，k｝．得到i+k；S（vk1）=k+1．

其它的邊vijvi（j+1）（j≥2）分成如下兩種情形討論：

1）當(dāng)k≡1（mod 3）時，各邊染色情況分組討論：

C（v12）=｛2，k-1｝；C（v1k）=｛1｝；C（v1j）依次按照｛1，2｝、｛1，3｝、｛2，3｝循環(huán)（3≤j≤k-1）．得到S（v12）=k+1；S（v1k）=1；S（v1j）按照3，4，5循環(huán)出現(xiàn)．

C（vk2）=｛1，3｝；C（vkk）=｛2｝；C（vkj）依次按照｛3，2｝、｛2，1｝、｛1，3｝循環(huán)（3≤j≤k-1）．得到S（vk2）=4；S（vkk）=2；S（vkj）按照5，3，4循環(huán)出現(xiàn)．

C（vi2）=｛1，k｝（2≤i≤k-1）；C（vik）=｛2｝（2≤i≤k-1）；C（vij）依次按照｛1，2｝、｛2，3｝、｛3，1｝循環(huán)（2≤i≤k-1，3≤j≤k-1）．得到S（vi2）=k+1（2≤i≤k-1）；S（vik）=2；S（vij）按照3，5，4循環(huán)出現(xiàn)．

由①②③知f是圖Sk的2-距離和可區(qū)別k-邊染色．

2）當(dāng)k≠1（mod 3）時，各邊染色情況分組討論：

此時C（v12）=｛2，k-1｝；C（vk2）=｛1，2｝；C（vij）依次按照｛2，3｝、｛1，3｝、｛1，2｝循環(huán)（i=1，k；3≤得到S（v12）=k+1；S（vk2）=3；S（v1j）、S（vkj）按照5，4，3循環(huán)出現(xiàn)（3≤j≤k-1）；S（v1k）=S（vkk）=

此時C（vi2）=｛1，k｝（2≤i≤k-1），C（vij）依次按照｛1，3｝、｛2，3｝、｛2，1｝循環(huán)（2≤i≤k-1，3≤得到S（vi2）=k+1（2≤i≤k-1）；S（vij）按照4，5，3循環(huán)出現(xiàn)

由①②知f是圖Sk的2-距離和可區(qū)別k-邊染色．

綜上所述，此定理成立．

定理2對于蛛網(wǎng)圖Wk（k≥3），則

證明根據(jù)蛛網(wǎng)圖的結(jié)構(gòu)，下面分3種情形去討論．

情形1當(dāng)k=3時，存在相鄰的最大度點，根據(jù)引理2知，χ′2-∑（G）≥χ′∑（G）≥Δ（G）+1=5．

假設(shè)存在W3的2-距離和可區(qū)別5-邊染色，設(shè)色集合C=｛1，2，3，4，5｝，以點v11為例，要滿足正常的邊染色且距離小于2的色集合和值不同，需與點v11相鄰的點v12、v31、v21達到色集合和值不同，與點v11達到2-距離的點v22和v32，同樣需要保證其2-距離和可區(qū)別邊染色．由于C45=5，而蛛網(wǎng)圖W3中存在6個4度頂點需要達到色集合和值不同．故不存在W3的2-距離和可區(qū)別5-邊染色．

下面給出蛛網(wǎng)圖W3的一個2-距離和可區(qū)別6-邊染色f．

按上述染法各點色集合與色數(shù)和如表2所列.

表2 圖W3各點色集合C（vij）和色數(shù)和S（vij）的情況Tab．2 Sets of colors C（vij）and the chromatic number sum S（vij）of each vertex in Graph W3

從表2易見f是圖W3的2-距離和可區(qū)別6-邊染色．

情形2當(dāng)4≤k≤6時，分以下兩種情況討論：

①當(dāng)k=4時，存在相鄰的最大度點，根據(jù)引理2知根據(jù)情形1當(dāng)k=3時可知，不存在W4的2-距離和可區(qū)別5-邊染色．假設(shè)存在W4的2-距離和可區(qū)別6-邊染色，設(shè)色集合C=｛1，2，3，4，5，6｝，以點v12為例，要滿足正常的邊染色且距離小于2的色集合和值不同，需保證與點v122-距離內(nèi)的11個4度頂點色集合和值不同．由于色中選取4種元素其色集合和值有10，11，…，18共9種情況．蛛網(wǎng)圖W4中2-距離內(nèi)最多存在11個4度頂點需要達到色集合和值不同，9＜11．故不存在W4的2-距離和可區(qū)別6-邊染色．

下面給出圖W4的一個2-距離和可區(qū)別7-邊染色f，如圖3所示.

圖3 蛛網(wǎng)圖W4Fig．3 Spider web of graph W4

此時C（v0）=｛4，5，6，7｝，S（v0）=22．其余各點情況如表3所列，易見f是圖W4的2-距離和可區(qū)別7-邊染色．

表3 圖W4各點色數(shù)和S（vij）的情況Tab．3 Chromatic number sum in Graph W4

②k=5，6時，圖W5和W6均不存在2-距離和可區(qū)別6-邊染色，理由同①k=4的情況，圖W5和W6的一個2-距離和可區(qū)別7-邊染色f如圖4和圖5所示．

圖4 蛛網(wǎng)圖W5Fig．4 Spider web of graph W5

圖5 蛛網(wǎng)圖W6Fig．5 Spider web of graph W6

按上述染法蛛網(wǎng)圖W5有C（v0）=｛1，2，3，4，5｝，S（v0）=15．蛛網(wǎng)圖W6有C（v0）=｛1，2，3，4，5，6｝，S（v0）=21.其余各點情況如表4及表5所列.

從表4和表5易見f是圖W5和W6的2-距離和可區(qū)別7-邊染色.

表4 圖W5各點S（vij）的情況Tab．4 Chromatic number sum in Graph W5

表5 圖W6各點S（vij）的情況Tab．5 Chromatic number sum in Graph W6

情形3當(dāng)k≥7時，不存在相鄰的最大度點，根據(jù)引理1得．設(shè)色集合為｛1，2，3，…，k｝，圖Wk中除葉子點vik（1≤i≤k）以及點v0之外，均為4度頂點，從色集合中選取4種元素其和值可能出現(xiàn)的數(shù)值為1+2+3+4=10，至k+（k-1）+（k-2）+（k-3）=4k-6，共有（4k-15）種和值情況．接下來對蛛網(wǎng)圖Wk的路數(shù)k做歸納．

當(dāng)k=7時，以點v12為例，要滿足正常的邊染色且距離小于2的色集合和值不同，需保證點v12與2-距離內(nèi)相關(guān)聯(lián)的共13個頂點色集合和值不同．其中v0點色集合為｛1，2，3，…，k｝，與其它4度頂點已保持不同．

圖6 蛛網(wǎng)圖W7Fig．6 Spider web of graph W7

假設(shè)對路數(shù)小于等于k-1的蛛網(wǎng)圖Wk-1上述結(jié)論成立.

下證對于k條路的蛛網(wǎng)圖，此結(jié)論依然成立．由歸納假設(shè)知，Wk-1存在2-距離和可區(qū)別（k-1）邊染色φ．根據(jù)蛛網(wǎng)圖Wk-1到Wk的結(jié)構(gòu)特點，分成以下四種情況去討論.

1）增加點v1k，v2k，…，vkk及邊v1，k-1v1k，v2，k-1v2k，…，vk，k-1vkk．這些點全是葉子點，與其它4度頂點可達到2-距離和可區(qū)別邊染色，且這些葉子點兩兩之間距離大于2，不妨令這些邊色數(shù)分別從f（vi，k-1vi，k）=｛1，2，3，…，k｝-f（vi，k-2vi，k-1）中取得，故k色可滿足這些葉子點2-距離和可區(qū)別邊染色．

2）增加k條邊v1，k-1v2，k-1，v2，k-1v3，k-1，…，vk-1，k-1vk，k-1，vk，k-1v1，k-1．以點v3，k-1為例，需保證與點v3，k-2，v3，k-3，v4，k-1，v4，k-2，v5，k-1，v2，k-1，v2，k-2，v1，k-1達到2-距離和可區(qū)別邊染色．根據(jù)路數(shù)等于k-1的蛛網(wǎng)圖Wk-1染色情況分析，v3，k-2，v3，k-3，v4，k-2，v2，k-2已達到2-距離和可區(qū)別邊染色，去掉｛S（v3，k-2），S（v3，k-3），S（v4，k-2），S（v2，k-2）｝這4種和數(shù)情況下，并添加k色的基礎(chǔ)上，使其余點達到2-距離和可區(qū)別邊染色，共有（4k-15）種情況，在（C4k-4）種可能性中，使用k色足夠使得蛛網(wǎng)圖Wk達到2-距離和可區(qū)別邊染色．

3）增加路pk上邊v0vk1，vk1vk2，…，vk，k-1vk，k．在情況1、2的染色基礎(chǔ)上，僅需考慮v0vk1，vk1vk2，…，vk，k-2vk，k-1，根據(jù)計算得，（k-1）色和k色相差（4k-15）-［4（k-1）-15］=4種．故可給pk路上點色集合和值賦予該4種情況，讓該4種和值情況以一定順序循環(huán)，不妨可以讓S（vk1）=4k-9，S（vk2）=4k-8，S（vk3）=4k-7，S（vk4）=4k-6，…，與Wk-1的染色情況可達到和值不同，故達到2-距離和可區(qū)別邊染色．

4）對于圖Wk-1至圖Wk中，因增加pk路造成pk-1和p1路間需重新染色，把Wk-1中pk路與p1路間相連的邊顏色賦予給Wk中pk-1路和pk路間相連的對應(yīng)邊，對于pk路與p1路間的連邊，①以點v12為例，與點v12相關(guān)聯(lián)的4條邊，在φ染色下有3條邊色數(shù)已確定，現(xiàn)從k種色中去掉這3種顏色，給第4條邊進行染色，在中有（k-3）種情況，故存在（k-3）種和值情況，點v12有12個4度點需要達到2-距離和可區(qū)別邊染色，12+（k-3）≤4k-15，使用k色可達到2-距離和可區(qū)別邊染色．②對于p1路上其他點，最多有13個4度點需要達到2-距離和可區(qū)別邊染色，存在（4k-15）-13種和值染法，用k色可達到2-距離和可區(qū)別邊染色．③其中當(dāng)k≥10時，點v11為特例，有（k+4）個點需要達到2-距離和可區(qū)別邊染色，（k+4）+（k-3）=2k-1，遠小于（4k-15）種和值情況，從而達到2-距離和可區(qū)別邊染色．

綜上所述，圖Wk滿足2-距離和可區(qū)別k-邊染色，定理成立．