贾秀卿, 李沐春

(兰州交通大学 应用数学研究所, 兰州 730070)

1 引言与主要结果

本文所讨论的图均为简单无向连通图.一个图G对应于一个有序三元组(V,E,φ), 其中V(G)表示图G的顶点集,E(G)表示图G中与V(G)不相交的边集,φ(G)表示图G顶点集与边集的关联函数, 使得对∀e∈E(G),u,v∈V(G), 有φ(e)=uv, 此时称u和v相邻,u和v是边e的两个端点, 同时也称u和v分别与e相关联.若图G中的两条边e1和e2仅有一个公共端点, 则称e1与e2相邻.与顶点x关联边的数目称为顶点x的度数, 记为d(x).称Δ(G)=max{d(x)|x∈V(G)}为图G的最大度, 简记为Δ.图G中度数为1的顶点称为悬挂点, 与悬挂点相邻的点称为次悬挂点.点u和v之间的距离定义为图G中最短的(u,v)路长, 记为d(u,v).一个边数等于点数的简单连通图称为单圈图.图G中最短圈的长称为图G的围长, 记为g(G).图G的一个正常k-边染色是指映射f:E→{1,2,…,k}, 使得对任意两条相邻的边e1和e2, 均有f(e1)≠f(e2).一个顶点x∈V在f下的色集合Sf(x)是指所有与x关联的边在f下的颜色构成的集合.

特别地, 当β=2时,D(β)-点可区别边染色称为D(2)-点可区别边染色.如果两个距离不超过2的顶点u,v在D(2)-点可区别边染色函数f下满足Sf(u)≠Sf(v), 则称u与v在f下是D(2)-点可区别的.

基于文献[9], 本文考虑单圈图在2-距离以内的D(2)-点可区别边染色.用数学归纳法并结合Hall定理, 得到如下结论:

定理1设G是围长为g的非圈单圈图,C是G中唯一的圈.如果G满足下列条件:

1) 当Δ(G)=3时, 圈上只有一个3度点,g≡0(mod 3)且次悬挂点在圈上; 或圈上有至少两个3度点且任意两个3度点的距离至少为3;

2) 当Δ(G)=4时, 任意两个4度点的距离至少为3且不包含如图1所示的S5作为子图;

图1 图……