文档介绍：第对卷第4 期 V ol .拼 N o .4
2 0 0 7 年 1 2 月 I b 〕. 2通X 片
关于Cm V C。和Cm V S。的点可区别边色数‘
马刚‘,张忠辅2
(1、西北民族大学计算机科学与信息工程学院,甘肃兰州,73 00 30 ;
2、兰州交通大学应用数学研究所,甘肃兰州,73 仪J7 0)
摘要对图‘的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色
法, 氏和几V 凡的点可区别边色数.
关键词圈,星,联图,点可区别边色数
中圈分类号 0 文献标识码 A
1. 引言
,Bu tri s等先后提出
点可区别边染色和邻点可区别边染色卜习,得到了若干结果,并提出了有关猜想,但所知结果较少.
定义1[, 一2〕对无孤立边且至多有一个孤立点的简单图 c (v,E )的一个 k- 正常边染色
法[5] f,若满足V “,。任V( C) ,且。并。,有c( “)笋c( 。).则称f 为‘的一个‘点可区别边染色
法,简记作‘的东舰 c (G) =而n{k!‘的k- 班)E C 法}称为‘的点可区别边色数.
其中,C( u) 二!f( 训)!彻e E(G) }称为点u 在f 下的色集,c(u) 在色全集合 c = 11,2,⋯,引
中的补集记为乙(u)二C \ C(u).
猜想[,·4] 对IF(c)1之3的连通图C,有户(C)‘x“(C)‘群(G)+ ,产(G)二max
{而nll!暇七n‘,占‘1‘△}},暇表示1个不同元素中任取1个元素的组合数,n‘为度为1的点
数才、△分别表示‘的最小、最大度数.
定义2[,〕设简单图c 与万有:v(c)门v(万)二,;￡(c)自E (H )二,.若满足:
V (G V H )= V(C )U V(万);E (G V 万)= E (C)U E (H )U {砌lu任y(G),,〔V(H )}.则称
G V H 为C 与H 的联图
护
.
‘ n , 一 n三1(m 记2);
引理 1[’·2] 对 n 全3的几阶完全图Kn ,有x场(凡) 一 L
n + 1,n 二0(m记2).
引理2[‘一2] 对Iv(c)1全3的连通图G,有x“(G)之产(G)。
文中未加述及的术语、记号可参见文献【5」.本文给出了Cm 和氏V S。的点可区别边
色数.
2. 主要结论及其证明
引理3 当m 七n七3 时,对氏 V C。,有△(氏V 氏)= m + 2.
引理4 对于焦V S。,有△(C二V S。)= m + n.
。基金项目:国家民委科研项目(No .05 XI刃7);国家自然科学基金资助项目(No .叨刃1037).
收稿日期:2(X 拓一11一15
万方数据
一 4 38 一经济数学第 24 卷
护
.
.6, m 二n 二3;
.
产
一- I m + 4 ,m 二n 2 4 ;
引理5 当m 全n之3时,对氏V 几,有召(氏V 久) L
凡 m + 3 ,