圖的corona積的局部反魔幻著色數(shù)

楊 雪,邊 紅*,于海征, 丁吉麗

(1.新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，新疆 烏魯木齊 830017;2.新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830046)

1 預(yù)備知識

令G=(V(G),E(G))是一個沒有孤立點的有限簡單無向圖.稱一個雙射f:E(G)→{1，2，…，|E(G)|}為圖G的反魔幻標(biāo)號，如果f滿足對于圖G的任意兩個頂點u和v都有w(u)≠w(v)，其中w(u)=∑e∈E(u)f(e)，E(u)是與頂點u相關(guān)聯(lián)的邊的集合.一個圖G稱為反魔幻的，如果圖G有一個反魔幻標(biāo)號.

圖的反魔幻標(biāo)號的定義是由Hartsfield等[1]在1994年提出的， 他們還提出“除了K2以外的所有連通簡單圖都有一個反魔幻標(biāo)號”的猜想，但至今這個猜想尚未完全解決.

近幾年，Arumugam等[2]和Bensmail等[3]分別獨立地提出了一個比反魔幻標(biāo)號相對較弱的定義：局部反魔幻標(biāo)號，并且也都提出“除了K2以外的所有連通簡單圖都有一個局部反魔幻標(biāo)號”的猜想.這個猜想已由Haslegrave[4]得到完全解決.稱一個雙射f:E(G)→{1，2，…，|E(G)|}是圖G的一個局部反魔幻標(biāo)號，如果對于圖G的任何兩個相鄰的頂點u和v都有w(u)≠w(v)，其中w(u)=∑e∈E(u)f(e)，E(u)是與點u相關(guān)聯(lián)的邊的集合.一個圖G稱為局部反魔幻的，如果圖G有一個局部反魔幻標(biāo)號.若對圖G的點v著顏色w(v),顯然圖G的任一個局部反魔幻標(biāo)號自然地導(dǎo)出圖G的一個正常點著色.同時Arumugam等[2]提出了局部反魔幻著色數(shù)的定義：圖G的局部反魔幻著色數(shù)是其局部反魔幻標(biāo)號中所使用的最少顏色數(shù)，記為χla(G)，他們還給出了路、圈、友誼圖、輪圖等一些特殊圖類的局部反魔幻著色數(shù)的確切值.

圖1 圖

2.1 圖Fn○K1的局部反魔幻著色數(shù)

友誼圖Fn的頂點集V(Fn)={v1，v2，…，v2n，v2n+1}，其中v2n+1是友誼圖Fn中的n個三角形的公共頂點；邊集E(Fn)={vivi+1：1≤i≤2n,i是奇數(shù)}∪{v2n+1vi：1≤i≤2n}.圖Fn○K1中K1的2n+1個拷貝點記為{d1，d2，…，d2n,d2n+1}，如圖2所示.

圖2 圖Fn○K1Fig.2Graph Fn○K1

下面的引理1和引理2分別給出了圖Fn○K1的局部反魔幻著色數(shù)的上、下界，由此可以得到圖Fn○K1的局部反魔幻著色數(shù)的確切值.

證明令f(e)表示圖Fn○K1中邊e上的局部反魔幻標(biāo)號.對于圖Fn○K1的邊{v2n+1vi：1≤i≤2n}和邊{vivi+1:i是奇數(shù)}，給出如下標(biāo)號:

f(v2n+1vi)=4n+2-i,當(dāng)1≤i≤2n且i是偶數(shù)時；

對于邊{vidi:1≤i≤2n},給如下標(biāo)號:

最后，令f(v2n+1d2n+1)=5n+1.對于1≤i≤2n,根據(jù)i的奇偶性，對圖Fn○K1中的點vi的標(biāo)號和w(vi)(即點vi所著顏色)進(jìn)行分類討論.

當(dāng)i是奇數(shù)且i≠2n+1時，點vi所著顏色

w(vi)=5n+1，

當(dāng)i是偶數(shù)時，點vi所著顏色是

w(vi)=8n+2，

而點v2n+1所著顏色是

易知這3類點所著顏色互不相同.而圖Fn○K1中的點dj(1≤j≤2n+1)所著顏色顯然互不相同，故這2n+1個點共著了2n+1個不同顏色.點d2n+1所著顏色是

w(d2n+1)=5n+1,

若對中心點v2n+1相關(guān)聯(lián)的邊使用最小標(biāo)號，有

w(v2n+1)=1+2+…+2n+1>5n+1≥w(dj)，

根據(jù)引理1和引理2可以得到圖Fn○K1的局部反魔幻著色數(shù)的確切值，有

若對中心點相關(guān)聯(lián)的邊使用最小標(biāo)號，有

w(v2n+1)=1+2+…+2n+m>m(2n+1)+3n,

而任意一個懸掛點dj所著顏色

w(dj)≤m(2n+1)+3n,(1≤j≤m(2n+1)),

即可，其中a∈{1，2}.

w(vi)=w(dj)≤m(2n+1)+3n,i≠j, 1≤i≤

2n, 1≤j≤m(2n+1).

顯然與這2n個頂點不相關(guān)聯(lián)的邊有m條，則與這2n個頂點相關(guān)聯(lián)的邊有2mn+3n條.令這2n個頂點的著色總和為σ,則有

σ≤2n[m(2n+1)+3n].

此外，若對與這2n個點相關(guān)聯(lián)的2mn+3n條邊使用最小的標(biāo)號，有

σ≥1+2+…+(2mn+3n),

故

2n[m(2n+1)+3n]≥1+2+…+(2mn+3n).

又因為

1+2+…+(2mn+3n)-2n[m(2n+1)+3n]=

4m2n2+4mn2-3n2-2mn+3n>0,

這與2n[m(2n+1)+3n]≥1+2+…+(2mn+3n)是矛盾的.

σ≤k[m(2n+1)+3n].

此外,若與這k個點相關(guān)聯(lián)的n+(m+1)k條邊使用最小標(biāo)號，則

a≥1+2+…+n+(m+1)k.

故

1+2+…+n+(m+1)k≤k[m(2n+1)+3n].

而

1+2+…+n+(m+1)k-k[m(2n+1)+3n]=

1≤j≤m}.

w(vi)=5n+1，

當(dāng)i是偶數(shù)時，點vi相關(guān)聯(lián)的部分邊標(biāo)號和是

w(vi)=8n+2,

點v2n+1相關(guān)聯(lián)的部分邊標(biāo)號和是

通過計算可知：當(dāng)i是奇數(shù)且i≠2n+1時，點vi著顏色

當(dāng)i是偶數(shù)時，點vi著顏色

點v2n+1著顏色

因此得到了3個互異的顏色且這3個顏色不同于懸掛點著的顏色，得證.

通過計算可得：當(dāng)i是奇數(shù)且i≠2n+1時，點vi所著顏色是

當(dāng)i是偶數(shù)時，點vi所著顏色是

點v2n+1所著顏色是

由此得到3種互異的顏色且這3種顏色不同于懸掛點所著顏色，得證.

m},

n,1≤j≤m}.

本節(jié)將根據(jù)星圖Sn的頂點個數(shù)給出圖Sn○K1的局部反魔幻著色數(shù)的確切值.

n}.

圖3 圖Sn○K1Fig.3Graph Sn○K1

當(dāng)n≥2時，圖Sn○K1有n+1個葉子點，則由定理3易知圖Sn○K1的局部反魔幻著色數(shù)的下界.

下面給出圖Sn○K1的局部反魔幻著色數(shù)的上界.

證明根據(jù)圖Sn○K1中邊的分布情況，將邊如下標(biāo)號(其中1≤i≤n,x為中心點)：

f(xui)=i,

f(xd1)=2n+1.

可以得到

w(ui)=2n+1,

w(d1)=2n+1,

根據(jù)引理6和引理7,可以得到圖Sn○K1的局部反魔幻著色數(shù)的確切值.

m},

n,1≤j≤m}.

即可.

w(x)=1+2+…+n+m>m(n+1)+n,

而每個懸掛點所著顏色都不超過m(n+1)+n,所以剩余的n個點必定與某些懸掛點著相同顏色.

與點ui(1≤i≤n)相關(guān)聯(lián)的邊有n(m+1)條.令σ為這剩余的n個點所著顏色的總和.若對與這n個點相關(guān)聯(lián)的邊用最小標(biāo)號，則有

σ≥1+2+…+n(m+1).

另一方面，每個點ui(1≤i≤n)所著顏色必與某個懸掛點所著顏色相同，而每個懸掛點所著顏色都不超過m(n+1)+n,則有

σ≤n[m(n+1)+n].

故

n[m(n+1)+n]≥1+2+…+n(m+1).

事實上，

[1+2+…+n(m+1)]-n[m(n+1)+n]=

m2n+1>0,

因此，n[m(n+1)+n]≥1+2+…+n(m+1)是不可能的，矛盾.

m},

n,1≤j≤m}.

f(xui)=i,

f(xd1)=2n+1.

f(xdj)=mn+n+j,當(dāng)j≠1時.

綜上可得，當(dāng)1≤i≤n時，ui所著顏色

中心點x所著顏色

f(xdj)=2n+j.

f(xdj)=nm+n+j,當(dāng)3≤j≤m時.

綜上可知，點ui所著顏色

點x所著顏色

容易看出這是兩個互異的顏色，且不同于懸掛點所著的顏色，得證.

f(xd1)=n+1,

f(xdj)=nm+n+j,當(dāng)3≤j≤m時.

綜上可知，點ui所著顏色

點x所著顏色

容易看出這是兩個互異的顏色，且不同于懸掛點著的顏色，得證.