图的强直积的2-距离染色

• 作者: 刘娟 陈祥恩 马宝林
• 来源期刊: 山东大学学报（理学版）
• 学科: 数学
• 关键词: 图 图的强直积 2-距离染色 2-距离色数
• 年，卷（期）: 2010,（3）
• 所属期刊栏目: 数学
• 页码范围: 66-70
• 页数: 5页
• 分类号: O157.5
• 语种: 中文

摘要

设G,H是阶至少为2的简单图.图G与日的强直积是指这样一个图G(□)H,其顶点集合为V(G)×V(H),并且(x_1,x_2)(y_1,y_2)∈E(G(□)H).当且仅当[x_1y_1 ∈E(G)且x_2y_2 ∈ E(H)]或者[x_1=y_1且x_2y_2 ∈E(H)]或者[x_2=y_2且x_1y_1 ∈ E(G)].一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色.对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为x_2(G).文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:△(G(□)H)+1≤x_2(G□H)≤(G)·x_2(H).对一些特殊图,例如P_m(□)P_n,P_m(□)K_n,P_m(□)W_n,P_m(□)S_n,P_m(□)F_n,P_m(□)C_n(n≡0(mod 3)或者n=5),给出了它们的2-距离色数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马宝林	西北师范大学数学与信息科学学院	29	36	3.0	5.0
3	陈祥恩	西北师范大学数学与信息科学学院	155	1069	14.0	28.0
4	刘娟	河南科技学院数学系	49	72	5.0	6.0