路與幾類圖的Cartesian 積的鄰點擴展和可區(qū)別全染色

王國興

(1. 蘭州財經大學絲綢之路經濟研究院，蘭州 730020; 2. 蘭州財經大學信息工程學院，蘭州 730020)

1 引言

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

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

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

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

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

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

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

圖1 Cartesian 積P5□P3

本文通過對Cartesian 積的結構進行分析，應用構造染色模式的方法證明了Cartesian積：Pm□Cn, Pm□Wn, Pm□Kn的鄰點擴展和可區(qū)別全色數(shù)均為2.說明文獻[1]提出的NESDTC 猜想對于Cartesian 積：Pm□Cn, Pm□Wn, Pm□Kn是成立的.

2 一些重要引理

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

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

3 主要結果

表示C3=u1u2u3u1的NESD 2-全染色f，其中52表示頂點u1的擴展和為5，且u1的顏色為2.其余符號表示的意思類似.設P, Q分別為r行s列和r行t列的模式.用Pk表示P重復出現(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對應的序列對Pm□Cn中的m個圈分別進行染色，再將這m個圈之間的邊都用顏色1 染色，可得到Pm□Cn的一個NESD 2-全染色(見(R1R2R1···R2R1)′).

情形2.2m ≡0 (mod 2).

當m=2 時，用R1R2對P2□Cn中的2 個圈分別進行染色，再將這2 個圈之間的邊用顏色2,1,··· ,1 依次染色，可得到P2□Cn的一個NESD 2-全染色.

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

綜上所述，結論成立.

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

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

綜上所述，結論成立.

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

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

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

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

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

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

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

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

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