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

摘要

对一个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的值,记作k(c).将Min{ hc(c)｜c是G的H着色}称为G的Hamiltonian色数(以下简称G的H色数),记作hc(G).如果G的一个H着色c满足k(c)=hc(G),则称c为G的一个最小H着色.本次研究得到了完全正则m-元树的H色数的确切值,并给出了其最小H着色.