图的corona积的局部反魔幻着色数

杨 雪,边 红*,于海征, 丁吉丽

(1.新疆师范大学数学科学学院，新疆 乌鲁木齐 830017;2.新疆大学数学与系统科学学院，新疆 乌鲁木齐 830046)

1 预备知识

令G=(V(G),E(G))是一个没有孤立点的有限简单无向图.称一个双射f:E(G)→{1，2，…，|E(G)|}为图G的反魔幻标号，如果f满足对于图G的任意两个顶点u和v都有w(u)≠w(v)，其中w(u)=∑e∈E(u)f(e)，E(u)是与顶点u相关联的边的集合.一个图G称为反魔幻的，如果图G有一个反魔幻标号.

图的反魔幻标号的定义是由Hartsfield等[1]在1994年提出的， 他们还提出“除了K2以外的所有连通简单图都有一个反魔幻标号”的猜想，但至今这个猜想尚未完全解决.

近几年，Arumugam等[2]和Bensmail等[3]分别独立地提出了一个比反魔幻标号相对较弱的定义：局部反魔幻标号，并且也都提出“除了K2以外的所有连通简单图都有一个局部反魔幻标号”的猜想.这个猜想已由Haslegrave[4]得到完全解决.称一个双射f:E(G)→{1，2，…，|E(G)|}是图G的一个局部反魔幻标号，如果对于图G的任何两个相邻的顶点u和v都有w(u)≠w(v)，其中w(u)=∑e∈E(u)f(e)，E(u)是与点u相关联的边的集合.一个图G称为局部反魔幻的，如果图G有一个局部反魔幻标号.若对图G的点v着颜色w(v),显然图G的任一个局部反魔幻标号自然地导出图G的一个正常点着色.同时Arumugam等[2]提出了局部反魔幻着色数的定义：图G的局部反魔幻着色数是其局部反魔幻标号中所使用的最少颜色数，记为χla(G)，他们还给出了路、圈、友谊图、轮图等一些特殊图类的局部反魔幻着色数的确切值.

图1 图

2.1 图Fn○K1的局部反魔幻着色数

友谊图Fn的顶点集V(Fn)={v1，v2，…，v2n，v2n+1}，其中v2n+1是友谊图Fn中的n个三角形的公共顶点；边集E(Fn)={vivi+1：1≤i≤2n,i是奇数}∪{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的局部反魔幻着色数的上、下界，由此可以得到图Fn○K1的局部反魔幻着色数的确切值.

证明令f(e)表示图Fn○K1中边e上的局部反魔幻标号.对于图Fn○K1的边{v2n+1vi：1≤i≤2n}和边{vivi+1:i是奇数}，给出如下标号:

f(v2n+1vi)=4n+2-i,当1≤i≤2n且i是偶数时；

对于边{vidi:1≤i≤2n},给如下标号:

最后，令f(v2n+1d2n+1)=5n+1.对于1≤i≤2n,根据i的奇偶性，对图Fn○K1中的点vi的标号和w(vi)(即点vi所着颜色)进行分类讨论.

当i是奇数且i≠2n+1时，点vi所着颜色

w(vi)=5n+1，

当i是偶数时，点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相关联的边使用最小标号，有

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

根据引理1和引理2可以得到图Fn○K1的局部反魔幻着色数的确切值，有

若对中心点相关联的边使用最小标号，有

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个顶点不相关联的边有m条，则与这2n个顶点相关联的边有2mn+3n条.令这2n个顶点的着色总和为σ,则有

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

此外，若对与这2n个点相关联的2mn+3n条边使用最小的标号，有

σ≥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个点相关联的n+(m+1)k条边使用最小标号，则

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，

当i是偶数时，点vi相关联的部分边标号和是

w(vi)=8n+2,

点v2n+1相关联的部分边标号和是

通过计算可知：当i是奇数且i≠2n+1时，点vi着颜色

当i是偶数时，点vi着颜色

点v2n+1着颜色

因此得到了3个互异的颜色且这3个颜色不同于悬挂点着的颜色，得证.

通过计算可得：当i是奇数且i≠2n+1时，点vi所着颜色是

当i是偶数时，点vi所着颜色是

点v2n+1所着颜色是

由此得到3种互异的颜色且这3种颜色不同于悬挂点所着颜色，得证.

m},

n,1≤j≤m}.

本节将根据星图Sn的顶点个数给出图Sn○K1的局部反魔幻着色数的确切值.

n}.

图3 图Sn○K1Fig.3Graph Sn○K1

当n≥2时，图Sn○K1有n+1个叶子点，则由定理3易知图Sn○K1的局部反魔幻着色数的下界.

下面给出图Sn○K1的局部反魔幻着色数的上界.

证明根据图Sn○K1中边的分布情况，将边如下标号(其中1≤i≤n,x为中心点)：

f(xui)=i,

f(xd1)=2n+1.

可以得到

w(ui)=2n+1,

w(d1)=2n+1,

根据引理6和引理7,可以得到图Sn○K1的局部反魔幻着色数的确切值.

m},

n,1≤j≤m}.

即可.

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

而每个悬挂点所着颜色都不超过m(n+1)+n,所以剩余的n个点必定与某些悬挂点着相同颜色.

与点ui(1≤i≤n)相关联的边有n(m+1)条.令σ为这剩余的n个点所着颜色的总和.若对与这n个点相关联的边用最小标号，则有

σ≥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,当j≠1时.

综上可得，当1≤i≤n时，ui所着颜色

中心点x所着颜色

f(xdj)=2n+j.

f(xdj)=nm+n+j,当3≤j≤m时.

综上可知，点ui所着颜色

点x所着颜色

容易看出这是两个互异的颜色，且不同于悬挂点所着的颜色，得证.

f(xd1)=n+1,

f(xdj)=nm+n+j,当3≤j≤m时.

综上可知，点ui所着颜色

点x所着颜色

容易看出这是两个互异的颜色，且不同于悬挂点着的颜色，得证.