劉 歡，強(qiáng)會(huì)英*，白 羽，王洪申

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

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

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

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

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

定義2令f是圖G的一個(gè)正常［k］-邊染色，若對(duì)任意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個(gè)點(diǎn)，共有n（n=k2+1）個(gè)點(diǎn)的圖稱為蛛形圖［7］，記為Sk，它的頭點(diǎn)用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對(duì)于簡(jiǎn)單圖Δ（G）．若圖G有相鄰最大度點(diǎn)，則

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

2 主要結(jié)論

定理1對(duì)于蛛形圖

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

情形1當(dāng)k=3時(shí)，不存在相鄰的最大度點(diǎn)，根據(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），此時(shí)S（v11）=S（v13）=3，出現(xiàn)矛盾，故不存在S3的2-距離和可區(qū)別3-邊染色．

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

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

表1 圖S3各點(diǎn)色集合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時(shí)，不存在相鄰的最大度點(diǎn)，根據(jù)引理1知

當(dāng)k=4、5時(shí)，圖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時(shí)，下面給出圖Sk的一個(gè)2-距離和可區(qū)別k-邊染色：

如下定義一個(gè)從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．

此時(shí)，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）時(shí)，各邊染色情況分組討論：

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）時(shí)，各邊染色情況分組討論：

此時(shí)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）=

此時(shí)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對(duì)于蛛網(wǎng)圖Wk（k≥3），則

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

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

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

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

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

表2 圖W3各點(diǎn)色集合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時(shí)，分以下兩種情況討論：

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

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

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

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

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

②k=5，6時(shí)，圖W5和W6均不存在2-距離和可區(qū)別6-邊染色，理由同①k=4的情況，圖W5和W6的一個(gè)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.其余各點(diǎn)情況如表4及表5所列.

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

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

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

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

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

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

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

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

1）增加點(diǎn)v1k，v2k，…，vkk及邊v1，k-1v1k，v2，k-1v2k，…，vk，k-1vkk．這些點(diǎn)全是葉子點(diǎn)，與其它4度頂點(diǎn)可達(dá)到2-距離和可區(qū)別邊染色，且這些葉子點(diǎn)兩兩之間距離大于2，不妨令這些邊色數(shù)分別從f（vi，k-1vi，k）=｛1，2，3，…，k｝-f（vi，k-2vi，k-1）中取得，故k色可滿足這些葉子點(diǎn)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．以點(diǎn)v3，k-1為例，需保證與點(diǎn)v3，k-2，v3，k-3，v4，k-1，v4，k-2，v5，k-1，v2，k-1，v2，k-2，v1，k-1達(dá)到2-距離和可區(qū)別邊染色．根據(jù)路數(shù)等于k-1的蛛網(wǎng)圖Wk-1染色情況分析，v3，k-2，v3，k-3，v4，k-2，v2，k-2已達(dá)到2-距離和可區(qū)別邊染色，去掉｛S（v3，k-2），S（v3，k-3），S（v4，k-2），S（v2，k-2）｝這4種和數(shù)情況下，并添加k色的基礎(chǔ)上，使其余點(diǎn)達(dá)到2-距離和可區(qū)別邊染色，共有（4k-15）種情況，在（C4k-4）種可能性中，使用k色足夠使得蛛網(wǎng)圖Wk達(dá)到2-距離和可區(qū)別邊染色．

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

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

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