杨 澜,陈祥恩

(西北师范大学 数学与统计学院,甘肃兰州 730070)

§1 引言

关于图的点可区别一般边染色已进行了许多研究(如[1-4]).图G的一个E-全染色φ是指使相邻点着以不同色且每条关联边与它的端点着以不同的色的全染色.用C(x)表示在φ的作用下点x的颜色以及与x关联的边的色所构成的集合(非多重集合).设φ为G的一个E-全染色,若∀u,v ∈V(G),u≠v,有C(u)≠C(v),则φ称为图G的点可区别E-全染色(Vertex-Distinguishing E-Total Coloring),简称为VDET染色.令存在k−VDET染色}.称为图G的点可区别E-全色数.

文[5]中探讨了完全图,完全二部图K2,n,星,轮,扇,路和圈的VDET染色.文[6]中得出了m个三阶圈的联图和m个四阶圈的联图的VDET色数.文[7-9]中讨论了完全二部图K3,n,K4,n,K5,n的VDET染色,文[10-11]中部分讨论了完全二部图K7,n的VDET染色.本文主要讨论了K8,n(8≤n ≤34)的VDET染色并且得到了K8,n的VDET色数.

在本文中,对于完全二部图K8,n,令V(K8,n)=X ∪Y,E(K8,n)={uivj:1≤i ≤8,1≤j ≤n},其中X={u1,u2,···,u8},Y={v1,v2,···,vn}.

给定K8,n的一个点可区别E-全染色φ,令

给定一个正整数k,{1,2,···,k}的i-子集是指{1,2,···,k}的包含i个元素的集合.

给定一个正整数l,一个集合M,|M|=l是指集合M中包含l个元素.

§2 主要结果及其证明

定理1当8≤n ≤34时,有(K8,n)=6.

证先证K8,n不存在5-VDET染色.设K8,n有一个5-VDET染色φ,颜色分别为1,2,3,4,5.考虑以下4种情形.

情形1|{φ(ui)|i=1,2,···,8}|=1.

此时A1中至少有3个成员都属于C(Y),可知:在2,3,4,5中至少有一种色同时包含在每个C(ui)中,不妨设2∈C(ui),i=1,2,···,8,则每个C(ui)只可能是以下8个集合之一:{1,2},{1,2,3},{1,2,4},{1,2,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,2,3,4,5}.又因为{3,4},{3,5},{4,5},{3,4,5}这三个集合中至少有一个属于C(Y),则{1,2}一定不属于C(X),7个集合不能区分X中的8个顶点,矛盾.

情形2|{φ(ui)|i=1,2,···,8}|=2.

是{1,2,3,4,5}的4-子集,5-子集以及不在中的3-子集构成的集合.

情形2.1中的成员均不属于C(Y),显然也不属于C(X).

情形2.1.1Y中任一顶点的色集合不含中的成员.

事实……