具有较小直径的三类图的对极色数  

Antipodal Chromatic Number of Three Classes of Graphs with Small Diameter

作　　者：申玉发[1] 董丽沙[2] 肖欣[1] 武利猛[1] 郑国萍[1] 

机构地区：[1]河北科技师范学院数学与信息科技学院,河北秦皇岛066004 [2]河北工业大学理学院,天津300401

出　　处：《数学的实践与认识》2014年第23期198-204,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10871058);河北科技师范学院科研创新团队资助计划(CXTD2012-08);河北科技师范学院博士基金(2013YB008)

摘　　要：对一个连通图G,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d.For a connected graph G, let d（u, v） denote the distance between two vertices u and v of G, and d be the diameter of G. An antipodal coloring c of G is an assignment of positive integers （colors） to the vertices of G, such that d（u, v） ＋ │c（u） - c（v）│ 〉 d for every pair u and v of distinct vertices of G. The value ac（c） is the maximum color assigned to a vertex of G by c, the antipodal chromatic number ac（G） of G is the minimum of ac（c） taken over all antipodal coloring c of G. In this paper, we determine the exact values of antipodal chromatic number for wheel graphs, gear graphs and double star graphs, which all have smalldiameter d.

关 键 词：Radio染色 对极色数 轮图 齿轮图 双星图 

分 类 号：O157.5[理学—数学]