王國(guó)興

(1. 蘭州財(cái)經(jīng)大學(xué)絲綢之路經(jīng)濟(jì)研究院，蘭州 730020; 2. 蘭州財(cái)經(jīng)大學(xué)信息工程學(xué)院，蘭州 730020)

1 引言

本文中僅考慮有限、無(wú)向簡(jiǎn)單圖.設(shè)G= (V,E)表示頂點(diǎn)集為V，邊集為E的簡(jiǎn)單圖.對(duì)任意x ∈V(G), N(x) ={y ∈(G)|xy ∈E}表示頂點(diǎn)x的鄰集.此外，用Pn, Cn, Kn和Wn分別表示n個(gè)點(diǎn)的路、圈、完全圖和輪.

圖G的一個(gè)k-全染色是k種顏色1,2,··· ,k在圖G的所有頂點(diǎn)及邊上的一個(gè)分配.設(shè)f是圖G的一個(gè)k-全染色，對(duì)任意的x ∈V(G)，稱

為點(diǎn)x的擴(kuò)展和.圖G的一個(gè)k-全染色f滿足對(duì)任意的xy ∈E(G)，有w(x)/=w(y)，則稱f是鄰點(diǎn)擴(kuò)展和可區(qū)別的(簡(jiǎn)記為NESD).使得圖G存在NESDk-全染色的k的最小值被稱為圖G的鄰點(diǎn)擴(kuò)展和可區(qū)別全色數(shù)，簡(jiǎn)記為egndi∑(G).

Kalkowski 等人[1]引入并研究了圖的鄰和可區(qū)別一般邊染色.Przybylo 和Wo′znizk[2]進(jìn)一步提出鄰和可區(qū)別一般全染色的概念，該問(wèn)題的相關(guān)研究見(jiàn)文獻(xiàn)[3-6].Flandrin 等人[7]在此基礎(chǔ)上提出鄰點(diǎn)擴(kuò)展和可區(qū)別全染色，并對(duì)一些特殊圖類：路、圈、完全圖、樹(shù)等進(jìn)行了研究.同時(shí)，他們提出了如下猜想：

猜測(cè)1(NESDTC 猜想)[7]任意一個(gè)圖的鄰點(diǎn)擴(kuò)展和可區(qū)別全色數(shù)不超過(guò)2.

圖G與圖H的Cartesian 積(或稱卡氏積)記為G□H，其中V(G□H) =V(G)×V(H),(x1,x2)(y1,y2)∈E(G□H)，當(dāng)且僅當(dāng)x1y1∈E(G)且x2=y2，或者x2y2∈E(H)且x1=y1.

例如，路P5與P3的Cartesian 積P5□P3，如圖1 所示.

圖1 Cartesian 積P5□P3

本文通過(guò)對(duì)Cartesian 積的結(jié)構(gòu)進(jìn)行分析，應(yīng)用構(gòu)造染色模式的方法證明了Cartesian積：Pm□Cn, Pm□Wn, Pm□Kn的鄰點(diǎn)擴(kuò)展和可區(qū)別全色數(shù)均為2.說(shuō)明文獻(xiàn)[1]提出的NESDTC 猜想對(duì)于Cartesian 積：Pm□Cn, Pm□Wn, Pm□Kn是成立的.

2 一些重要引理

命題1[7]設(shè)Pm(m ≥2)是m階的路，則

引理2[8-10]設(shè)G為簡(jiǎn)單圖，點(diǎn)u與點(diǎn)v是圖G的兩個(gè)相鄰頂點(diǎn)，且dG(u)≥2dG(v)，則對(duì)G的任意一個(gè)2-全染色，均有w(u)/=w(v).

3 主要結(jié)果

表示C3=u1u2u3u1的NESD 2-全染色f，其中52表示頂點(diǎn)u1的擴(kuò)展和為5，且u1的顏色為2.其余符號(hào)表示的意思類似.設(shè)P, Q分別為r行s列和r行t列的模式.用Pk表示P重復(fù)出現(xiàn)k次的r行ks列的模式，用PQ表示P和Q依次出現(xiàn)的r行s+t列的模式.

情形1.1m ≡0 (mod 3).

令

表示Cn=v1v2···vnv1的3 種不同的NESD 2-全染色.

情形2.1m ≡1 (mod 2).

用R1R2···R1對(duì)應(yīng)的序列對(duì)Pm□Cn中的m個(gè)圈分別進(jìn)行染色，再將這m個(gè)圈之間的邊都用顏色1 染色，可得到Pm□Cn的一個(gè)NESD 2-全染色(見(jiàn)(R1R2R1···R2R1)′).

情形2.2m ≡0 (mod 2).

當(dāng)m=2 時(shí)，用R1R2對(duì)P2□Cn中的2 個(gè)圈分別進(jìn)行染色，再將這2 個(gè)圈之間的邊用顏色2,1,··· ,1 依次染色，可得到P2□Cn的一個(gè)NESD 2-全染色.

用R1R2···R1R2R1R3對(duì)應(yīng)的序列對(duì)Pm□Cn中的m個(gè)圈分別進(jìn)行染色，再將這m個(gè)圈之間的邊都用顏色1 染色，可得到Pm□Cn的2-全染色(R1R2···R1R2R1R3)′.易看出，此模式中只有第(1,m-2)個(gè)元素和第(1,m-1)個(gè)元素對(duì)應(yīng)的頂點(diǎn)是擴(kuò)展和相同的相鄰頂點(diǎn).由圈Cn的NESD 2-全染色g可知，第(1,m-1)個(gè)元素和第(2,m-1)個(gè)元素對(duì)應(yīng)頂點(diǎn)之間的邊顏色是1.將這條邊的顏色由1 改為2，可得到Pm□Cn的一個(gè)NESD 2-全染色(見(jiàn)(R1R2···R1R2R1R3)′′).

綜上所述，結(jié)論成立.

根據(jù)上述分析，對(duì)任意x ∈V(Pm□Wn)A，有wf′(x)=wf(x)+3.因此，對(duì)任意相鄰頂點(diǎn)y,z ∈V(Pm□Wn)A, wf′(y)/=wf′(z).由于n ≥9，利用引理2 可知，對(duì)任意相鄰頂點(diǎn)y ∈V(Pm□Wn)A和z ∈A, wf′(y)/=wf′(z).

因此，對(duì)任意相鄰頂點(diǎn)y, z ∈A，有wf′(y)/=wf′(z).

綜上所述，結(jié)論成立.

由文獻(xiàn)[7]的定理8 和推論9 可以知道，Kn存在滿足一定要求的鄰點(diǎn)擴(kuò)展和可區(qū)別2-全染色.該染色在如下的引理3 中給出.

引理3[7]設(shè)n ≥3, V(Kn)={v1,v2,··· ,vn}.

1) 若n是偶數(shù)，則Kn存在鄰點(diǎn)擴(kuò)展和可區(qū)別2-全染色f，使得

定理2 設(shè)m ≥2, n ≥3，則egndi∑(Pm□Kn)=2.

證明 若n=3，則Pm□K3=Pm□C3.根據(jù)定理1 可知結(jié)論成立.

情形1n是偶數(shù)且n ≥4.

圖2 n 是偶數(shù)時(shí)Pm□Kn 的NESD 2-全染色示意圖

情形2n是奇數(shù)且n ≥5.

圖3 n 是奇數(shù)時(shí)Pm□Kn 的NESD 2-全染色示意圖