三正則構造圖的鄰點全和可區別全染色
2024-01-01 00:00:00楊超程銀萬姚兵
吉林大學學報(理學版) 2024年6期
摘要： 首先， 根據Snark圖的結構特點， 構造基于雙星和十字交叉形的兩類三正則圖; 其次， 利用窮染法和組合分析法研究四類三正則構造圖的鄰點全和可區別全染色問題， 得到了它們的鄰點全和可區別全色數均為2.
關鍵詞： 非正常全染色; 鄰點全和可區別全染色; 鄰點全和可區別全色數; 三正則圖
中圖分類號： O157.5""文獻標志碼： 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
圖的可區別染色問題在交通、 排序、 無線電頻率分配等領域應用廣泛， 目前已取得了許多研究成果. Karoński等［1］首次介紹并研究了圖的鄰和可區別邊染色， 并提出了1-2-3猜想. Kalkowski等［2］證明了： 若G是k-可著色的且k為奇數， 則G中存在一個鄰和可區別k-邊染色. 因此， 對于一類3-可著色圖， 包括二部圖， 1-2-3猜想均成立. Addario-Berry等［3］給出： 當k=30時， 每個無孤立邊的圖都有一個鄰和可區別30-邊染色. 文獻［4-5］將k值進一步改進為k=15， k=13. 對于每個無孤立邊的圖， Kalkowski等［2］還證明了它們都是鄰和可區別5-邊染色的. Przybylo［6］證明了： 每個d-正則圖（d≥2）都是鄰和可區別4-邊染色的， 且當d≥108時， 每個d-正則圖是鄰和可區別3-邊染色的.
Przybylo等［7］在鄰和可區別邊染色的基礎上考慮加入點自身的顏色， 定義了圖的鄰和可區別全染色， 同時給出了關于鄰和可區別全染色的1-2猜想. 當圖G是一個3-可著色圖、 完全圖或者4-正則圖時， 1-2猜想均成立. 文獻［8］研究表明： 任意圖G 的鄰和可區別全色數小于等于3.
Flandrin等［9］在鄰和可區別全染色的基礎上， 將每個點的鄰點顏色數加入其權重和中， 定義了圖的鄰點全和可區別全染色. Baudon等［10］進一步給出了關于鄰點全和可區別全染色的一個猜想： 任意圖的鄰點全和可區別全色數不超過3. "研究表明， 該猜想對哈林圖［11］、 若干平方圖［12］、 廣義Petersen圖和循環圖［13］以及若干倍圖［14］均成立. 基于圖的鄰點全和可區別全染色猜想， 本文研究四類三正則構造圖的鄰點全和可區別全色數問題.
1"預備知識
本文所討論的圖G均為無向簡單連通圖， 用V（G）和E（G）分別表示G的頂點集和邊集. 本文未定義的術語和符號均見文獻［15］.
定義1［9］"設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的一個鄰點全和可區別k-全染色. 圖G的鄰點全和可區別全染色中最小的k值稱為G的鄰點全和可區別全色數， 記為fgndi∑（G）.
Snark圖是源自3-邊著色猜想而構造的圖， 若圖G是2-邊連通的三正則圖且不可3-邊著色， 且圍長至少為5， 也無3-邊割集， 則圖G稱為Snark圖. Petersen圖是最小的Snark圖. 本文研究的四類三正則圖定義如下.
定義2［16］"設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}， 點的標號下標對n取模， 則把Gn通過用邊bn-1a0，an-1b0替換bn-1b0，an-1a0得到的圖定義為Hn. 如果n為奇數且n≥5， 則Hn稱為Flower Snark圖， 其他的圖稱為Flower Snark圖的相關圖.
把Flower Snark圖及其相關圖統一用Fn表示， F5如圖1所示.
定義3［17］"設圖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}∪{vt2vt+11，vt4vt+13，
vt5vt+150≤t≤k-1}， 這里加法取模k. 當k為奇數時， Bk稱為Goldberg Snark圖.
Goldberg Snark圖B3如圖2所示.
類似于Flower Snark圖和Goldberg Snark圖的構造方法， 本文分別構造了基于雙星和十字交叉形的兩類三正則圖Dn和Ln. 三正則圖Dn和Ln分別構造如下.
定義4"設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}∪{vi8vi+17，vi6vi+15，vi2vi+11，vi10vi+19，v05vn-16，v07vn-18，v01vn-12，v09vn-1100≤i≤n-1}.
三正則圖D4如圖3所示.
定義5"設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}∪{vi2vi+1
1，vi6vi+15，vi8vi+17，vi4vi+13，v03vn-14，v01vn-12，v05vn-16，v07vn-180≤i≤n-1}.
三正則圖L4如圖4所示.
2"主要結果
引理1"設G是一個k-正則圖， 則fgndi∑（G）≥2.
證明： 反證法. 假設k-正則圖G的點和邊均染顏色1， 則G中每個點的權重值都為2k+1， 與定義1矛盾， 故fgndi∑（G）≥2. 證畢.
當k=3時， 引理1給出了三正則圖G滿足fgndi∑（G）≥2， 即確定了三正則圖的鄰點全和可區別全色數的一個下界. 下面先構造基于定義2～定義5中四類
三正則圖的2-全染色函數， 再驗證它們是鄰點全和可區別2-全染色的， 即fgndi∑（G）≤2.
定理1"fgndi∑（Fn）=2.
證明： 由定義2知， 圖Fn是一個三正則圖. 由引理1知， 至少用2 種顏色才能完成Fn的一個鄰點全和可區別全染色. 下面分4種情形對Fn進行染色.
情形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.
因為各相鄰點權重不同， 所以f1為Fn的一個鄰點全和可區別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.
因為各相鄰點權重不同， 所以f2為Fn的一個鄰點全和可區別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）.
因為各相鄰點權重不同， 所以f3為Fn的一個鄰點全和可區別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）.
因為各相鄰點權重不同， 所以f4為Fn的一個鄰點全和可區別2-全染色.
定理2"fgndi∑（Bk）=2.
證明： 由定義3知， 圖Bk是一個三正則圖. 由引理1知， 至少用2 種顏色才能完成Bk的一個鄰點全和可區別全染色. 對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）}∪{vi5vi+15i≡1（mod 2）}
∪{vi3vi8i≡0（mod 2）}∪{vi4vi7i≡1（mod 2）}∪{vi3vi4i≡1（mod 2）}∪{vi4vi+13i≡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）.
因為各相鄰點權重不同， 所以f5為Bk的一個鄰點全和可區別2-全染色.
定理3"fgndi∑（Dn）=2.
證明： 由定義4知， 圖Dn是一個三正則圖. 由引理1知， 至少用2種顏色才能完成Dn的一個鄰點全和可區別全染色.
情形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，vn-16v05，vn-12v01，vn-18v07 }∪{vi1vi3}∪{vi6vi10i≠n-1}
∪{vi10vi+19i≠n-1}∪{vi1vi7i≠0}∪{vi2vi8i≠n-1}
∪{vi8vi+17i≡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.
因為各相鄰點權重不同， 所以f6為Dn的一個鄰點全和可區別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，vn-16v05，vn-12v01 }∪{vi1vi3}∪{vi6vi10i≠n-1}∪{vi10vi+19i≠n-1}
∪{vi1vi7}∪{vi2vi8i≠n-1}∪{vi8vi+17i≡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.
因為各相鄰點權重不同， 所以f7為Dn的一個鄰點全和可區別2-全染色.
定理4"fgndi∑（Ln）=2.
證明： 由定義5知， 圖Ln是一個三正則圖. 由引理1知， 至少用2 種顏色才能完成Ln的一個鄰點全和可區別全染色. 下面定義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的一個鄰點全和可區別2-全染色.
參考文獻
［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］"程銀萬， 楊超， 姚兵. 關于哈林圖的鄰和可區別染色的注記 ［J］. 吉林大學學報（理學版）， 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］"王芹， 楊超， 常景智， 等. 平方圖的鄰點全和可區別全染色 ［J］. 華南師范大學學報（自然科學版）， 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］"常景智， 楊超， 程銀萬， 等. 兩類正則圖的鄰點全和可區別全染色 ［J］. 西南大學學報（自然科學版）， 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］"程銀萬， 楊超， 姚兵. 若干倍圖的鄰點全和可區別全染色 ［J］. 華中師范大學學報（自然科學版）， 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圖的強邊染色 ［J］. 長春師范大學學報， 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圖的強邊染色 ［J］. 東北師大學報（自然科學版）， 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.）
（責任編輯： 趙立芹）
