三正則構(gòu)造圖的鄰點全和可區(qū)別全染色

摘要： 首先， 根據(jù)Snark圖的結(jié)構(gòu)特點， 構(gòu)造基于雙星和十字交叉形的兩類三正則圖; 其次， 利用窮染法和組合分析法研究四類三正則構(gòu)造圖的鄰點全和可區(qū)別全染色問題， 得到了它們的鄰點全和可區(qū)別全色數(shù)均為2.

關(guān)鍵詞： 非正常全染色; 鄰點全和可區(qū)別全染色; 鄰點全和可區(qū)別全色數(shù); 三正則圖

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

Neighbor Full Sum Distinguishing Total Coloring of3-Regular Construction Graphs

YANG Chao1， CHENG Yinwan1， YAO Bing2

（1. School of Mathematics， Physics and Statistics， Center of Intelligent Computing and Applied Statistics，Shanghai University of Engineering Science， Shanghai 201620， China;

2. College of Mathematics and Statistics， Northwest Normal University， Lanzhou 730070， China）

Abstract： Firstly， "according to the structural characteristics of Snark graphs， we constructed two classes of 3-regular graphs based on Double Star and Cross.

Secondly， we studied the "problem of neighbor full sum distinguishing total coloring of four classes of 3-regular graphs by exhaustive coloring method and combinatorial analysis，

and obtained that the neighbor full sum distinguishing total chromatic numbers for these graphs are all 2.

Keywords： non-proper total coloring; neighbor full sum distinguishing total coloring; neighbor full sum distinguishing total chromatic number; 3-regular graph

圖的可區(qū)別染色問題在交通、 排序、 無線電頻率分配等領(lǐng)域應(yīng)用廣泛， 目前已取得了許多研究成果. Karoński等^［1］首次介紹并研究了圖的鄰和可區(qū)別邊染色， 并提出了1-2-3猜想. Kalkowski等^［2］證明了： 若G是k-可著色的且k為奇數(shù)， 則G中存在一個鄰和可區(qū)別k-邊染色. 因此， 對于一類3-可著色圖， 包括二部圖， 1-2-3猜想均成立. Addario-Berry等^［3］給出： 當(dāng)k=30時， 每個無孤立邊的圖都有一個鄰和可區(qū)別30-邊染色. 文獻(xiàn)［4-5］將k值進(jìn)一步改進(jìn)為k=15， k=13. 對于每個無孤立邊的圖， Kalkowski等^［2］還證明了它們都是鄰和可區(qū)別5-邊染色的. Przybylo^［6］證明了： 每個d-正則圖（d≥2）都是鄰和可區(qū)別4-邊染色的， 且當(dāng)d≥108時， 每個d-正則圖是鄰和可區(qū)別3-邊染色的.

Przybylo等^［7］在鄰和可區(qū)別邊染色的基礎(chǔ)上考慮加入點自身的顏色， 定義了圖的鄰和可區(qū)別全染色， 同時給出了關(guān)于鄰和可區(qū)別全染色的1-2猜想. 當(dāng)圖G是一個3-可著色圖、 完全圖或者4-正則圖時， 1-2猜想均成立. 文獻(xiàn)［8］研究表明： 任意圖G 的鄰和可區(qū)別全色數(shù)小于等于3.

Flandrin等^［9］在鄰和可區(qū)別全染色的基礎(chǔ)上， 將每個點的鄰點顏色數(shù)加入其權(quán)重和中， 定義了圖的鄰點全和可區(qū)別全染色. Baudon等^［10］進(jìn)一步給出了關(guān)于鄰點全和可區(qū)別全染色的一個猜想： 任意圖的鄰點全和可區(qū)別全色數(shù)不超過3. "研究表明， 該猜想對哈林圖^［11］、 若干平方圖^［12］、 廣義Petersen圖和循環(huán)圖^［13］以及若干倍圖^［14］均成立. 基于圖的鄰點全和可區(qū)別全染色猜想， 本文研究四類三正則構(gòu)造圖的鄰點全和可區(qū)別全色數(shù)問題.

1"預(yù)備知識

本文所討論的圖G均為無向簡單連通圖， 用V（G）和E（G）分別表示G的頂點集和邊集. 本文未定義的術(shù)語和符號均見文獻(xiàn)［15］.

定義1^［9］"設(shè)f： V（G）∪E（G）→［1，k］是圖G的一個非正常k-全染色. 令?（x）=f（x）+∑x∈ef（e）+∑y∈N（x）f（y）， 其中N（x）={y∈V（G）xy∈E（G）}. 對任意的邊uv∈E（G）， 如果有?（u）≠?（v）成立， 則稱f是圖G的一個鄰點全和可區(qū)別k-全染色. 圖G的鄰點全和可區(qū)別全染色中最小的k值稱為G的鄰點全和可區(qū)別全色數(shù)， 記為fgndi∑（G）.

Snark圖是源自3-邊著色猜想而構(gòu)造的圖， 若圖G是2-邊連通的三正則圖且不可3-邊著色， 且圍長至少為5， 也無3-邊割集， 則圖G稱為Snark圖. Petersen圖是最小的Snark圖. 本文研究的四類三正則圖定義如下.

定義2^［16］"設(shè)Gn是一個三正則圖， 其頂點集為V（Gn）={ai，bi，ci，di; 0≤i≤n-1}， 邊集為E（Gn）={aiai+1，bibi+1，cici+1，diai，dibi，dici; 0≤i≤n-1}， 點的標(biāo)號下標(biāo)對n取模， 則把Gn通過用邊bn-1a0，an-1b0替換bn-1b0，an-1a0得到的圖定義為Hn. 如果n為奇數(shù)且n≥5， 則Hn稱為Flower Snark圖， 其他的圖稱為Flower Snark圖的相關(guān)圖.

把Flower Snark圖及其相關(guān)圖統(tǒng)一用Fn表示， F5如圖1所示.

定義3^［17］"設(shè)圖Bk（k≥3）的頂點集為V（Bk）={vtj0≤t≤k-1， 1≤j≤8}， 邊集為E（Bk）={vt1vt2，vt3vt4，vt5vt6，vt6vt7，vt6vt8，vt1vt7，vt4vt7，vt2vt8，vt3vt80≤t≤k-1}∪{vt2v^t+11，vt4v^t+13，

vt5v^t+150≤t≤k-1}， 這里加法取模k. 當(dāng)k為奇數(shù)時， Bk稱為Goldberg Snark圖.

Goldberg Snark圖B3如圖2所示.

類似于Flower Snark圖和Goldberg Snark圖的構(gòu)造方法， 本文分別構(gòu)造了基于雙星和十字交叉形的兩類三正則圖Dn和Ln. 三正則圖Dn和Ln分別構(gòu)造如下.

定義4"設(shè)Dn（n≥3）為三正則圖， 其頂點集為V（Dn）={vij0≤i≤n-1， 1≤j≤10}， 邊集為E（Dn）={vi1vi3，vi3vi4，vi2vi4，vi3vi5，vi4vi6，vi2vi8，vi6vi10，vi1vi7，vi5vi9，vi7vi

8，vi9vi100≤i≤n-1}∪{vi8vⁱ⁺¹7，vi6vⁱ⁺¹5，vi2vⁱ⁺¹1，vi10vⁱ⁺¹9，v05v^n-16，v07v^n-18，v01v^n-12，v09v^n-1100≤i≤n-1}.

三正則圖D4如圖3所示.

定義5"設(shè)Ln（n≥3）為三正則圖， 其頂點集為V（Ln）={vij0≤i≤n-1， 1≤j≤8}， 邊集為E（Ln）={vi1vi4，vi2vi

3，vi1vi5，vi2vi6，vi3vi7，vi4vi8，vi5vi6，vi7vi80≤i≤n-1}∪{vi2vⁱ⁺¹

1，vi6vⁱ⁺¹5，vi8vⁱ⁺¹7，vi4vⁱ⁺¹3，v03v^n-14，v01v^n-12，v05v^n-16，v07v^n-180≤i≤n-1}.

三正則圖L4如圖4所示.

2"主要結(jié)果

引理1"設(shè)G是一個k-正則圖， 則fgndi∑（G）≥2.

證明： 反證法. 假設(shè)k-正則圖G的點和邊均染顏色1， 則G中每個點的權(quán)重值都為2k+1， 與定義1矛盾， 故fgndi∑（G）≥2. 證畢.

當(dāng)k=3時， 引理1給出了三正則圖G滿足fgndi∑（G）≥2， 即確定了三正則圖的鄰點全和可區(qū)別全色數(shù)的一個下界. 下面先構(gòu)造基于定義2～定義5中四類

三正則圖的2-全染色函數(shù)， 再驗證它們是鄰點全和可區(qū)別2-全染色的， 即fgndi∑（G）≤2.

定理1"fgndi∑（Fn）=2.

證明： 由定義2知， 圖Fn是一個三正則圖. 由引理1知， 至少用2 種顏色才能完成Fn的一個鄰點全和可區(qū)別全染色. 下面分4種情形對Fn進(jìn)行染色.

情形1） n≡1（mod 4）且n≥5.

定義Fn的一個全染色f1： V（Fn）∪E（Fn）→［1，2］如下：

f1（v）=1， v∈V（Fn）;

f1（e）=2， 其中e∈{a0d0，a0bn-1，b0d0，bn-1dn-1，c0cn-1}∪{cidii≡0（mod 2）}∪{cici+1i≡1（mod 2）}

∪{aiai+1i≡1，2（mod 4）}∪{bibi+1i≡0，3（mod 4）};

f1（e0）=1， e0∈E（Fn）＼{e}.

由染色f1可得：

?（ai）=7，i≡0（mod 4）， i≠0，8，i≡1（mod 2），9，i≡2（mod 4）， i=0;

?（bi）=7，i≡2（mod 4），8，i≡1（mod 2），9，i≡0（mod 4）， i≠n-1，10，i=n-1;

?（ci）=8，i≡1（mod 2），9，i≡0（mod 2）， i≠n-1，10，i=n-1;

?（di）=7，i≡1（mod 2），8，i≡0（mod 2）， i≠0，n-1，9，i=n-1，

10，i=0.

因為各相鄰點權(quán)重不同， 所以f1為Fn的一個鄰點全和可區(qū)別2-全染色.

情形2） n≡3（mod 4）且n≥7.

定義Fn的一個全染色f2： V（Fn）∪E（Fn）→［1，2］如下：

f2（v）=1， v∈V（Fn）;

f2（e）=2， 其中e∈{an-1b0，bn-3dn-3，an-1dn-1，cn-3cn-2，c0cn-1，bn-2bn-1}∪{cidii≡0（mod 2）

}∪{cici+1i≡1（mod 2）}∪{aiai+1i≡1，2（mod 4）}∪{bibi+1i≡0，3（mod 4）};

f2（e0）=1， e0∈E（Fn）＼{e}.

由染色f2可得：

?（ai）=7，i≡0（mod 4），8，i≡1（mod 2），9，i≡2（mod 4）， i≠n-1，10，i=n-1;

?（bi）=7，i≡2（mod 4）， i≠n-1，8，i≡1（mod 2）， i=n-1，9，i≡0（mod 4）， i=n-2，10，i=n-3;

?（ci）=8，i≡1（mod 2）， i≠n-2，9，i≡0（mod 2）， i=n-2， i≠n-1，n-3，10，i=n-1，n-3；

?（di）=7，i≡1（mod 2），8，i≡0（mod 2）， i≠n-3，n-1，9，i=n-1，n-3.

因為各相鄰點權(quán)重不同， 所以f2為Fn的一個鄰點全和可區(qū)別2-全染色.

情形3） n≡0（mod 4）且n≥4.

定義Fn的一個染色f3： V（Fn）∪E（Fn）→［1，2］如下：

f3（v）=1， v∈V（Fn）;

f3（e）=2， 其中e∈{cici+1i≡0（mod 2）}∪{cidii≡1（mod 2）}∪{aiai+1i≡2，3（mod 4）}

∪{bibi+1i≡2，3（mod 4）}∪{an-1b0，bn-1a0};

f3（e0）=1， e0∈E（Fn）＼{e}.

由染色f3可得：

?（ai）=7，i≡1（mod 4），8，i≡0（mod 2），9，i≡3（mod 4）;

?（bi）=7，i≡1（mod 4），8，i≡0（mod 2），9， i≡3（mod 4）;

?（ci）=8，i≡0（mod 2），9，i≡1（mod 2）;

?（di）=7，i≡0（mod 2），8，i≡1（mod 2）.

因為各相鄰點權(quán)重不同， 所以f3為Fn的一個鄰點全和可區(qū)別2-全染色.

情形4） n≡2（mod 4）且n≥4.

定義Fn的一個染色f4： V（Fn）∪E（Fn）→［1，2］如下：

f4（v）=1， v∈V（Fn）;

f4（e）=2， 其中e∈{cici+1i≡0（mod 2）}∪{cidi i≡1（mod 2）}∪{aiai+1i≡0，3（mod 4）}

∪{bibi+1i≡1，2（mod 4）}∪{aidi，bidi0≤i≤n-1}∪{bn-1a0};

f4（e0）=1， e0∈E（Fn）＼{e}.

由染色f4可得：

?（ai）=8，i≡2（mod 4），9，i≡1（mod 2），10，i≡0（mod 4）;

?（bi）=8，i≡0（mod 4），9，i≡1（mod 2），10，i≡2（mod 4）;

?（ci）=8，i≡0（mod 2），9，i≡1（mod 2）;

?（di）=9，i≡0（mod 2），10，i≡1（mod 2）.

因為各相鄰點權(quán)重不同， 所以f4為Fn的一個鄰點全和可區(qū)別2-全染色.

定理2"fgndi∑（Bk）=2.

證明： 由定義3知， 圖Bk是一個三正則圖. 由引理1知， 至少用2 種顏色才能完成Bk的一個鄰點全和可區(qū)別全染色. 對Bk給出染色方案f5： V（Bk）∪E（Bk）→［1，2］如下：

f5（v）=1， v∈V（Bk）;

f5（e）=2， 其中e∈{vi6vi7，vi6vi8，vi2vi80≤i≤n-1}∪{vi5vi6i≡1（mod 2）}∪{vi5vⁱ⁺¹5i≡1（mod 2）}

∪{vi3vi8i≡0（mod 2）}∪{vi4vi7i≡1（mod 2）}∪{vi3vi4i≡1（mod 2）}∪{vi4vⁱ⁺¹3i≡1（mod 2）};

f5（e0）=1， e0∈E（Bk）＼{e}.

由染色f5可得：

?（vi1）=7;""?（vi2）=8;

?（vi3）=8，i≡1（mod 2）， i=0，9，i≡0（mod 2）， i≠0;

?（vi4）=7，i≡0（mod 2），10，i≡1（mod 2）;

?（vi5）=7，i=0，8，i≡0（mod 2）， i≠0，9，i≡1（mod 2）;

?（vi6）=9，i≡0（mod 2），10，i≡1（mod 2）;

?（vi7）=8，i≡0（mod 2），9，i≡1（mod 2）;

?（vi8）=9，i≡1（mod 2），10，i≡0（mod 2）.

因為各相鄰點權(quán)重不同， 所以f5為Bk的一個鄰點全和可區(qū)別2-全染色.

定理3"fgndi∑（Dn）=2.

證明： 由定義4知， 圖Dn是一個三正則圖. 由引理1知， 至少用2種顏色才能完成Dn的一個鄰點全和可區(qū)別全染色.

情形1） n≡0（mod 2）且n≥4.

染色方案f6： V（Dn）∪E（Dn）→［1，2］如下：

f6（v）=1， v∈V（Dn）;

f6（e）=2， 其中e∈{v05v09，v^n-16v05，v^n-12v01，v^n-18v07 }∪{vi1vi3}∪{vi6vi10i≠n-1}

∪{vi10vⁱ⁺¹9i≠n-1}∪{vi1vi7i≠0}∪{vi2vi8i≠n-1}

∪{vi8vⁱ⁺¹7i≡0（mod 2）}∪{vi7vi8i≡1（mod 2）};

f6（e0）=1， e0∈E（Dn）＼{e}.

由染色f6可得：

?（vi1）=9;"?（vi2）=8;"?（vi3）=8;"?（vi4）=7;"?（vi6）=8;"?（vi8）=9;"?（vi9）=8;

?（vi5）=7，1≤i≤n-1，9，i=0;

?（vi7）=8，i≡0（mod 2），10，i≡1（mod 2）;

?（vi10）=7，i=n-1，9，0≤i≤n-2.

因為各相鄰點權(quán)重不同， 所以f6為Dn的一個鄰點全和可區(qū)別2-全染色.

情形2） n≡1（mod 2）且n≥3.

染色方案f7： V（Dn）∪E（Dn）→［1，2］如下：

f7（v）=1， v∈V（Dn）;

f7（e）=2， 其中e∈{v05v09，v^n-16v05，v^n-12v01 }∪{vi1vi3}∪{vi6vi10i≠n-1}∪{vi10vⁱ⁺¹9i≠n-1}

∪{vi1vi7}∪{vi2vi8i≠n-1}∪{vi8vⁱ⁺¹7i≡0（mod 2）}∪{vi7vi8i≡1（mod 2）};

f7（e0）=1， e0∈E（Dn）＼{e}.

由染色f7可得：

?（vi2）=8;"?（vi3）=8;"?（vi4）=7;nbsp;?（vi6）=8;"?（vi8）=9;"?（vi9）=8;

?（vi1）=9，1≤i≤n-1，10， i=0;

?（vi5）=7，1≤i≤n-1，9，i=0;

?（vi7）=8，i≡0（mod 2），10，i≡1（mod 2）;

?（vi10）=7，i=n-1，9，0≤i≤n-2.

因為各相鄰點權(quán)重不同， 所以f7為Dn的一個鄰點全和可區(qū)別2-全染色.

定理4"fgndi∑（Ln）=2.

證明： 由定義5知， 圖Ln是一個三正則圖. 由引理1知， 至少用2 種顏色才能完成Ln的一個鄰點全和可區(qū)別全染色. 下面定義Ln的一個2-全染色f8： f8（v）=1， v∈V（Ln）;

f8（e）=2， e∈{vi1vi5，vi1vi4，vi2vi3，vi3vi7}; f8（e0）=1， e0∈E（Ln）＼{e}. 則

?（vi1）=9;"?（vi2）=8;"?（vi3）=9;"?（vi4）=8;"?（vi5）=8;"?（vi6）=7;"?（vi7）=8;"?（vi8）=7.

故f8為Ln的一個鄰點全和可區(qū)別2-全染色.

參考文獻(xiàn)

［1］"KARON＇SKI M， LUCZAK T， THOMASON A. Edge

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

［2］"KALKOWSKI M， KARON＇SKI M， PFENDER F.

Vertex-Coloring Edge-Weightings： Towards the 1-2-3-Conjecture ［J］. Journal of Combinatorial Theory （Series B）， 2010， 100（3）： 347-349.

［3］"ADDARIO-BERRY L， DALAL K， MCDIARMID C， et al. Vertex-Colouring Edge-Weightings ［J］. Combinatorica， 2007， 27（1）： 1-12.

［4］"ADDARIO-BERRY L， DALAL K， REED B A， et al. Degree

Constrained Subgraphs ［J］. Discrete Applied Mathematics， 2008， 156（7）： 1168-1174.

［5］"WANG T， YU Q L. On Vertex-Coloring 13-Edge-Weighting ［J］. Frontiers of Mathematics in China， 2008， 3（4）： 581-587.

［6］"PRZYBYLO J. The 1-2-3 Conjecture Almost Holds for Regular Graphs ［J］. Journal of Combinatorial Theory （Series B）， 2021， 147： 183-200.

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

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

［8］"KALKOWSKI M. A Note on the 1，2-Conjecture ［D］. Poznan： Adam Mickiewicz University， 2010.

［9］"FLANDRIN E， LI H， MARCZYK A， et al. A Note on Neighbor Expanded Sum Distinguishing Index ［J］. Discussiones Mathematicae Graph Theory， 2017， 37（1）： 29-37.

［10］"BAUDON O， HOCQUARD H， MARCZYK A， et al. On a Total Version of 1，2，3 Conjecture ［J］.

Discussiones Mathematicae Graph Theory， 2020， 40（4）： 1175-1186.

［11］"程銀萬， 楊超， 姚兵. 關(guān)于哈林圖的鄰和可區(qū)別染色的注記 ［J］. 吉林大學(xué)學(xué)報（理學(xué)版）， 2022， 60（4）： 833-837.

（CHENG Y W， YANG C， YAO B. Notes on Neighbor Sum Distinguishing Coloring of Halin Graphs ［J］. Journal of Jilin University （Science Edition）， 2022， 60（4）： 833-837.）

［12］"王芹， 楊超， 常景智， 等. 平方圖的鄰點全和可區(qū)別全染色 ［J］. 華南師范大學(xué)學(xué)報（自然科學(xué)版）， 2022， 54（1）： 107-112.

（WANG Q， YANG C， CHANG J Z， et al. Neighbor Full Sum Distinguishing Total Colori

ng of Square Graphs ［J］. Journal of South China Normal University （Natural Science Edition）， 2022， 54（1）： 107-112.）

［13］"常景智， 楊超， 程銀萬， 等. 兩類正則圖的鄰點全和可區(qū)別全染色 ［J］. 西南大學(xué)學(xué)報（自然科學(xué)版）， 2022， 44（4）： 117-121.

（CHANG J Z， YANG C， CHENG Y W， et al. Neighbor Full Sum Distinguishing Total Coloring of Two Types of Regular Graphs ［J］. Journal of Southwest University （Natural Science Edition）， 2022， 44（4）： 117-121.）

［14］"程銀萬， 楊超， 姚兵. 若干倍圖的鄰點全和可區(qū)別全染色 ［J］. 華中師范大學(xué)學(xué)報（自然科學(xué)版）， 2023， 57（5）： 682-687.

（CHENG Y W， YANG C， YAO B. Neighbor Full Sum Distinguishing Total Coloring of So

me Double Graphs ［J］. Journal of Central China Normal University （Natural Sciences）， 2023， 57（5）： 682-687.）

［15］"BONDY J A， MURTY U S R. Graph Theory with Applications ［M］. London： The MaCmillan Press Ltd， 1976： 1-170.

［16］"董曉媛. Flower Snark圖的強(qiáng)邊染色 ［J］. 長春師范大學(xué)學(xué)報， 2019， 38（2）： 4-8.

（DONG X Y. Strong Edge Coloring of Flower Snark ［J］. Journal of Changchun Normal University， 2019， 38（2）： 4-8.）

［17］"董曉媛， 馬登舉. Goldberg Snark圖的強(qiáng)邊染色 ［J］. 東北師大學(xué)報（自然科學(xué)版）， 2018， 50（4）： 16-19.

（DONG X Y， MA D J. Strong Edge Coloring of Goldberg Snark ［J］. Journal of Northeast Normal University （Natural Science Edition）， 2018， 50（4）： 16-19.）

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