路的强积的邻点可区别边染色

安卓莫 ,田双亮,2,蔡 瑾

(1.西北民族大学 数学与计算机科学学院,甘肃 兰州 730030；2.西北民族大学 动态流数据计算与应用重点实验室,甘肃 兰州 730030)

0 引言

本文所考虑的图G都是有限、无向的简单连通图,用V(G)与E(G)分别表示G的顶点集和边集,并用Δ(G)表示G的最大度，记(x)k=x(modk),其中x为整数,k为正整数.

由邻点可区别边染色概念,容易得到以下引理.

引理1.1 若阶至少为3的简单图G中存在相邻的最大度点,则

χ＇α(G)≥Δ(G)+1.

zhang等在文献[1]中提出了邻点可区别边染色概念,并研究了一些基本简单图，如路、圈、完全图、树等的邻点可区别边染色,得到了相应的邻点可区别边色数.Balister在文献[2]中证明了最大度为3的图的邻点可区别边色数不超过5,二部图的邻点可区别边色数不超过其最大度加2,并证明这些上界是可达的.Hatami在文献[3]中证明了任意图的邻点可区别边色数不超过其最大度加300.由于图的结构运算是构造图的重要方法和手段,因此,研究运算图的邻点可区别的边染色有助于确定一般图类的相应染色数.常见的图结构运算有图的字典积、图的笛卡尔积、图的联，以及图的半强积、直积等等.Tian等在文献[4]与[5]中研究了一些特殊图的字典积与笛卡尔积的邻点可区别的边染色,得到了相应的邻点可区别边色数.Baril、Chen等在文献[6]与[7]中得到了一些网格图与超立方体的邻点可区别的边色数.何雪等在文献[8]中给出了一些特殊图的倍图(即二阶路与图的半强积)的邻点可区别边色数.

设Pm=v0v1…vm-1,Pn=v0v1…vn-1是两条路,其中m,n≥2.为了方便叙……