In order to solve the channel assignment problem in network information transmission system,more restrictions are given to the more important substructures(called backbone)when designing a network,and less restrictions are given to the other parts of the network,and this type of problem can be abstracted as the backbone coloring of graphs,which is an important variant of the classical coloring theory.Using square of cycle and generalized Peterson graph to describe two special types of network information transmission systems,and considering the Hamiltonian path as the backbone of the graph,the λ-backbone coloring of the square of cycle and the generalized Petersen graph is investigated,and BBCλ(G,P)=λ+2 is obtained.
关键词
BB-染色/哈密顿路径/圈平方图/广义Petersen图/非平面图
Key words
backbone coloring/Hamiltonian path/square of cycles/generalized Petersen graphs/nonplanar graph
维普
万方数据