赵亚迪, 陈祥恩

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

1 引言与预备知识

目前, 关于图的点可区别的正常边染色与点可区别的一般边染色研究已有很多结果[1-6]. 图G的一个k-全染色是指用k种颜色{1,2,…,k}对图G的全体顶点及边的一个分配, 对图G的每个顶点y,Cf(y)指在f下点y的颜色及与y关联的全体边的颜色构成的集合(非多重集), 称为y的色集合. 设f是图G的一个正常全染色, 如果对∀u,v∈V,u≠v, 有C(u)≠C(v), 则称f是图G的点可区别全染色(VDTC)[7-8].

本文所研究的图均为有限的无向简单图, 考虑点可区别的一类未必正常的全染色. 设f为图G的k-全染色, 若任意两个相邻顶点在f下的色不相同, 且任意两条相邻边在f下的色也不相同, 则该染色f称为图G的Ⅰ-全染色. 如果在f下图G的任意相邻两条边均染不同颜色, 则称f为Ⅵ-全染色. 易知Ⅰ-全染色必为Ⅵ-全染色[9-10]. 设f为图G的Ⅰ-全染色(Ⅵ-全染色), 若图G任意两个顶点的色集合均不相同, 则称f是点可区别的. 分配k种颜色的点可区别的Ⅰ-全染色简记为k-VDITC(k-点可区别的Ⅵ-全染色简记为k-VDVITC).

显然图的VDITC一定是图的VDVITC, 因此本文只需讨论图的最优VDITC, 从而可得出图的最优VDVITC. Chen等[10]提出了图的VDITC和图的VDVITC, 从而确定了完全图、 完全二部图、 轮、 扇、 正规双星、 路、 圈等图类的点可区别的Ⅰ-全色数以及点可区别的Ⅵ-全色数, 并提出了以下猜想.

苗婷婷等[11-12]研究了两条路的联图、 圈与路的联图、 圈与圈、 圈与轮、 圈与扇的联图的VDITC和VDVITC； 杨晗等[13]研究了m个阶为4的圈的不交并的点可区别的Ⅰ-全染色和Ⅵ-全染色. 本文通过构造m个长为15的圈的不交并mC15的最优VDITC, 确定mC15的点可区别Ⅰ-全色数以及当m≥1时mC15的点可区别Ⅵ-全色数. 结果表明: 对于图mC15, VDITC猜想和VDVITC猜想均成立.

构造如下(n-1)×(n-1)阶矩阵An(n≥5), 使矩阵An中元素是集合{1,2,…,n}的含n的2-子集、 3-子集(即构造某个VDITC下点的色集合, 非多重集)或空集, 其中第i行含有(i-1)个Ø：

定义1设1≤i1

定义2若矩阵An的15个元素(非空)恰为C15的某个VDITC下C15全体顶点的色集合, 则称由这15个元素构成的组为一个好组.

图1 图C15的全染色

2 主要结果

下面考虑剩余元素为{k,i,k-1}(i=1,2,…,n-1)的染色.

证毕.

由命题1和定理1可得如下结论：

本文结论表明VDITC和VDVITC猜想对图mC15也成立.