完全正则m-元树的Hamiltonian色数与最小Hamiltonian着色  

Hamiltonian Chromatic Number and Minimum Hamiltonian Coloring of The Completely Regular m-ary Trees

作　　者：申玉发[1] 郭玲玲 周雪 王莹[1] SHEN Yufa;GUO Lingling;ZHOU Xue;WANG Ying(School of Mathematics and Information Science & Technology,Hebei Normal University of Science &Technology,Qinhuangdao Hebei,066004;Applied Mathematics Institute,Hebei University of Technology;Guangming Primary School of Hebei District of Tianjin,China)

机构地区：[1]河北科技师范学院数学与信息科技学院,河北秦皇岛066004 [2]河北工业大学应用数学研究所 [3]天津市河北区光明小学

出　　处：《河北科技师范学院学报》2019年第2期35-40,共6页Journal of Hebei Normal University of Science & Technology

基　　金：国家自然科学基金项目(项目编号:11571091);河北科技师范学院博士基金项目(项目编号:2018YB016)

摘　　要：对一个n阶连通图G,G的Hamiltonian着色(以下简称G的H着色)定义为从G的顶点集V(G)到正整数集N(称为颜色集)的一个映射c,且对G的任意2个不同顶点u和v,满足|c(u)-c(v)|+D(u,v)≥n-1,其中D(u,v)表示G中u到v的最长路径的长度。对G的一个H着色c,将Max{c(u)|u∈V(G)}称为c的值,记作hc(c)。将Min{hc(c)|c是G的H着色}称为G的Hamiltonian色数(以下简称G的H色数),记作hc(G)。如果G的一个H着色c满足hc(c)=hc(G),则称c为G的一个最小H着色。本次研究得到了完全正则m-元树的H色数的确切值,并给出了其最小H着色。For a connected graph of G order n , a Hamiltonian coloring of G (named a H coloring of G for short) is a mapping c from a set of vertices of G to a set of positive integers V(G)→{1,2,3,…}(called a color set). And for every two distinct vertices u and v of G , the formula |c(u)-c(v)|+D(u,v)≥n-1 will be satisfied, in whih D(u,v) is the length of a longest u-v path in G . The Hamiltonian chromatic number hc(G) of G (named the H chromatic number hc(G ) of G for short) is Min{ hc(c)} taken over all H coloring c of G . A H coloring c of G is a minimum H coloring if hc(c)=hc(G). The exact values of H chromatic number for the completely regular m -ary trees are obtained, and a minimum H coloring for them is presented.

关 键 词：Hamiltonian着色 Hamiltonian色数 完全正则m-元树 最小Hamiltonian着色 

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