摘要： 用結(jié)構(gòu)分析法完整刻畫(huà)單圈圖U的鄰點(diǎn)全和可區(qū)別全染色， 并得到當(dāng)

UCn且n0（mod 3）時(shí)， ftndiΣ（U）=Δ（U）+2; 其他情況下， ftndiΣ（U）=Δ（U）+1.

表明鄰點(diǎn)全和可區(qū)別全染色猜想在任意單圈圖上都成立.

關(guān)鍵詞： 單圈圖; 正常全染色; 鄰點(diǎn)全和可區(qū)別全染色; 鄰點(diǎn)全和可區(qū)別全色數(shù)

中圖分類(lèi)號(hào)： O157.5" 文獻(xiàn)標(biāo)志碼： A" 文章編號(hào)： 1671-5489（2024）03-0497-06

Neighbor Full Sum Distinguishing Total Coloring of" Unicyclic Graph

LI Zhijun， WEN Fei

（Institute of Applied Mathematics， Lanzhou Jiaotong University， Lanzhou 730070， China）

Abstract： By using structural analysis method， we completely characterized the neighbor full sum dis

tinguishing total coloring of unicyclic graph U， and obtained that ftndiΣ（U）=Δ（U）+2 when UCn and n0（mod 3），" ftndiΣ

（U）=Δ（U）+1 in other cases. This result" shows that the neighbor full sum distinguishing total coloring conjecture" holds on any unicyclic graph.

Keywords： unicyclic graph; proper total coloring;" neighbor full sum distinguishing total coloring; neighbor full sum distinguishing total chromatic number

收稿日期： 2023＼|08＼|28." 網(wǎng)絡(luò)首發(fā)日期： 2024＼|05＼|09.

第一作者簡(jiǎn)介： 李志軍（1998—）， 男， 漢族， 碩士研究生， 從事圖染色的研究， E-mail： lzj12282023@163.com. 通信作者簡(jiǎn)介

： 文" 飛（1984—）， 男， 漢族， 博士， 教授， 從事圖染色和圖譜理論的研究， E-mail： wenfei@lzjtu.edu.cn.

基金項(xiàng)目： 國(guó)家自然科學(xué)基金（批準(zhǔn)號(hào)： 11961041； 12261055）和甘肅省自然科學(xué)基金（批準(zhǔn)號(hào)： 21JR11RA135）.

網(wǎng)絡(luò)首發(fā)地址： https：//link.cnki.net/urlid/22.1340.O.20240508.0957.001.

1" 引言及主要結(jié)果

本文考慮的圖均為無(wú)向簡(jiǎn)單連通圖， 設(shè)G=（V，E）是一個(gè)簡(jiǎn)單圖， 其中V（G）表示G的頂點(diǎn)集， E（G）表示G的邊集. 如果G不含孤立邊， 則G稱(chēng)為正常圖. 對(duì)

任意的v∈V（G）， 用dG（v）（或d（v））表示點(diǎn)v的度， Δ（G）表示G的最大度. 用NG（v）（或N（v））表示頂點(diǎn)v在G中所有鄰點(diǎn)構(gòu)成的集合.

圖染色問(wèn)題在計(jì)算機(jī)科學(xué)、 通訊網(wǎng)絡(luò)、 交通運(yùn)輸?shù)阮I(lǐng)域應(yīng)用廣泛. 目前， 關(guān)于圖染色的研究已有很多結(jié)果， 例如： Karoński等［1］首次提出了圖的鄰和可區(qū)

別邊染色； 張忠輔等［2］提出了圖的鄰點(diǎn)強(qiáng)可區(qū)別全染色的概念及相關(guān)問(wèn)題； Przybylo等［3］提出了圖的鄰和可區(qū)別全染色; Pils＇niak等［4］

研究了一些特殊圖的鄰和可區(qū)別全色數(shù); Flandrin等［5］定義了圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色， 研究了一些圖類(lèi)的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù)， 并在該染色的基礎(chǔ)上提出了

鄰點(diǎn)全和可區(qū)別全染色. 崔福祥等［6］研究了路、 圈、 星、 輪、 完全二部圖、 完全圖以及樹(shù)的鄰點(diǎn)全和可區(qū)別全色數(shù)， 并給出了圖的鄰點(diǎn)全和可區(qū)別全染色的概念.

定義1［6］" 設(shè)f： V（G）∪E（G）→{1，2，…，k}是圖G的一個(gè)正常k-全染色. 令（v）=f（v）+∑v∈ef（e）+∑u∈

N（v）f（u）， 其中N（v）={u∈V（G）uv∈E（G）}. 對(duì)任意的uv∈E（G）， 若（u）≠（v）成立， 則稱(chēng)f是圖G的一個(gè)鄰點(diǎn)全和可區(qū)別

k-全染色， 簡(jiǎn)記為k-NFSDTC. 將所用的最小顏色數(shù)k稱(chēng)為G的鄰點(diǎn)全和可區(qū)別全色數(shù)， 記作ftndiΣ（G）. 即

ftndiΣ（G）=min{kG具有一個(gè)k-鄰點(diǎn)全和可區(qū)別全染色}.

特別地， 在圖G的一個(gè)正常k-全染色f下， 如果對(duì)任意的uv∈E（G）， 若（u）≠（v）成立， 則稱(chēng)u和v在f下是鄰點(diǎn)全和可區(qū)別全可染的.

崔福祥等［6］基于一些特殊圖類(lèi)上鄰點(diǎn)全和可區(qū)別全染色的研究， 給出如下猜想：

猜想1［6］" 設(shè)G是一個(gè)正常圖， 則ftndiΣ（G）≤Δ（G）+2.

崔福祥等［7］又研究了路與路、 路與圈、 圈與圈三類(lèi)聯(lián)圖的鄰點(diǎn)全和可區(qū)別全染色; 葉宏波等［8］給出了路與路、 路與圈的笛卡爾積圖的鄰點(diǎn)全和可區(qū)別全色數(shù).

通常將連通的無(wú)圈圖稱(chēng)為樹(shù)， 點(diǎn)數(shù)與邊數(shù)相同的連通圖稱(chēng)為單圈圖， 將具有ν≥3個(gè)頂點(diǎn)的單圈圖簡(jiǎn)記為U. 趙新梅等［9］

給出了單圈圖的鄰強(qiáng)邊染色; 賈秀卿等［10］研究了單圈圖的D（2）-點(diǎn)可區(qū)別邊染色， 并給出了其確切的D（2）-點(diǎn)可區(qū)別邊色數(shù); 譚鈞銘等［11］

用分析法與數(shù)學(xué)歸納法得到了單圈圖的鄰和可區(qū)別邊色數(shù). 基于上述研究結(jié)果， 本文用結(jié)構(gòu)分析法結(jié)合數(shù)學(xué)歸納法完全刻畫(huà)單圈圖的鄰點(diǎn)全和可區(qū)別全染色， 并得到如下結(jié)論：

定理1" 設(shè)U是ν≥3階的單圈圖，" 則ftndiΣ（U）=Δ（U）+2，UCn且n0（mod 3），Δ（U）+1，其他.

定理1進(jìn)一步說(shuō)明猜想1在任意的單圈圖上都成立.

2" 引理及主要結(jié)果的證明

由定義1知， 圖的鄰點(diǎn)全和可區(qū)別全染色首先是一個(gè)正常全染色， 因此如下引理成立.

引理1" 設(shè)G是一個(gè)正常圖， 則ftndiΣ（G）≥Δ（G）+1.

引理2［6］" 對(duì)圈Cn（n≥3）， 有

ftndiΣ（Cn）=4，n≥4且n≠0（mod 3）;3，其他.

由定義1可知， 懸掛點(diǎn)x的全和是其鄰點(diǎn)y的全和的一部分， 因此如下引理成立.

引理3" 對(duì)一個(gè)正常圖G， 若x是G的一個(gè)懸掛點(diǎn)， y是x的鄰點(diǎn)， 則（x）≠（y）.

n階圈圖Cn的每個(gè)點(diǎn)上都添加一個(gè)懸掛邊所得的圖稱(chēng)為太陽(yáng)圖， 記為Sν（ν≥3）.

引理4" 設(shè)Sν（ν≥6）是太陽(yáng)圖， 則ftndiΣ（Sν）=4.

證明： 設(shè)C=v1v2…vnv1（n≥3）為太陽(yáng)圖Sν上具有n個(gè)頂點(diǎn)的基本圈， 圈上每個(gè)點(diǎn)vi關(guān)聯(lián)的懸掛邊為vixi， 其中懸掛點(diǎn)為xi（

1≤i≤n）. 由引理1可知， ftndiΣ（Sν）≥4， 下證Sν有一個(gè)4-NFSDTC. 令f為V（Sν）∪E（Sν）→{1，2，3，4}的一個(gè)映射.

圖1" S6的4-NFSDTCFig.1" 4-NFSDTC of S6

當(dāng)n=3時(shí)， S6的4-NFSDTC如圖1所示. 當(dāng)n≥4時(shí)， 對(duì)于vk∈V（C）， vk

vk+1∈E（C）， 懸掛邊為vkxk， 下面分兩種情形分別給出Sν的一個(gè)4-鄰點(diǎn)全和可區(qū)別全染色.

情形1） 當(dāng)n≡0（mod 2）時(shí)， 染色方案如下： 若k≡1（mod 2）， 則令f（vk）=1， f（vkxk）=3， f（vkvk+1）=2;

若k≡0（mod 2）， 則令f（vk）=3， f（vkvk+1）=4， f（vkxk）=1; 對(duì)于懸掛點(diǎn)xi， 令f（xi）=f（vivi+1）， 其中1≤i，k≤n.

此時(shí)， （v1），…，（vn）為18，16的循環(huán)， 即圈上的點(diǎn)都鄰點(diǎn)全和可區(qū)別; 又由引理3可知， 懸掛點(diǎn)與其鄰點(diǎn)全和可區(qū)別. 因此， f是Sν的一個(gè)4-NFSDTC.

情形2） 當(dāng)n≡1（mod 2）時(shí)， 染色方案如下： 若k≡1（mod 2）， 則令f（vk）=1， f（vkxk）=3， f（vkvk+1）=2; 若k

≡0（mod 2）， 則令f（vk）=3， f（vkvk+1）=4， f（vkxk）=1; 其中1≤k≤n-2. f（vn-1）=3， f（vn-1vn）=1， f（vn-1xn-1）=4， f（vn

）=2， f（vnv1）=4， f（vnxn）=3， 對(duì)于懸掛點(diǎn)xi， 令f（xi）=f（vivi+1）， 其中1≤i≤n. 此時(shí)， （v2），…，（vn-2）為16，18的循環(huán)， （vn-1）=14，

（vn）=18， （v1）=17. 即圈上的點(diǎn)都鄰點(diǎn)全和可區(qū)別; 又由引理3可知， 懸掛點(diǎn)與其鄰點(diǎn)全和可區(qū)別. 因此， f是Sν的一個(gè)4-NFSDTC.

綜上所述， ftndiΣ（Sν）=4.

注1" 在引理4的證明中：

1） 刪去所有懸掛點(diǎn)后， 在染色f下， 當(dāng)n≡0（mod 2）時(shí)， 基本圈C上點(diǎn)v1，v2，…，vn的全和為13，11的循環(huán); 當(dāng)n≡

1（mod 2）時(shí)， 基本圈C上點(diǎn)v2，v3，…，vn-2的全和為1

1，13的循環(huán)， vn-1，vn，v1的全和為9，11，12， 此時(shí)圈上所有2度點(diǎn)之間是鄰點(diǎn)全和可區(qū)別全可染的;

2） 刪去任意一個(gè)懸掛點(diǎn)后， 在染色f下， 2度點(diǎn)的全和可能為9，11，12，13， 而3度點(diǎn)的全和為14，16，17，18. 故圈上所有2度點(diǎn)與3度點(diǎn)之間是鄰點(diǎn)全和可區(qū)別全可染的.

太陽(yáng)圖刪去一些懸掛點(diǎn)得到的圖稱(chēng)為破太陽(yáng)圖， 記為S′ν（ν≥3）. 顯然， 任意一個(gè)破太陽(yáng)圖S′ν都是某個(gè)太陽(yáng)圖Sω的子圖， 其中νlt;ω.

引理5" 設(shè)S′ν（ν≥3）是一個(gè)破太陽(yáng)圖， 則ftndiΣ（S′ν）=4.

證明： 設(shè)Sω是S′ν的2度點(diǎn)添加懸掛邊所得的太陽(yáng)圖. 顯然， S′ν是Sω的一個(gè)子圖. 由引理4可知， Sω有一

個(gè)4-NFSDTC f. 由注1可知， f′=fS′ν為S′ν的一個(gè)4-NFSDTC， 故結(jié)論成立.

引理6（組合零點(diǎn)定理）［12］" 設(shè)F為任一域， P=P（x1，x2，…，xn）為F［x1，x2，…，x

n］上的多項(xiàng)式. 設(shè)deg（P）=∑ni=1ki， 其中ki為非負(fù)整數(shù)， 并且P中xk11xk22…xknn的系數(shù)非零. 若

S1，S2，…，SnF且Sigt;ki（1≤i≤n）， 則存在s1∈S1， s2∈S2， …， sn∈Sn， 使得P（s1，s2，…，sn）≠0.

引理7" 設(shè)G是n≥3階的連通圖， v是G的一個(gè)懸掛點(diǎn)， v的鄰點(diǎn)為w且w僅有一個(gè)非懸掛鄰點(diǎn)， 記為u. 若G′=G-v且G′有一個(gè)（Δ（G′）+1）-NFSDTC

， 則G存在一個(gè)由f′所延拓的（Δ（G）+1）-正常全染色f; 進(jìn)一步， 若f滿(mǎn)足f（v）+f（wv）至少有兩個(gè)不同的取值， 則f為G的一個(gè)（Δ（G）+1）-NFSDTC.

證明： 由已知G′=G-v， 所以Δ（G′）≤Δ（G）. 又因?yàn)镚′有一個(gè)（Δ（G′）+1）-NFSDTC f′， 從而G′有一個(gè)（Δ（G）+1）-NFSDTC

， 不妨記為f. 由于v是G的一個(gè)懸掛點(diǎn)， 所以f也是G的一個(gè)由f′所延拓的（Δ（G）+1）-正常全染色.

在上述f下， 注意到G中屬于G′的任意兩個(gè)相鄰點(diǎn)都是鄰點(diǎn)全和可區(qū)別全可染的. 對(duì)于v和w， 由引理3知， G（v）≠G（w）. 若

將f擴(kuò)展為G的一個(gè)（Δ（G）+1）-NFSDTC， 只需證G（w）≠G（u）. 由G′和G的關(guān)系可知：

G（u）=G′（u），" G（w）=G′（w）+f（wv）+f（v）.

于是，

G（w）-G（u）=f（wv）+f（v）+（G′（w）-G′（u）），

其中G′（w）-G′（u）≠0. 因?yàn)镚′是（Δ（G）+1）-鄰點(diǎn)全和可區(qū)別全可染的， 其中Δ（G）≥3， 又因?yàn)閐G（w）≤Δ（G）， 所以f（wv）至少有

一種色可染， f（v）至少存在兩種色可染. 由于f為G的一個(gè)正常全染色， 因此f（v）≠f（wv）， 從而f（v）+f（wv）至少有兩個(gè)不同的取值. 進(jìn)一步， 根據(jù)引理6可知， G（w）≠G（u）， 從而G在f下是

（Δ（G）+1）-鄰點(diǎn)全和可區(qū)別全可染的. 因此， 由引理1可知， f為G的一個(gè)（Δ（G）+1）-NFSDTC. 證畢.

下面用符號(hào)［a，b］表示非負(fù)整數(shù)集{a，a+1，a+2，…，b}， 其中a和b都是整數(shù)且0≤alt;b. 令dG（v，H）=max{dG（v，x）v∈V（G

）＼V（H）， x∈V（H）}為點(diǎn)v到H的最大距離， 其中H是G的子圖." Cf′（u）表示在染色f′下u點(diǎn)所染的顏色與其關(guān)聯(lián)邊的顏色組成的集合.

下面證明定理1. 設(shè)U是ν≥3階的單圈圖， 若UCn， 則由引理2可知結(jié)論成立. 否則， 記C=v1v2…vnv1為單圈圖U上的基本圈， 下面根據(jù)U的最大度分兩種情形討論.

情形1） Δ（U）=3.

① 懸掛點(diǎn)的鄰點(diǎn)不在基本圈C上.

對(duì)U的階ν做歸納. 當(dāng)ν=5時(shí)的單圈圖及其染色如圖2所示， 可知結(jié)論成立.

假設(shè)對(duì)階數(shù)小于ν且Δ（U）=3的單圈圖結(jié)論成立， 下面考慮階數(shù)等于ν時(shí)結(jié)論成立.

設(shè)U與C上頂點(diǎn)距離最大的一個(gè)懸掛點(diǎn)為v， v的鄰點(diǎn)為w且w的非懸掛點(diǎn)的鄰點(diǎn)為u， 其中dU（w）≥2， dU（u）≥2. 令U′=U-v， 由歸納

假設(shè)， U′有一個(gè)4-NFSDTC f′. 顯然， f′是U′的一個(gè)正常全染色， 定義U的染色f： f（v）=f′（v）， v∈V（U′

）; f（e）=f′（e）， e∈E（U′）. 由引理7可知， 只需證明f（v）+f（wv）至少有兩個(gè)不同的取值時(shí)， 即可證明結(jié)論成立.

當(dāng)dU（w）=dU（u）=2時(shí)， dU′（w）=dU（w）-1=1， 令I(lǐng)=［1，4］＼Cf′（w）， 則I=2. 令f（wv）∈I， f（v）∈［1，4］＼{f（wv），

f（w）}. 由于f是U的一個(gè)正常全染色， f（v）≠f（wv）， f（v）≠f（w）， 所以f（v）有兩個(gè)不同的值可取， 故f（v）+f（wv）至少有兩個(gè)不同的取值. 當(dāng)dU（w）=2， d

U（u）=3時(shí)， 類(lèi)似可證.

當(dāng)dU（w）=dU（u）=3時(shí)， dU′（w）=dU（w）-1=2， 令I(lǐng)=［1，4］＼Cf′（w）， 則I=1. 令f（wv）∈I， f（v）∈［1，4］＼{f（wv），f

（w）}. 由于f是U的一個(gè)正常全染色， f（v）≠f（wv）， f（v）≠f（w）， 所以f（v）有兩個(gè)不同的值可取， 故f（v）+f（wv）至少有兩個(gè)不同的取值. 當(dāng)dU（w）=3， dU（u）=2時(shí)， 類(lèi)似可證.

② 懸掛點(diǎn)的鄰點(diǎn)在基本圈C上.

若C的每個(gè)點(diǎn)都有懸掛邊， 則U為太陽(yáng)圖. 由引理4知， U有一個(gè)4-NFSDTC f. 反之， 若C上至少有一個(gè)點(diǎn)沒(méi)有懸掛邊， 則U為破

太陽(yáng)圖. 由引理5知， U有一個(gè)4-NFSDTC f.

情形2） Δ（U）≥4.

① 懸掛點(diǎn)的鄰點(diǎn)不在基本圈C上.

對(duì)U的階ν使用數(shù)學(xué)歸納法. 當(dāng)ν=6時(shí)， U如圖3所示， 給出U的一個(gè)（Δ（U）+1）-NFSDTC.

圖2" ν=5且Δ=3時(shí)的單圈圖及其染色Fig.2" Unicyclic graph" with ν=5， Δ=3 and its coloring

圖3" ν=6且Δ=4時(shí)的單圈圖及其染色Fig.3" Unicyclic graph with ν=6， Δ=4 and its coloring

當(dāng)ν≥7時(shí)， 假設(shè)對(duì)滿(mǎn)足條件的（ν-1）階單圈圖， 有（Δ（U）+1）-NFSDTC. 下面考慮滿(mǎn)足條件的ν階單圈圖.

選取U與C上頂點(diǎn)距離最大的一個(gè)懸掛點(diǎn)v， 且v的鄰點(diǎn)w不在圈上， 而w僅有一個(gè)非懸掛鄰點(diǎn)u， 如圖4所示.

圖4" 懸掛點(diǎn)的鄰點(diǎn)不在基本圈上

Fig.4" Neighbors of pendant vertex out of basic cycle

令U′=U-v， 由歸納假設(shè)知， ftndiΣ（U′）=Δ（U′）+1. 令f′是U′的一個(gè)（Δ（U′）+1）-NFSDTC. 定義U 的染色f： f（v）=f′（v）， v∈V（U′）; f（e）=f′（e）， e∈

E（U′）. 由引理7可知， 只需證明f（v）+f（wv）至少有兩個(gè)不同的取值， 即可證明結(jié)論成立. 下面根據(jù)最大度頂點(diǎn)是否相鄰分兩種情形討論.

（i） U中不存在兩個(gè)相鄰的最大度點(diǎn).

當(dāng)dU′（u）≤dU′（w）時(shí)， 由于dU′（w）=dU（w）-1≤Δ（U）-1且U中不存在兩個(gè)相鄰的最大度點(diǎn)， 令I(lǐng)=［1，Δ（U）+1］＼

Cf′（w）， 則I≥1. 令f（wv）∈I， f（v）∈［1，Δ（U）+1］＼{f（wv），f（w）}. 由于f是U的一個(gè)正常全染色， f（v）≠f（wv）， f（v）≠

f（w）， 所以f（v）至少有兩個(gè)不同的值可取， 故f（v）+f（wv）至少有兩個(gè)不同取值.

當(dāng)dU′（u）= dU′（w）+1時(shí)， 由于U中不存在兩個(gè)相鄰的最大度點(diǎn)， 所以dU′（u）=dU（w）lt;Δ（U）， 即Δ（U′）=Δ（U），

故有dU′（w）=dU（w）-1lt;Δ（U）-1. 令I(lǐng)=［1，Δ（U）+1］＼Cf′（w）， 則I≥2. 令f（wv）∈I， f（v）∈［1，Δ（U）+1］＼

{f（wv），f（w）}. 由于f是U的一個(gè)正常全染色， f（v）≠f（wv）， f（v）≠f（w）， 所以f（v）至少有兩個(gè)不同的值可取， 故f（v）+f（wv）至少有兩個(gè)不同取值.

當(dāng)dU′（u）≥ dU′（w）+2時(shí)， dU′（w）≤dU′（u）-2≤Δ（U）-2. 令I(lǐng)=［1，Δ（U）+1］＼Cf′（w

）， 則I≥2. 令f（wv）∈I， f（v）∈［1，Δ（U）+1］＼{f（wv），f（w）}， 由于f是U的一個(gè)正常全染色， f（v）≠f（wv）， f（v）≠f（w）， 所以f（v）至

少有兩個(gè)不同的值可取， 故f（v）+f（wv）至少有兩個(gè)不同取值.

（ii） U中存在兩個(gè)相鄰的最大度頂點(diǎn).

當(dāng)dU′（u）≤dU′（w）時(shí)， 如情形（i）類(lèi)似可證. 當(dāng)dU′（u）= dU′（w）+1時(shí)， 由于U中存在兩個(gè)相鄰的最大度頂點(diǎn)， 所以dU（u）=dU（w）≤Δ（U）. 若

dU（u）=dU（w）=Δ（U）， dU′（w）=Δ（U）-1， 令I(lǐng)=［1，Δ（U）+1］＼Cf′（w）， 則I=1. 若dU（u）=dU（w）≤Δ（U）-1， dU′（w）=dU（w）-

1≤Δ（U）-1， 令I(lǐng)=［1，Δ（U）+1］＼Cf′（w）， 則I≥2.

令f（wv）∈I， f（v）∈［1，Δ（U）+1］＼{f（wv），f（w）}. 由于f是U 的一個(gè)正常全染色， f（v）≠f（wv）， f（v）≠f（w）， 所以f（v）至少有兩個(gè)不同的值可取， 故f（v）+f（wv）至少有兩個(gè)不同取值.

當(dāng)dU′（u）≥dU′（w）+2時(shí)， 如情形（i）類(lèi)似可證.

② 懸掛點(diǎn)的鄰點(diǎn)在基本圈C上.

對(duì)U的階ν使用數(shù)學(xué)歸納法. 當(dāng)ν=5時(shí)， U如圖5所示， 給出U的一個(gè)（Δ（U）+1）-NFSDTC.

當(dāng)ν≥6時(shí)， 假設(shè)對(duì)滿(mǎn)足條件的ν-1階單圈圖， 有（Δ（U）+1）-NFSDTC. 下面考慮滿(mǎn)足條件的ν階單圈圖.

令NU（w）={v1，v2，w1，w2…，wr1≤r≤Δ（U）-2}， 設(shè)dU（vj）≥2， 其中j=1，2; dU（wi）=1， 其中i=1，2，…，r. 如圖6所示.

圖5" ν=5且Δ=4時(shí)的單圈圖及其染色Fig.5" Unicyclic graph" with ν=5， Δ=4 and its coloring

圖6" 懸掛點(diǎn)的鄰點(diǎn)在基本圈上

Fig.6" Neighbors of pendant vertex on basic cycle

令U′=U-wr， 由歸納假設(shè)知， ftndiΣ（U′）=Δ（U′）+1， Δ（U′）≤Δ（U）. 設(shè)f′是U′的一個(gè)（Δ（U′）+1）-NFSDTC.

若將f′拓展為U的一個(gè)（Δ（U）+1）-NFSDTC f， 基于f′， 為保證f是正常的， 則需給邊wwr和點(diǎn)wr正常著色. 由于f（wwr）≠f′

（w）， f（wwr）≠f′（v1w）， f（wwr）≠f′（v2w）， f（wwr）≠f′（wwi）（1≤i≤r-1， r≤Δ-2）， 邊w

wr至多有Δ（U）種禁用色. 下面考慮點(diǎn)w的非懸掛鄰點(diǎn)v1和v2的全和是否相等， 分兩種情形討論.

（i） f（v1）=f（v2）.

由于邊wwr至多有Δ（U）種禁用色， 所以f（wwr）至少存在一種可用色， 而f（wr）可用［1，Δ（U）+1］＼{f（wwr），f（w）}種色去染， 又因f是

U的一個(gè)正常全染色， f（wr）≠f（wwr）， f（wr）≠f（w）， 所以f（wr）至少有兩個(gè)不同的值可取， 故f（wwr）+f（wr）至少有兩個(gè)不同的值可取. 由引理7可知結(jié)論成立.

（ii） f（v1）≠f（v2）.

由引理6和引理7可知， 要使（w）≠（v1）且（w）≠（v2）， 則f（wwr）+f（wr）至少有3個(gè)不同的值可取. 對(duì)邊wwr和點(diǎn)

wr正常染色， f（wwr）至少存在一種可用色， 而f（wr）可用［1，Δ（U）+1］＼{f（wwr），f（w）}種色去染， 由于Δ（U）≥4且f是U的一個(gè)

正常全染色， f（wr）≠f（wwr）， f（wr）≠f（w）， 所以f（wr）至少有3個(gè)不同的值可取， 從而f（wwr）+f（wr）至少有3個(gè)不同的值可取. 即

點(diǎn)w與其鄰點(diǎn)在f下是鄰點(diǎn)全和可區(qū)別全可染的. 定理1證畢.

參考文獻(xiàn)

［1］" KARON＇SKI M， UCZAK T， THOMASON A. Edge Weights an

d Vertex Colours ［J］. Journal of Combinatorial Theory： Series B， 2004， 91（1）： 151-157.

［2］" 張忠輔， 程輝， 姚兵， 等. 圖的鄰點(diǎn)強(qiáng)可區(qū)別的全染色 ［J］. 中國(guó)科學(xué)A輯： 數(shù)

學(xué)， 2007， 37（9）： 1073-1082. （ZHANG Z F， CHENG H， YAO B， et al. Adjacent Vertex Strongly Distinguishing Total Coloring of Graphs ［J］. Scientia Sinica （A： Mathematica），

2007， 37（9）： 1073-1082.）

［3］" PRZYBYLO J， WOZ＇NIAK M. On a 1，2 Conjecture

［J］. Discrete Mathematics and Theoreyical Computer Science， 2010， 12（1）： 101-108.

［4］" PILS＇NIAK M， WOZ＇NIAK

M. On the Total-Neighbor-Distinguishing Index by Sums ［J］. Graphs and Combinatorics， 2015， 31（3）： 771-782.

［5］" FLANDRIN E， LI H， MARCZYK A， et al. A Note on Neighb

or Expanded Sum Distinguishing Index ［J］. Discussiones Mathematicae Graph Theory， 2017， 37（1）： 29-37.

［6］" 崔福祥， 楊超， 葉宏波， 等. 圖的鄰點(diǎn)全和可區(qū)別全染色 ［J］. 運(yùn)籌學(xué)學(xué)報(bào)， 2023， 27（1）： 149-158. （CUI F X， YANG C， YE H B， et

al. Neighbor Full Sum Distinguishing Total Coloring of Graphs ［J］. Operations Research Transactions， 2023， 27（1）： 149-158.）

［7］" 崔福祥， 楊超， 葉宏波， 等. 聯(lián)圖的鄰點(diǎn)全和可區(qū)別全染色 ［J］. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2022， 60（1）： 44-52. （CUI F X， YANG C， YE H

B， et al. Neighbor Full Sum Distinguishing Total Coloring of Join Graphs ［J］. Journal of Jilin University （Science Edition）， 2022， 60（1）： 44-52.）

［8］" 葉宏波， 楊超， 殷志祥， 等. 兩類(lèi)笛卡爾乘積圖的鄰點(diǎn)全和可區(qū)別全染色 ［J］. 上海工程技術(shù)大學(xué)學(xué)報(bào)， 2022， 36（1）： 91-97. （YE H B， YANG C，

YIN Z X， et al. Neighbor Full Sum Distinguishing Total Coloring of Two Types of Cartesian

Product Graphs ［J］. Journal of Shanghai University of Engineering Science， 2022， 36（1）： 91-97.）

［9］" 趙新梅， 陳祥恩. 單圈圖的鄰強(qiáng)邊染色 ［J］. 蘭州交通大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2005， 24（6）： 138-140. （ZHAO X M， CHEN X E. On the Adjacent

Strong Edge Coloring of Monocycle Graph ［J］. Journal of Lanzhou Jiaotong University （Natural Sciences）， 2005， 24（6）： 138-140.）

［10］" 賈秀卿， 李沐春. 單圈圖的D（2）-點(diǎn)可區(qū)別邊染色 ［J］. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2021， 59（4）： 807-815. （JIA X Q， LI M C. D（2）-Ve

rtex-Distinguishing Edge Coloring of Unicyclic Graphs ［J］. Journal of Jilin University （Science Edition）， 2021， 59（4）： 807-815.）

［11］" 譚鈞銘， 強(qiáng)會(huì)英， 王洪申. 單圈圖的鄰和可區(qū)別邊染色 ［J］. 山東大學(xué)學(xué)報(bào)（理學(xué)版）， 2022， 57（2）： 78-83. （TAN J M， QIANG H Y， W

ANG H S. Neighbor Sum Distinguishing Edge Coloring of Unicyclic Graphs ［J］. Journal of Shandong University （Natural Science）， 2022， 57（2）： 78-83.）

［12］" ALON N. Combinatorial Nullstellensatz ［J］. Combinatorics， Probability and Computing， 1999， 8（1/2）： 7-29.

（責(zé)任編輯： 趙立芹）